MASTERSHEET
Copy/Paste Formulae for Module 2 Networks

>Copy the formula you need
>Paste it into the other workbook you are using
>NOTE: Do NOT alter the formulae in this workbook, these are your templates only.

MATHEMATICA COMMANDS FOR Module 2 Networks

1. Find all Hamiltonian Cycles

Clear[g]
g={"Enter all edges with comma, in between; using \!\(\*StyleBox[\"Esc\",FontColor->RGBColor[1, 0, 0]]\)\!\(\*StyleBox[\" \",FontColor->RGBColor[1, 0, 0]]\)\!\(\*StyleBox[\"u\",FontColor->RGBColor[1, 0, 0]]\)\!\(\*StyleBox[\" \",FontColor->RGBColor[1, 0, 0]]\)\!\(\*StyleBox[\"e\",FontColor->RGBColor[1, 0, 0]]\)\!\(\*StyleBox[\" \",FontColor->RGBColor[1, 0, 0]]\)\!\(\*StyleBox[\"Esc\",FontColor->RGBColor[1, 0, 0]]\) buttons for edge input"};
FindHamiltonianCycle[g,All]
GraphPlot[g,VertexLabeling->True]
FindHamiltonianCycle[g]
HighlightGraph[g,PathGraph[First[%]]]

Clear[g]
g={1\[UndirectedEdge]2,2\[UndirectedEdge]3,3\[UndirectedEdge]6,6\[UndirectedEdge]9,9\[UndirectedEdge]8,8\[UndirectedEdge]5,8\[UndirectedEdge]7,6\[UndirectedEdge]5,4\[UndirectedEdge]5,1\[UndirectedEdge]4,2\[UndirectedEdge]5,4\[UndirectedEdge]7,7\[UndirectedEdge]5};
FindHamiltonianCycle[g,All]
GraphPlot[g,VertexLabeling->True]
FindHamiltonianCycle[g]
HighlightGraph[g,PathGraph[First[%]]]

2. Find all Hamiltonian Path

Clear[g]
g={"Enter all edges with comma, in between; using \!\(\*StyleBox[\"Esc\",FontColor->RGBColor[1, 0, 0]]\)\!\(\*StyleBox[\" \",FontColor->RGBColor[1, 0, 0]]\)\!\(\*StyleBox[\"u\",FontColor->RGBColor[1, 0, 0]]\)\!\(\*StyleBox[\" \",FontColor->RGBColor[1, 0, 0]]\)\!\(\*StyleBox[\"e\",FontColor->RGBColor[1, 0, 0]]\)\!\(\*StyleBox[\" \",FontColor->RGBColor[1, 0, 0]]\)\!\(\*StyleBox[\"Esc\",FontColor->RGBColor[1, 0, 0]]\) buttons for edge input"};
FindHamiltonianPath[g,"Starting Vertex in number","Finishing Vertex in number"]
GraphPlot[g,VertexLabeling->True]
FindHamiltonianPath[g,"Starting Vertex in number","Finishing Vertex in number"]
HighlightGraph[g,PathGraph[FindHamiltonianPath[g,"Starting Vertex in number","Finishing Vertex in number"]]]

List Hamiltonian path from vertex C to G

Clear[g]
g={1\[UndirectedEdge]2,2\[UndirectedEdge]3,3\[UndirectedEdge]6,6\[UndirectedEdge]9,9\[UndirectedEdge]8,8\[UndirectedEdge]5,8\[UndirectedEdge]7,6\[UndirectedEdge]5,4\[UndirectedEdge]5,1\[UndirectedEdge]4,2\[UndirectedEdge]5,4\[UndirectedEdge]7,7\[UndirectedEdge]5};
FindHamiltonianPath[g,3,7]
GraphPlot[g,VertexLabeling->True]
FindHamiltonianPath[g,3,7]
HighlightGraph[g,PathGraph[FindHamiltonianPath[g,3,7]]]

3. Minimal Spanning Tree: Prim’s Algorithm, Kruskal’s Algorithm

n="Number of vertices";
weightedEdges={{"two vertices number with weight of this edge, comma in between"},{"two vertices number with weight of this edge, comma in between"},{"two vertices number with weight of this edge, comma in between"},{"two vertices number with weight of this edge, comma in between"},{"two vertices number with weight of this edge, comma in between"},{"two vertices number with weight of this edge, comma in between"},{"two vertices number with weight of this edge, comma in between"},{"two vertices number with weight of this edge, comma in between"},{"two vertices number with weight of this edge, comma in between"},{"two vertices number with weight of this edge, comma in between"},{"two vertices number with weight of this edge, comma in between"},{"two vertices number with weight of this edge, comma in between"},{"two vertices number with weight of this edge, comma in between"},{"two vertices number with weight of this edge, comma in between"}};
Clear[adjM];
adjM[i_,j_]:=∞;
adjM[i_,j_]:=adjM[j,i]/;i>j;
weightedEdges/.{i_,j_,k_}:>(adjM[i,j]=k);
Array[adjM,{n,n}]//MatrixForm
Clear[g]
g=WeightedAdjacencyGraph[Array[adjM,{n,n}],VertexLabels->"Name",EdgeLabels->"EdgeWeight"]
FindSpanningTree[g]
HighlightGraph[g,%,GraphHighlightStyle->"Thick"]

n=7;
weightedEdges={{1,2,5},{1,3,2},{1,5,7},{2,3,1},{2,4,5},{3,4,8},{3,5,10},{4,5,2},{4,6,10},{5,6,2},{2,6,6},{1,4,12},{6,7,5},{5,7,20}};
Clear[adjM];
adjM[i_,j_]:=∞;
adjM[i_,j_]:=adjM[j,i]/;i>j;
weightedEdges/.{i_,j_,k_}:>(adjM[i,j]=k);
Array[adjM,{n,n}]//MatrixForm
Clear[g]
g=WeightedAdjacencyGraph[Array[adjM,{n,n}],VertexLabels->"Name",EdgeLabels->"EdgeWeight"]
FindSpanningTree[g]
HighlightGraph[g,%,GraphHighlightStyle->"Thick"]

4. The Shortest Path: Dijkstra’s Algorithm

n="Number of vertices";
weightedEdges={{"two vertices number with weight of this edge, comma in between"},{"two vertices number with weight of this edge, comma in between"},{"two vertices number with weight of this edge, comma in between"},{"two vertices number with weight of this edge, comma in between"},{"two vertices number with weight of this edge, comma in between"},{"two vertices number with weight of this edge, comma in between"},{"two vertices number with weight of this edge, comma in between"},{"two vertices number with weight of this edge, comma in between"},{"two vertices number with weight of this edge, comma in between"},{"two vertices number with weight of this edge, comma in between"},{"two vertices number with weight of this edge, comma in between"},{"two vertices number with weight of this edge, comma in between"},{"two vertices number with weight of this edge, comma in between"},{"two vertices number with weight of this edge, comma in between"}};
Clear[adjM];
adjM[i_,j_]:=∞;
adjM[i_,j_]:=adjM[j,i]/;i>j;
weightedEdges/.{i_,j_,k_}:>(adjM[i,j]=k);
Array[adjM,{n,n}]//MatrixForm
Clear[g]
g=WeightedAdjacencyGraph[Array[adjM,{n,n}],VertexLabels->"Name",EdgeLabels->"EdgeWeight"]
FindShortestPath[g,"Starting Vertex in number","Finishing Vertex in number"]
HighlightGraph[g,PathGraph[FindShortestPath[g,"Starting Vertex in number","Finishing Vertex in number"]]]

n=7;
weightedEdges={{1,2,5},{1,3,2},{1,5,7},{2,3,1},{2,4,5},{3,4,8},{3,5,10},{4,5,2},{4,6,10},{5,6,2},{2,6,6},{1,4,12},{6,7,5},{5,7,20}};
Clear[adjM];
adjM[i_,j_]:=∞;
adjM[i_,j_]:=adjM[j,i]/;i>j;
weightedEdges/.{i_,j_,k_}:>(adjM[i,j]=k);
Array[adjM,{n,n}]//MatrixForm
Clear[g]
g=WeightedAdjacencyGraph[Array[adjM,{n,n}],VertexLabels->"Name",EdgeLabels->"EdgeWeight"]
FindShortestPath[g,3,7]
HighlightGraph[g,PathGraph[FindShortestPath[g,3,7]]]

5. Matching & Allocation Problems: Hungarian Algorithm

Needs["Combinatorica`"]
g=Combinatorica`CompleteGraph["row number","column number"];
edgeWeights={{"Number on 1st column with comma, in between"},{"Number on 2nd column with comma, in between"},{"Number on 3rd column with comma, in between"},{"Number on 4th column with comma, in between"},{"Number on 5th column with comma, in between"}};
g1=Combinatorica`SetEdgeWeights[g,-Flatten[edgeWeights]];
Combinatorica`BipartiteMatchingAndCover[g1]
Extract[edgeWeights,First[%]/.x_/;x>"row number":>x-"row number"]
Total[%]

Needs["Combinatorica`"]
g=Combinatorica`CompleteGraph[4,4];
edgeWeights={{110,105,125,115},{95,82,78,90},{140,145,140,135},{80,80,75,85}};
g1=Combinatorica`SetEdgeWeights[g,-Flatten[edgeWeights]];
Combinatorica`BipartiteMatchingAndCover[g1]
Extract[edgeWeights,First[%]/.x_/;x>4:>x-4]
Total[%]

Answers Explain :           {1,6},{2,7},{3,8},{4,5} -->A-X, B-Y, C-Z, D-W                 398=Total Cost

6. Visualize Hamiltonian Cycles

a. Listing how many cycles from vertex 13 to vertex 17

g=PolyhedronData["Dodecahedron","Skeleton"];
hc=FindHamiltonianCycle[g,All];
{s,t}={13,17};
hps2t=Select[hc,MemberQ[(s|t)\[UndirectedEdge](s|t)]];
GraphicsGrid[Partition[Table[HighlightGraph[g,DeleteCases[p,(s|t)\[UndirectedEdge](s|t)],GraphHighlightStyle->"Thick"],{p,hps2t}],5]]

b. how one cycle traveling

dodecahedron=PolyhedronData["Dodecahedron","Skeleton"];
hcycle=First[FindHamiltonianCycle[dodecahedron]]
Animate[HighlightGraph[dodecahedron,PathGraph[hcycle[[1;;n]]],GraphHighlightStyle->"Thick"],{n,0,Length[hcycle],1}]