FACTOID # 1: Idaho produces more milk than Iowa, Indiana and Illinois combined.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Distance (graph theory)

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

Contents


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

  1. choose a vertex v in V
  2. create a level structure with root v
  3. choose a vertex u in Lε(v) with minimal degree
  4. if ε(u) > ε(v) then set v=u and repeat with step 2 else u is a pseudo-peripheral vertex

See also


  Results from FactBites:
 
Graph theory - Wikipedia, the free encyclopedia (1884 words)
Enumerative graph theory then rose from the results of Cayley and the fundamental results published by Pólya between 1935 and 1937 and the generalization of these by De Bruijn in 1959.
The introduction of probabilistic methods in graph theory, specially in the study of Erdös and Rényi of the asymptotic probability of graph connexity is at the origin of yet another branch, known as random graph theory.
Graph theory is also used to study molecules in chemistry and physics.
Wikinfo | Graph theory (2257 words)
Graphs with weights can be used to represent many different concepts; for example if the graph represents a road network, the weights could represent the length of each road.The only information a weighted graph provides as such is (a) the vertices, (b) the edges and (c) the weights.
Graph theory is the branch of mathematics that examines the properties of graphs.
Every graph gives rise to a matroid, but in general the graph cannot be recovered from its matroid, so matroids are not truly generalizations of graphs.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m