Inline videos. See also:Category: Articles with embedded Videos..

Distance (graph theory)

From Biocrawler, the free encyclopedia.

In the mathematical subfield of graph theory we can define a notion of distance between two vertices in a graph.

Contents

1 Definition

1.1 Eccentricity
1.2 Diameter
1.3 Peripheral vertex
1.4 Pseudo-peripheral vertex

2 Algorithm for finding pseudo-peripheral vertices

3 See also

[edit]

Definition

Given a graph G:=(V,E) with V the set of vertices and E the set of edges 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

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.

[edit]

Eccentricity

The eccentricity of a vertex v is

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

[edit]

Diameter

The diameter of the graph is defined as

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

[edit]

Peripheral vertex

A peripheral vertex for G is a vertex v with

ε(v) = δ(G)

[edit]

Pseudo-peripheral vertex

A vertex v is called pseudo-peripheral vertex if for any vertex u with

d G (v, u) = ε(u)

then

ε(v) = ε(u)

[edit]

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 ε(v)$ with minimal degree
if $ε(u) > ε(v)$ then set v=u and repeat with step 2 else u is a pseudo-peripheral vertex