|
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. ...
- dG(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 - dG(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 | 
Feeds |
Contact