Distance (graph theory)

In the mathematics subfield of graph theory we can define a notion of distance between two vertex_(graph theory) in a graph. ==Definition== Given a graph ''G'':=(''V'',''E'') with ''V'' the set of vertex_(graph theory) and ''E'' the set of edge_(graph theory) then the distance between two vertices is the number of edges in a shortest path connecting the two vertices. We denote the distance of two vertices

u

and

v

by :

\mathrm{d}_G(u,v)

The vertex set ''V'' of a connected graph ''G'' thus becomes a metric space. For given ordering of vertices it is common to store distances in a distance matrix ''D''(''G'')of a graph. ===Eccentricity=== The eccentricity of a vertex ''v'' is :

\epsilon(v):= \max_{u \in V} \mathrm{d}_G(v,u)

===Diameter=== The diameter of the graph is defined as :

\delta(G):= \max_{v \in V} \epsilon_G(v)

===Peripheral vertex=== A peripheral vertex for ''G'' is a vertex ''v'' with :

\epsilon(v)=\delta(G)

===Pseudo-peripheral vertex=== A vertex ''v'' is called pseudo-peripheral vertex if for any vertex ''u'' with :

\mathrm{d}_G(v,u) = \epsilon(u)

then :

\epsilon(v) = \epsilon(u)

==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. By constructing level structures for the graph we can easily find such a pseudo-peripheral vertex. #choose a vertex ''v'' in ''V'' #create a level structure with root ''v''

\lbrace L_0(v),\ldots,L_{\epsilon(v)}(v)\rbrace

#choose a vertex ''u'' in

L_{\epsilon(v)}

with minimal degree #if

\epsilon(u) > \epsilon(v)

then set ''v''=''u'' and repeat with step 2 else ''u'' is a pseudo-peripheral vertex ==See also== * Betweenness * Centrality * Closeness (graph theory) Graph theory

See other meanings of words starting from letter:

D

DA | DB | DC | DE | DF | DG | DH | DI | DJ | DK | DL | DM | DN | DO | DP | DR | DS | DT | DU | DW | DX | DY | DZ |

Words begining with Distance_(graph_theory):

Distance_(graph_theory)