Psychology Wiki

Distance (graph theory)

34,203pages on
this wiki
Add New Page
Talk0 Share

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).

Ad blocker interference detected!

Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

Also on Fandom

Random Wiki