DiscreteMath`GraphPlotDiscreteMath`GraphPlot provides functions for aesthetic straight-line drawing of graphs. The package also contains a number of functions useful for graph theory applications. The functions are designed to work efficiently for very large graphs. In this package, a graph is represented by its adjacency matrix. Graphs from the Combinatorica package are also supported, as are graphs specified by a rule list. Graph drawing functions. This loads the package. This plots a graph specified by a rule list.
GraphPlot and GraphPlot3D work with disconnected graphs. The individual components are laid out in a visually appealing way.
GraphPlot and GraphPlot3D are designed to work with very large graphs. This plots a graph of 1005 vertices defined by a matrix from a structural engineering application.
GraphPlot and GraphPlot3D accept the following options, as well as options for Graphics and Graphics3D. Options for GraphPlot and GraphPlot3D. This imports a data set and draws the graph in blue, using the spring model method.
Graph drawing functions that return coordinates. This plots a graph.
This gives the coordinates of the vertices in the previous drawing.
Out[11]= |  |
GraphCoordinates and GraphCoordinates3D accept the following options. Options for GraphCoordinates and GraphCoordinates3D. This gives the coordinates using the spring model method.
Out[12]= |  |
The TreePlot function. This plots a binary tree.
TreePlot accepts the following options, as well as options for Graphics. Options for TreePlot. This plots the previous tree but with the root in the center.
Calculating graph distance and diameter. This plots a graph of 37 vertices.
This calculates the pseudo-diameter of the graph. The graph is first converted to an undirected graph, because PseudoDiameter takes an undirected graph as input. The calculation finds that the diameter 6 is achieved between vertices 1 and 25.
Out[18]= |  |
This confirms that the distance between vertices 1 and 25 is indeed 6.
Out[19]= |  |
Finding a maximal matching, a maximal independent vertex set, and a maximal independent edge set. For a matrix of dimension  , the bipartite graph consists of vertex sets  and  , where two vertices  and  are connected if the matrix element  . This shows that, for the following bipartite graph, row 1 is matched to column 2, row 3 is matched to column 2, and row 2 is matched to column 3.
Out[20]= |  |
For an undirected graph, an independent vertex set is a set of vertices such that no two vertices in the set share an edge. A maximal independent vertex set is an independent set such that adding another vertex will make it no longer independent. This shows that for an undirected graph of four vertices linked in a square, a maximal independent vertex set consists of two vertices at diagonally opposite corners.
Out[21]= |  |
A maximal independent edge set of this graph has two edges opposite one another.
Out[22]= |  |
Finding strongly connected components. A strongly connected component in a directed graph is a set of vertices such that there is a path between any two vertices in the set. This shows that in a directed graph of three nodes ordered in a circular fashion, the strongly connected component contains all the vertices.
Out[23]= |  |
Finding a mincut. This shows a graph of 6 vertices.
This shows the best partitioning of the graph into two parts. This partitioning only cuts through one edge, between vertices 2 and 4.
Out[25]= |  |
Getting a list of all vertices. This function is particularly useful for graphs specified using a rule list. This specifies a graph using a rule list. This gives the list of vertices.
Out[28]= |  |
For further information, see the Advanced Documentation for GraphPlot.
| 
