HOME

TheInfoList



OR:

In the
mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
field of
graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, the distance between two vertices in a
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...
is the number of edges in a
shortest path In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between ...
(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 In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pa ...
the distance between two vertices and is defined as the length of a shortest directed path from to consisting of arcs, provided at least one such path exists. Notice that, in contrast with the case of undirected graphs, does not necessarily coincide with —so it is just a quasi-metric, and it might be the case that one is defined while the other is not.


Related concepts

A
metric space In mathematics, a metric space is a set together with a notion of '' distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general setti ...
defined over a set of points in terms of distances in a graph defined over the set is called a graph metric. The vertex set (of an undirected graph) and the distance function form a metric space, if and only if the graph is
connected Connected may refer to: Film and television * ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular'' * '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film * ''Connected'' (2015 TV ...
. The eccentricity of a vertex is the greatest distance between and any other vertex; in symbols, :\epsilon(v) = \max_d(v,u). 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 or, in symbols, :r = \min_ \epsilon(v) = \min_\max_d(v,u). The diameter of a graph is the maximum eccentricity of any vertex in the graph. That is, is the greatest distance between any pair of vertices or, alternatively, :d = \max_\epsilon(v) = \max_\max_d(v,u). To find the diameter of a graph, first find the
shortest path In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between ...
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 is one whose eccentricity is —that is, a vertex whose distance from its furthest vertex is equal to the radius, equivalently, a vertex such that . A peripheral vertex in a graph of diameter is one whose eccentricity is —that is, a vertex whose distance from its furthest vertex is equal to the diameter. Formally, is peripheral if . A pseudo-peripheral vertex has the property that, for any vertex , if is as far away from as possible, then is as far away from as possible. Formally, a vertex is pseudo-peripheral if, for each vertex with , it holds that . A
level structure In the mathematical subfield of graph theory a level structure of an undirected graph is a partition of the vertices into subsets that have the same distance from a given root vertex.. Definition and construction Given a connected graph ''G'' ...
of the graph, given a starting vertex, is a partition of the graph's vertices into subsets by their distances from the starting vertex. A
geodetic graph In graph theory, a geodetic graph is an undirected graph such that there exists a unique (unweighted) shortest path between each two vertices. Geodetic graphs were introduced in 1962 by Øystein Ore, who observed that they generalize a property of ...
is one for which every pair of vertices has a unique shortest path connecting them. For example, all
trees In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are u ...
are geodetic.
Øystein Ore Øystein Ore (7 October 1899 – 13 August 1968) was a Norwegian mathematician known for his work in ring theory, Galois connections, graph theory, and the history of mathematics. Life Ore graduated from the University of Oslo in 1922, with ...
, Theory of graphs rd ed., 1967 Colloquium Publications, American Mathematical Society, p. 104
The weighted shortest-path distance generalises the geodesic distance to weighted graphs. In this case it is assumed that the weight of an edge represents its length or, for
complex networks Complex Networks is an American media and entertainment company for youth culture, based in New York City. It was founded as a bi-monthly magazine, ''Complex'', by fashion designer Marc (Ecko) Milecofsky. Complex Networks reports on popular ...
the cost of the interaction, and the weighted shortest-path distance is the minimum sum of weights across all the paths connecting and . See the
shortest path problem In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between ...
for more details and algorithms.


Algorithm for finding pseudo-peripheral vertices

Often peripheral
sparse matrix In numerical analysis and scientific computing, a sparse matrix or sparse array is a matrix in which most of the elements are zero. There is no strict definition regarding the proportion of zero-value elements for a matrix to qualify as sparse b ...
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: # Choose a vertex u. # Among all the vertices that are as far from u as possible, let v be one with minimal degree. # If \epsilon(v) > \epsilon(u) then set u=v and repeat with step 2, else u is a pseudo-peripheral vertex.


See also

*
Distance matrix In mathematics, computer science and especially graph theory, a distance matrix is a square matrix (two-dimensional array) containing the distances, taken pairwise, between the elements of a set. Depending upon the application involved, the ''dist ...
*
Resistance distance In graph theory, the resistance distance between two vertices of a simple, connected graph, , is equal to the resistance between two equivalent points on an electrical network, constructed so as to correspond to , with each edge being replaced ...
*
Betweenness centrality In graph theory, betweenness centrality (or "betweeness centrality") is a measure of centrality in a graph based on shortest paths. For every pair of vertices in a connected graph, there exists at least one shortest path between the vertices suc ...
*
Centrality In graph theory and network analysis, indicators of centrality assign numbers or rankings to nodes within a graph corresponding to their network position. Applications include identifying the most influential person(s) in a social network, key ...
* Closeness *
Degree diameter problem In graph theory, the degree diameter problem is the problem of finding the largest possible graph (in terms of the size of its vertex set ) of diameter such that the largest degree of any of the vertices in is at most . The size of is bound ...
for
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...
s and digraphs *
Metric graph In mathematics and physics, a quantum graph is a linear, network-shaped structure of vertices connected on edges (i.e., a graph) in which each edge is given a length and where a differential (or pseudo-differential) equation is posed on each ed ...


Notes

{{reflist Graph theory Metric geometry