Psychology Wiki

Distance (graph theory)

34,135pages on
this wiki
Revision as of 23:20, February 8, 2007 by Dr Joe Kiff (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Assessment | Biopsychology | Comparative | Cognitive | Developmental | Language | Individual differences | Personality | Philosophy | Social |
Methods | Statistics | Clinical | Educational | Industrial | Professional items | World psychology |

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:

  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 alsoEdit

he:מרחק (תורת הגרפים)
This page uses Creative Commons Licensed content from Wikipedia (view authors).

Around Wikia's network

Random Wiki