Distance (graph theory)

Distance (graph theory)

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 [1] because it is the length of the graph geodesic between those two vertices.[2] 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 (of an undirected graph) 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 \epsilon of a vertex v is the greatest geodesic distance between v and any other vertex. It can be thought of as how far a node is from the node most distant from it in the graph.

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 pair of vertices. To find the diameter of a graph, first find the shortest path between each pair of vertices. The greatest length of any of these paths is the diameter of the graph.

A central vertex in a graph of radius r is one whose eccentricity is r—that is, a vertex that achieves the radius.

A peripheral vertex in a graph of diameter d is one that is distance d from some other vertex—that is, a vertex that achieves the diameter.

A pseudo-peripheral vertex v has the property that for any vertex u, if v is as far away from u as possible, then u is as far away from v as possible. Formally, a vertex u is pseudo-peripheral, if for each vertex v with d(u,v) = \epsilon(u) holds \epsilon(u)=\epsilon(v).

Algorithm for finding pseudo-peripheral vertices

Often peripheral sparse matrix algorithms need a starting vertex with a high eccentricity. A peripheral vertex would be perfect, but is often hard to calculate. In most circumstances a pseudo-peripheral vertex can be used. A pseudo-peripheral vertex can easily be found with the following algorithm:

  1. Choose a vertex u.
  2. Among all the vertices that are as far from u as possible, let v be one with minimal degree.
  3. If \epsilon(v) > \epsilon(u) then set u = v and repeat with step 2, else v is a pseudo-peripheral vertex.

See also

Notes

  1. ^ Bouttier, Jérémie; Di Francesco,P. ,Guitter, E. (July 2003). "Geodesic distance in planar graphs". Nuclear Physics B 663 (3): 535–567. doi:10.1016/S0550-3213(03)00355-9. http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TVC-48KW72R-1&_user=3742306&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000061256&_version=1&_urlVersion=0&_userid=3742306&md5=86dd4de63373a7e72d23d16840947661. Retrieved 2008-04-23. "By distance we mean here geodesic distance along the graph, namely the length of any shortest path between say two given faces" 
  2. ^ Weisstein, Eric W.. "Graph Geodesic". MathWorld--A Wolfram Web Resource. Wolfram Research. http://mathworld.wolfram.com/GraphGeodesic.html. Retrieved 2008-04-23. "The length of the graph geodesic between these points d(u,v) is called the graph distance between u and v" 

Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and …   Wikipedia

  • Geometric graph theory — In mathematics, a geometric graph is a graph in which the vertices or edges are associated with geometric objects or configurations. Geometric graph theory is a specialization of graph theory that studies geometric graphs. Notable geometric… …   Wikipedia

  • Algebraic graph theory — is a branch of mathematics in which algebraic methods are applied to problems about graphs. In one sense, algebraic graph theory studies graphs in connection with linear algebra. Especially, it studies the spectrum of the adjacency matrix, the… …   Wikipedia

  • Tree (graph theory) — Trees A labeled tree with 6 vertices and 5 edges Vertices v Edges v 1 Chromatic number …   Wikipedia

  • Girth (graph theory) — In graph theory, the girth of a graph is the length of a shortest cycle contained in the graph.[1] If the graph does not contain any cycles (i.e. it s an acyclic graph), its girth is defined to be infinity.[2] For example, a 4 cycle (square) has… …   Wikipedia

  • Star (graph theory) — Star The star S7. (Some authors index this as S8.) Vertices k+1 Edges k …   Wikipedia

  • Glossary of graph theory — Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with… …   Wikipedia

  • De Bruijn–Erdős theorem (graph theory) — This article is about coloring infinite graphs. For the number of lines determined by a finite set of points, see De Bruijn–Erdős theorem (incidence geometry). In graph theory, the De Bruijn–Erdős theorem, proved by Nicolaas Govert de Bruijn and… …   Wikipedia

  • Unit distance graph — In mathematics, and particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points by an edge whenever the distance between the two points is exactly one.… …   Wikipedia

  • Metric dimension (graph theory) — In graph theory, the metric dimension of a graph G is the minimum number of vertices in a subset S of G such that all other vertices are uniquely determined by their distances to the vertices in S. Finding the metric dimension of a graph is an NP …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”