Section 5.1

To draw a graph in Mathematica, make a list of the edges you want to include, using arrows to indicate which vertices are connected.  If you want directed edges, change the code to DirectedEdges->True.  You get the arrow by typing a dash - then a > symbol.

Graph[{1->1, 2->1, 3->2, 2->3, 4->1, 2->4}, DirectedEdges->False]

If you want labels, you can add them.  If you set the labels to Automatic, you get, well, automatically generated labels.  This isn’t a bad idea if you only want the vertices labelled.

Graph[{1->1, 2->1, 3->2, 2->3, 4->1, 2->4},  VertexLabels->Automatic, EdgeLabels->Automatic, DirectedEdges->True]

You can also use letters to signify vertices.

samplegraph=Graph[{A->B, B->C, C->A,D->A, B->D,C->B},  VertexLabels->Automatic, EdgeLabels->Automatic, DirectedEdges->True]

Of course, custom labels look nicer!

Graph[{1->1, 2->1, 3->2, 2->3, 4->1, 2->4},  VertexLabels->{(1->(Subscript[v, 1])), (2->(Subscript[v, 2])), (3->(Subscript[v, 3])), (4->(Subscript[v, 4]))}, EdgeLabels->{(1->1)->(Subscript[e, 1]), (2->1)->(Subscript[e, 2]), (3->2)->(Subscript[e, 3]), (2->3)->(Subscript[e, 4]), (4->1)->(Subscript[e, 5]), (2->4)->(Subscript[e, 6])}, DirectedEdges->True]

The GraphPlot command can be used as well, but it draws graphs in a slightly different style.  You have seen me use these before.  Vertices can be labelled or unlabelled.

samplegraph2=GraphPlot[{1->1, 2->1, 3->2, 2->3, 4->1, 2->4}]

GraphPlot[{1->1, 2->1, 3->2, 2->3, 4->1, 2->4}, VertexLabeling->True]

Complete graphs are easy to make...

CompleteGraph[5]

... as are complete bipartite graphs.

CompleteGraph[{2,3}]

Some really important graphs have their own commands!

PetersenGraph[]

Do you want to see a graph with a specific degree sequence?  You can do that!  Keep hitting enter below and you’ll see different graphs with the same degree sequence.

RandomGraph[DegreeGraphDistribution[{4,4,4,3,3,2,1,1,1,1}]]

Do you want to know whether or not your favorite graph is bipartite?  Mathematica can answer that question!

BipartiteGraphQ[samplegraph]

BipartiteGraphQ[CompleteGraph[{4,5}]]  (*Of course the complete bipartite graph with 4 vertices in one set and 5 vertices in the other is bipartite!*)

Section 5.2

You can also produce adjacency matrices automatically, but only if you have used the Graph command. Why?  The Graph command creates a list, but the GraphPlot command creates a graphics object.  It’s complicated.  We will discuss these later in the course.

samplegraph3=Graph[{1->1, 6->1, 3->2,4->1, 2->4, 5->1, 5->4, 3->5, 2->1, 3->6, 4->6, 5->6}, DirectedEdges->False, VertexLabels->"Name"]

mat=AdjacencyMatrix[samplegraph3]

VertexList[samplegraph3]

MatrixForm[mat]

m=AdjacencyMatrix[PetersenGraph[]]

MatrixForm[m]

MatrixForm[m.m]

MatrixForm[m.m + m]

MatrixForm[m.m  m]

Notice that in the Adjacency matrix, the vertices are renumbered in the order they appear in your Graph statement.  If you want to keep them in the traditional order, be careful of the order in which you define your edges.  Compare the above to the next couple of cells. All I did was re-order the red entries, and the graph even looks different!

samplegraph4=Graph[{1->1,2->1, 3->2,4->1, 2->4, 5->1, 5->4, 3->5, 6->1, 3->6, 4->6, 5->6}, DirectedEdges->False, VertexLabels->"Name"]

mat2=AdjacencyMatrix[samplegraph4]

VertexList[samplegraph4]

MatrixForm[mat2]

Including the labels in the matrix can help us decipher what the numbers mean.  The command below puts headings on the matrix.

TableForm[mat2,TableHeadings->{VertexList[samplegraph4], VertexList[samplegraph4]}]

To see how many paths of length 7 exist from vertex 2 to vertex 5, we raise the adjacency matrix to the 7th power and check out the corresponding entry in the resulting matrix.

MatrixPower[mat2,7] //MatrixForm

The heading would help here.

TableForm[MatrixPower[mat2,7],TableHeadings->{VertexList[samplegraph4], VertexList[samplegraph4]}]

TableForm[MatrixPower[mat2,1],TableHeadings->{VertexList[samplegraph4], VertexList[samplegraph4]}]

There are 1985 paths of length 7 from vertex 2 to vertex 5!

Here is another example using letters to label the vertices.

samplegraph5=Graph[{"A"->"B","C"->"B","A"->"C","D"->"C"}, DirectedEdges->False, VertexLabels->"Name"]

mat3=AdjacencyMatrix[samplegraph5]

TableForm[MatrixPower[mat3,4],TableHeadings->{VertexList[samplegraph5], VertexList[samplegraph5]}]

samplegraph6=Graph[{"A"->"B","C"->"B","A"->"C","B"->"C", "C"->"C"}, DirectedEdges->False, VertexLabels->"Name"]

mat4=AdjacencyMatrix[samplegraph6]

TableForm[MatrixPower[mat4,1],TableHeadings->{VertexList[samplegraph6], VertexList[samplegraph6]}]

TableForm[MatrixPower[mat4,2],TableHeadings->{VertexList[samplegraph6], VertexList[samplegraph6]}]

Here is a little bit of code to find the diameter of a graph.  Do you see why each part is there?

testmatrix=mat7;
max=1;
diam=0;
While[diam<1,
diam=Min[IdentityMatrix[Length[testmatrix]]+Sum[MatrixPower[testmatrix,i], {i,1,max}]];  max++;
];
Print[max-1]

samplegraph7=Graph[{1->2, 2->3, 3->4, 4->5, 5->6, 6->6, 6->1, 3->7}, DirectedEdges->False]

mat7=AdjacencyMatrix[samplegraph7]

MatrixForm[mat7]