In the mathematical field of graph theory, the distance between two vertices in a graph is the number of edges in a shortest path connecting them. This is also known as the geodesic distance because it is the length of the graph geodesic between those 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.

PropertyValue
dbpprop:abstract
  • In the mathematical field of graph theory, the distance between two vertices in a graph is the number of edges in a shortest path connecting them. This is also known as the geodesic distance because it is the length of the graph geodesic between those 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. The vertex set and the distance function form a metric space, if and only if the graph is connected. A metric defined over a set of points in terms of distances in a graph defined over the set is called a graph metric. There are a number of other measurements defined in terms of distance: The eccentricity <math>\epsilon</math> of a vertex <math>v</math> is the greatest distance between <math>v</math> and any other vertex. The radius of a graph is the minimum eccentricity of any vertex. The diameter of a graph is the maximum eccentricity of any vertex in the graph. That is, it is the greatest distance between any two vertices. A peripheral vertex in a graph of diameter <math>d</math> is one that is distance <math>d</math> from some other vertex—that is, a vertex that achieves the diameter. A pseudo-peripheral vertex <math>v</math> has the property that for any vertex <math>u</math>, if <math>v</math> is as far away from <math>u</math> as possible, then <math>u</math> is as far away from <math>v</math> as possible. Formally, if the distance from <math>u</math> to <math>v</math> equals the eccentricity of <math>u</math>, then it equals the eccentricity of <math>v</math>.
  • Średnica grafu spójnego to odległość na jaką są oddalone dwa najodleglejsze wierzchołki grafu czyli najmniejsza taka liczba n, że dowolne dwa wierzchołki łączy ścieżka długości co najwyżej n. Jedynymi grafami o średnicy równej 1 są grafy pełne. Definicję średnicy grafu rozszerza się czasami na grafy niespójne, przyjmując, że jest ona nieskończona.
dbpprop:hasPhotoCollection
rdfs:comment
  • In the mathematical field of graph theory, the distance between two vertices in a graph is the number of edges in a shortest path connecting them. This is also known as the geodesic distance because it is the length of the graph geodesic between those 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.
  • Średnica grafu spójnego to odległość na jaką są oddalone dwa najodleglejsze wierzchołki grafu czyli najmniejsza taka liczba n, że dowolne dwa wierzchołki łączy ścieżka długości co najwyżej n. Jedynymi grafami o średnicy równej 1 są grafy pełne. Definicję średnicy grafu rozszerza się czasami na grafy niespójne, przyjmując, że jest ona nieskończona.
rdfs:label
  • Distance (graph theory)
  • Średnica grafu
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of