This HTML5 document contains 109 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

Prefix	IRI
dbpedia-sl	http://sl.dbpedia.org/resource/
dcterms	http://purl.org/dc/terms/
dbo	http://dbpedia.org/ontology/
foaf	http://xmlns.com/foaf/0.1/
dbpedia-hu	http://hu.dbpedia.org/resource/
dbpedia-ca	http://ca.dbpedia.org/resource/
dbpedia-ko	http://ko.dbpedia.org/resource/
dbpedia-es	http://es.dbpedia.org/resource/
n16	https://global.dbpedia.org/id/
dbpedia-he	http://he.dbpedia.org/resource/
yago	http://dbpedia.org/class/yago/
dbpedia-ru	http://ru.dbpedia.org/resource/
dbt	http://dbpedia.org/resource/Template:
dbpedia-uk	http://uk.dbpedia.org/resource/
rdfs	http://www.w3.org/2000/01/rdf-schema#
freebase	http://rdf.freebase.com/ns/
dbpedia-sr	http://sr.dbpedia.org/resource/
dbpedia-pl	http://pl.dbpedia.org/resource/
dbpedia-pt	http://pt.dbpedia.org/resource/
dbpedia-cs	http://cs.dbpedia.org/resource/
dbpedia-fa	http://fa.dbpedia.org/resource/
rdf	http://www.w3.org/1999/02/22-rdf-syntax-ns#
owl	http://www.w3.org/2002/07/owl#
dbpedia-sk	http://sk.dbpedia.org/resource/
dbpedia-fr	http://fr.dbpedia.org/resource/
dbpedia-zh	http://zh.dbpedia.org/resource/
wikipedia-en	http://en.wikipedia.org/wiki/
dbp	http://dbpedia.org/property/
prov	http://www.w3.org/ns/prov#
dbc	http://dbpedia.org/resource/Category:
xsdh	http://www.w3.org/2001/XMLSchema#
wikidata	http://www.wikidata.org/entity/
dbr	http://dbpedia.org/resource/

Statements

Subject Item

dbr:Distance_(graph_theory)

rdf:type

yago:Abstraction100002137 yago:Concept105835747 yago:Invariant105850432 yago:PsychologicalFeature100023100 yago:Property105849040 yago:Content105809192 yago:Feature105849789 yago:Idea105833840 yago:WikicatGraphInvariants yago:Cognition100023271

rdfs:label

Distancia (teoría de grafos) Odległość (teoria grafów) Distance (graph theory) Vzdálenost (teorie grafů) Метрика кратчайшего пути Distância (teoria dos grafos) 距离 (图论) 거리 (그래프 이론) Distance (théorie des graphes) Відстань (теорія графів) Distància (teoria de grafs)

rdfs:comment

Odległość między dwoma wierzchołkami definiuje się w teorii grafów jako liczbę krawędzi w najkrótszej ścieżce, łączącej rozpatrywane wierzchołki. W przypadku, gdy nie istnieje taka ścieżka, tj. gdy wierzchołki z danej pary należą do odrębnych spójnych składowych jednego grafu niespójnego, odległość z definicji równa się nieskończoności. W ten sposób zdefiniowana odległość może zostać znaleziona poprzez zastosowanie algorytmu przeszukiwania wszerz (BFS) bądź algorytmu Dijkstry. Graf z tak określoną funkcją odległości jest przestrzenią metryczną. En teoria de grafs, la distància entre els dos vèrtexs d'un graf és el nombre d'arestes en el camí més curt que els uneix. Això també es coneix com a distància geodèsica. Hi pot haver més d'un camí més curt entre dos vèrtexs. Si no hi ha cap camí que uneixi els dos vèrtexs, per exemple perquè pertanyen a diferents components, per convenció es diu que la distància entre ells és infinita. Метрика кратчайшего пути — метрика на вершинах графа равная числу рёбер в кратчайшем пути между даннымми вершинами.Если нет пути между двумя вершинами, то есть если они принадлежат различным компонентам связности, то принято считать расстояние бесконечным. В случае ориентированных графов расстояние между двумя вершинами и определяется как длина кратчайшего пути из в , состоящий из дуг. В отличие от случая неориентированных графов может не совпадать с и даже может случиться, что одно расстояние существует, а другое — нет. No campo da matemática da teoria dos grafos, a distância entre dois vértices em um grafo é o número de arestas em um caminho mínimo conectando eles. Em outras palavras, denomina-se distância d(v, w) de um grafo como sendo o comprimento do menor caminho entre v e w. Isso também é conhecido como distância geodésica porque é o comprimento do grafo geodésico entre os dois vértices. A distância entre dois vértices v1 e v2 é d se e somente se existe um caminho de comprimento d de v1 a v2 e nenhum caminho de v1 a v2 tem comprimento menor que d. Se não existe caminho algum conectando dois vértices, ou seja, se eles pertencem a diferentes , então convencionalmente a distância entre eles é definida como infinita. У теорії графів, відстань між двома вершинами графа — це кількість ребер у найкоротшому шляху, що сполучає їх. Це поняття також відоме як геодезична відстань. Зауважте, що може існувати більш ніж один найкоротший шлях між двома вершинами. Якщо нема шляху, що поєднував би дві вершини, тобто, якщо вони належать до різних компонент зв'язності, тоді ми кажемо, що відстань нескінченна. 在图论中，一张无向图里，两顶点之间的距离是指他们之间最短路径（英語：shortest path）的长度，两顶点之间的距离也被称为测地距离（英語：geodesic distance）。需要注意的是两个顶点之间可能有多条最短路径，如果两个顶点之间不存在路径（即他们属于不同的连通分量），那么按照传统它们距离被定义为无穷大。 在有向图中，如果从顶点 到顶点 存在有向路径（英語：directed path），那么距离 被定义为从顶点 到顶点 之间最短有向路径的长度。不同于无向图，在有向图中 不一定和 相等，甚至有可能出现从顶点 到顶点 存在有向路径，而从顶点 到顶点 却不存在有向路径的情况。 En théorie des graphes, la distance entre deux nœuds d'un graphe est la longueur d'un plus court chemin entre ces deux nœuds. La longueur d'un chemin est sa longueur en nombre d'arêtes. Pour un graphe pondéré c'est la somme des poids des arêtes empruntées. Pour les graphes non orientés, c'est une distance au sens mathématique, tandis que pour les graphes orientés elle ne vérifie pas la propriété de symétrie. Cette notion permet entre autres de définir le diamètre et le rayon d'un graphe. 그래프 이론의 수학적 영역에서, 그래프의 두 꼭짓점간의 거리는 두 점을 잇는 최단 경로(그래프 지오데식(영어: geodesic)이라고도 불린다)에 있는 모서리의 개수이다. 이 거리는 지오데식 거리(영어: geodesic distance)라고도 부른다. 두 꼭짓점 사이에는 최단 경로가 하나 이상 있을 수 있다는 점을 주목하라. 두 꼭짓점 사이에 경로가 없을 때, 즉, 두 꼭짓점이 서로 다른 연결 요소에 있다면, 전통적으로 거리는 무한으로 정의한다. 유향 그래프의 경우에 호로 이루어진 두 점 와 간의 거리 는 에서 까지 가는 경로가 적어도 하나가 있을 때, 가장 짧은 거리로 정의한다. 무향 그래프의 경우와는 달리 는 와 같을 필요가 없고, 하나는 정의되고 다른 하나는 정의되지 않을 수도 있다. En teoría de grafos se denomina distancia o distancia geodésica entre dos vértices o nodos de un grafo a la longitud o número de aristas del camino más corto entre ellos.​​ Si dos vértices no son accesibles a través de un camino, entonces la distancia entre ellos es infinita.​ Las distancias de todos los vértices de un grafo se pueden representar mediante una matriz de distancias. Délku nejkratší cesty mezi vrcholy a v souvislém grafu (na obrázku) nazýváme vzdáleností a v a označujeme . Například v grafu G (na obrázku) platí: , , .Dá se dokázat, že funkce je v souvislém grafu metrikou. In the mathematical field of graph theory, the distance between two vertices in a graph is the number of edges in a shortest path (also called a graph geodesic) connecting them. This is also known as the geodesic distance or shortest-path distance. Notice that there may be more than one shortest path between two vertices. If there is no path connecting the two vertices, i.e., if they belong to different connected components, then conventionally the distance is defined as infinite.

dcterms:subject

dbc:Graph_distance dbc:Metric_geometry dbc:Graph_theory

dbo:wikiPageID

1020021

dbo:wikiPageRevisionID

1104616628

dbo:wikiPageWikiLink

dbr:Tree_(graph_theory) dbr:Sparse_matrix dbc:Graph_distance dbr:Graph_theory dbr:Metric_graph dbr:Degree_(graph_theory) dbr:Glossary_of_graph_theory dbr:Centrality dbc:Metric_geometry dbr:Distance_matrix dbr:Digraph_(mathematics) dbr:Path_(graph_theory) dbr:Metric_(mathematics) dbr:Betweenness_centrality dbr:Directed_graph dbr:Complex_networks dbr:Geodetic_graph dbr:Level_structure dbc:Graph_theory dbr:Metric_space dbr:Resistance_distance dbr:Graph_(discrete_mathematics) dbr:Mathematics dbr:Closeness_(graph_theory) dbr:Connected_(graph_theory) dbr:Partition_of_a_set dbr:Connected_component_(graph_theory) dbr:Degree_diameter_problem dbr:Vertex_(graph_theory) dbr:Shortest_path_problem

owl:sameAs

dbpedia-sr:Rastojanje_(teorija_grafova) dbpedia-pt:Distância_(teoria_dos_grafos) dbpedia-uk:Відстань_(теорія_графів) n16:2ZVQw dbpedia-ko:거리_(그래프_이론) wikidata:Q2742711 dbpedia-fr:Distance_(théorie_des_graphes) dbpedia-es:Distancia_(teoría_de_grafos) dbpedia-hu:Távolság_(gráfelmélet) dbpedia-sk:Vzdialenosť_(teória_grafov) freebase:m.03zx8z dbpedia-zh:距离_(图论) dbpedia-ca:Distància_(teoria_de_grafs) dbpedia-cs:Vzdálenost_(teorie_grafů) dbpedia-sl:Razdalja_(teorija_grafov) dbpedia-fa:فاصله_در_گراف dbpedia-ru:Метрика_кратчайшего_пути dbpedia-pl:Odległość_(teoria_grafów) dbpedia-he:מרחק_(תורת_הגרפים)

dbp:wikiPageUsesTemplate

dbt:Colend dbt:Sup dbt:Math dbt:Reflist dbt:Anchor dbt:Redirect dbt:Mvar dbt:Short_description dbt:Col_div

dbo:abstract

No campo da matemática da teoria dos grafos, a distância entre dois vértices em um grafo é o número de arestas em um caminho mínimo conectando eles. Em outras palavras, denomina-se distância d(v, w) de um grafo como sendo o comprimento do menor caminho entre v e w. Isso também é conhecido como distância geodésica porque é o comprimento do grafo geodésico entre os dois vértices. A distância entre dois vértices v1 e v2 é d se e somente se existe um caminho de comprimento d de v1 a v2 e nenhum caminho de v1 a v2 tem comprimento menor que d. Se não existe caminho algum conectando dois vértices, ou seja, se eles pertencem a diferentes , então convencionalmente a distância entre eles é definida como infinita. Odległość między dwoma wierzchołkami definiuje się w teorii grafów jako liczbę krawędzi w najkrótszej ścieżce, łączącej rozpatrywane wierzchołki. W przypadku, gdy nie istnieje taka ścieżka, tj. gdy wierzchołki z danej pary należą do odrębnych spójnych składowych jednego grafu niespójnego, odległość z definicji równa się nieskończoności. W ten sposób zdefiniowana odległość może zostać znaleziona poprzez zastosowanie algorytmu przeszukiwania wszerz (BFS) bądź algorytmu Dijkstry. Graf z tak określoną funkcją odległości jest przestrzenią metryczną. W szczególnym przypadku grafu pełnego odległość między dowolną parą wierzchołków jest równa 1. 그래프 이론의 수학적 영역에서, 그래프의 두 꼭짓점간의 거리는 두 점을 잇는 최단 경로(그래프 지오데식(영어: geodesic)이라고도 불린다)에 있는 모서리의 개수이다. 이 거리는 지오데식 거리(영어: geodesic distance)라고도 부른다. 두 꼭짓점 사이에는 최단 경로가 하나 이상 있을 수 있다는 점을 주목하라. 두 꼭짓점 사이에 경로가 없을 때, 즉, 두 꼭짓점이 서로 다른 연결 요소에 있다면, 전통적으로 거리는 무한으로 정의한다. 유향 그래프의 경우에 호로 이루어진 두 점 와 간의 거리 는 에서 까지 가는 경로가 적어도 하나가 있을 때, 가장 짧은 거리로 정의한다. 무향 그래프의 경우와는 달리 는 와 같을 필요가 없고, 하나는 정의되고 다른 하나는 정의되지 않을 수도 있다. In the mathematical field of graph theory, the distance between two vertices in a graph is the number of edges in a shortest path (also called a graph geodesic) connecting them. This is also known as the geodesic distance or shortest-path distance. Notice that there may be more than one shortest path between two vertices. If there is no path connecting the two vertices, i.e., if they belong to different connected components, then conventionally the distance is defined as infinite. In the case of a directed graph the distance d(u,v) between two vertices u and v is defined as the length of a shortest directed path from u to v consisting of arcs, provided at least one such path exists. Notice that, in contrast with the case of undirected graphs, d(u,v) does not necessarily coincide with d(v,u)—so it is just a quasi-metric, and it might be the case that one is defined while the other is not. En teoria de grafs, la distància entre els dos vèrtexs d'un graf és el nombre d'arestes en el camí més curt que els uneix. Això també es coneix com a distància geodèsica. Hi pot haver més d'un camí més curt entre dos vèrtexs. Si no hi ha cap camí que uneixi els dos vèrtexs, per exemple perquè pertanyen a diferents components, per convenció es diu que la distància entre ells és infinita. En el cas d'un graf dirigit la distància entre els dos vèrtexs i es defineix com la longitud del camí més curt des de fins a consistent en arcs, sempre que existeixi un camí. En contrast amb els grafs no dirigits, i poden no coincidir o fins i tot pot ser que una de les dues estigui definida i l'altra no. У теорії графів, відстань між двома вершинами графа — це кількість ребер у найкоротшому шляху, що сполучає їх. Це поняття також відоме як геодезична відстань. Зауважте, що може існувати більш ніж один найкоротший шлях між двома вершинами. Якщо нема шляху, що поєднував би дві вершини, тобто, якщо вони належать до різних компонент зв'язності, тоді ми кажемо, що відстань нескінченна. Для орієнтованого графа відстань між двома вершинами та визначається як довжина найкоротшого орієнтованого шляху з в за умови, що принаймні один такий шлях існує. Зауважте, що на відміну від неорієнтованого графа, відстань не обов'язково збігається з , і можливі випадки, коли одна відстань визначена, а інша ні. En teoría de grafos se denomina distancia o distancia geodésica entre dos vértices o nodos de un grafo a la longitud o número de aristas del camino más corto entre ellos.​​ Si dos vértices no son accesibles a través de un camino, entonces la distancia entre ellos es infinita.​ Las distancias de todos los vértices de un grafo se pueden representar mediante una matriz de distancias. Délku nejkratší cesty mezi vrcholy a v souvislém grafu (na obrázku) nazýváme vzdáleností a v a označujeme . Například v grafu G (na obrázku) platí: , , .Dá se dokázat, že funkce je v souvislém grafu metrikou. En théorie des graphes, la distance entre deux nœuds d'un graphe est la longueur d'un plus court chemin entre ces deux nœuds. La longueur d'un chemin est sa longueur en nombre d'arêtes. Pour un graphe pondéré c'est la somme des poids des arêtes empruntées. Pour les graphes non orientés, c'est une distance au sens mathématique, tandis que pour les graphes orientés elle ne vérifie pas la propriété de symétrie. Cette notion permet entre autres de définir le diamètre et le rayon d'un graphe. 在图论中，一张无向图里，两顶点之间的距离是指他们之间最短路径（英語：shortest path）的长度，两顶点之间的距离也被称为测地距离（英語：geodesic distance）。需要注意的是两个顶点之间可能有多条最短路径，如果两个顶点之间不存在路径（即他们属于不同的连通分量），那么按照传统它们距离被定义为无穷大。 在有向图中，如果从顶点 到顶点 存在有向路径（英語：directed path），那么距离 被定义为从顶点 到顶点 之间最短有向路径的长度。不同于无向图，在有向图中 不一定和 相等，甚至有可能出现从顶点 到顶点 存在有向路径，而从顶点 到顶点 却不存在有向路径的情况。 Метрика кратчайшего пути — метрика на вершинах графа равная числу рёбер в кратчайшем пути между даннымми вершинами.Если нет пути между двумя вершинами, то есть если они принадлежат различным компонентам связности, то принято считать расстояние бесконечным. В случае ориентированных графов расстояние между двумя вершинами и определяется как длина кратчайшего пути из в , состоящий из дуг. В отличие от случая неориентированных графов может не совпадать с и даже может случиться, что одно расстояние существует, а другое — нет.

prov:wasDerivedFrom

wikipedia-en:Distance_(graph_theory)?oldid=1104616628&ns=0

dbo:wikiPageLength

6727

foaf:isPrimaryTopicOf

wikipedia-en:Distance_(graph_theory)