Mathematica 9 is now available
THIS IS DOCUMENTATION FOR AN OBSOLETE PRODUCT.
SEE THE DOCUMENTATION CENTER FOR THE LATEST INFORMATION.
Wolfram Mathematica Documentation Center
DOCUMENTATION CENTER SEARCH
New to Mathematica? Find your learning path »
Graph Utilities Package >
GRAPH UTILITIES PACKAGE SYMBOLTutorials »|See Also »|More About »

PseudoDiameter

PseudoDiameter[g]
give the pseudo-diameter of the undirected graph g, and the two vertices that achieve this diameter.
MORE INFORMATION
  • A graph geodesic is a shortest path between two vertices of a graph. The graph diameter is the longest possible length of all graph geodesics of the graph. finds an approximate graph diameter. It works by starting from a vertex u, and finds a vertex v that is farthest away from u. This process is repeated by treating v as the new starting vertex, and ends when the graph distance no longer increases. A vertex from the last level set that has the smallest degree is chosen as the final starting vertex u, and a traversal is done to see if the graph distance can be increased. This graph distance is taken to be the pseudo-diameter.
  • If the graph is disconnected, then the diameter and vertices for each connected component are returned.
  • The following option can be given:
AggressiveFalsewhether to make extra effort in finding the optimal graph diameter
EXAMPLESCLOSE ALL
Basic Examples   (2)
The pseudo-diameter of the graph of a square is 2:
A plot showing the graph with the two vertices of the pseudo-diameter highlighted in red:
Here is a matrix representation of the graph of a torus:
The pseudo-diameter of this torus is 7:
This finds the graph geodesic between vertices 1 and 26, highlighting the graph geodesic in red:
Needs["GraphUtilities`"]
The pseudo-diameter of the graph of a square is 2:
In[2]:=
Click for copyable input
In[3]:=
Click for copyable input
Out[3]=
A plot showing the graph with the two vertices of the pseudo-diameter highlighted in red:
In[4]:=
Click for copyable input
Out[4]=
 
Needs["GraphUtilities`"]
Here is a matrix representation of the graph of a torus:
In[2]:=
Click for copyable input
The pseudo-diameter of this torus is 7:
In[3]:=
Click for copyable input
Out[3]=
This finds the graph geodesic between vertices 1 and 26, highlighting the graph geodesic in red:
In[4]:=
Click for copyable input
In[5]:=
Click for copyable input
Out[5]=
Scope   (1)
A graph with disconnected components:
returns a list with pseudo-diameters and vertices for each component:
Possible Issues   (1)
This shows a small directed graph:
This finds the pseudo-diameter of the directed graph:
GraphDistance and GraphPath find that there is no path from 4 to 1 in the directed graph:
This turns into an undirected graph:
GraphDistance and GraphPath now find a path of length 2:
Ask a question about this page  |  Suggest an improvement  |  Leave a message for the team
Format:   HTML  |  CDF