In the mathematical subfield of graph theory we can define a notion of **distance** between two vertices in a graph. Wikibooks Wikiversity has more about this subject: School of Mathematics Wikiquote has a collection of quotations by or about: Mathematics Look up Mathematics in Wiktionary, the free dictionary Wikimedia Commons has more media related to: Mathematics Bogomolny, Alexander: Interactive Mathematics Miscellany and Puzzles. ...
A diagram of a graph with 6 vertices and 7 edges. ...
This article just presents the basic definitions. ...
## 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 This article just presents the basic definitions. ...
This article just presents the basic definitions. ...
- 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. In mathematics and computer science, graph theory studies the properties of graphs. ...
In mathematics, a metric space is a set where a notion of distance between elements of the set is defined. ...
In mathematics, a distance matrix is a matrix (two-dimensional array) containing the distances, taken pairwise, of a set of points. ...
### Eccentricity The **eccentricity** of a vertex *v* is ### Diameter The **diameter** of the graph is defined as ### Peripheral vertex A **peripheral vertex** for *G* is a vertex *v* with - ε(
*v*) = δ(*G*) ### 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*) ## 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. In the mathematical subfield of numerical analysis a sparse matrix is a matrix populated primarily with zeros. ...
In the mathematical subfield of graph theory a level structure of a graph is a special partition of the set of vertices. ...
- choose a vertex
*v* in *V* - create a level structure with root
*v* - 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 ## See also |