Wikia

Statistics: Scientific method · Research methods · Experimental design · Undergraduate statistics courses · Statistical tests · Game theory · Decision 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.

There are a number of other measurements defined in terms of distance:

The eccentricity $\epsilon$ of a vertex $v$ is the greatest distance between $v$ 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 $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, if the distance from $u$ to $v$ equals the eccentricity of $u$ , then it equals the eccentricity of $v$ .

Algorithm for finding pseudo-peripheral verticesEdit

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:

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 v is a pseudo-peripheral vertex.

Wikia

Distance (graph theory)

Algorithm for finding pseudo-peripheral verticesEdit

See alsoEdit

Photos

Recent Wiki Activity