PseudoDiameterCalculating the pseudo-diameter of an undirected graph. For an undirected graph  , PseudoDiameter[g] gives a list containing the pseudo-diameter of the graph and two vertices that achieve this diameter. If the graph is disconnected, the pseudo-diameter for each of the components is returned, along with the two vertices that achieve that diameter. The algorithm used finds an approximate diameter of the graph (hence the term "pseudo"). The algorithm works by starting from a vertex  , and finds a vertex  among all the vertices that are farthest away from  . This process is repeated by treating  as the new starting vertex  . The process stops when the graph distance between  and  no longer increases. This distance is the pseudo-diameter. If the option Aggressive->True is used, when the distance between  and  no longer increases, the algorithm will be carried out for one extra step by starting from each vertex  that is farthest away from  . The pseudo-diameter is the farthest distance possible from all such  . This shows that the graph of a square has a pseudo-diameter of 2, and that vertices 1 and 3 achieve this diameter (i.e., the graph distance between vertices 1 and 3 is 2). In[75]:=  |
In[77]:=  |
Out[77]=
|
The diameter of this graph is also 2. In[78]:=  |
In[81]:=  |
Out[81]=
|
For a disconnected graph, a list of the diameters and the vertices that achieved them is given for each of the components. In the following example, vertex 3 is isolated, so the component that consists solely of this vertex has a diameter of 0. In[82]:=  |
Out[82]=
|
To calculate the pseudo-diameter of a random undirected graph, a function giving random symmetric sparse matrices is needed. In[83]:=  |
This function can be used to determine the average pseudo-diameter of random undirected graphs of 100 vertices with an average degree of 2. The largest pseudo-diameter is chosen if there is more than one component. With Aggressive->True, the pseudo-diameter is slightly larger. In[84]:=  |
Out[87]=
|
This calculates the pseudo-diameter of a two-dimensional torus. In[88]:=  |
In[89]:=  |
Out[90]=
|
This highlights the two vertices that achieve this diameter. In[91]:=  |
| 
