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={"\"\[UndirectedEdge]"\","\"\[UndirectedEdge]"\","\"\[UndirectedEdge]"\","\"\[UndirectedEdge]"\","\"\[UndirectedEdge]"\","\"\[UndirectedEdge]"\","\"\[UndirectedEdge]"\","\"\[UndirectedEdge]"\","\"\[UndirectedEdge]"\","\"\[UndirectedEdge]"\","\"\[UndirectedEdge]"\","\"\[UndirectedEdge]"\","\"\[UndirectedEdge]"\"};
FindHamiltonianCycle[g,All]
GraphPlot[g,VertexLabeling->True]
FindHamiltonianCycle[g]
HighlightGraph[g,PathGraph[First[%]]]

Clear[g]
g={"A"\[UndirectedEdge]"B","A"\[UndirectedEdge]"D","B"\[UndirectedEdge]"C","B"\[UndirectedEdge]"E","D"\[UndirectedEdge]"G","D"\[UndirectedEdge]"E","E"\[UndirectedEdge]"G","E"\[UndirectedEdge]"H","E"\[UndirectedEdge]"F","C"\[UndirectedEdge]"F","H"\[UndirectedEdge]"I","F"\[UndirectedEdge]"I","G"\[UndirectedEdge]"H"};
FindHamiltonianCycle[g,All]
GraphPlot[g,VertexLabeling->True]
FindHamiltonianCycle[g]
HighlightGraph[g,PathGraph[First[%]]]

2. Find all Hamiltonian Path

Clear[g]
g={"\"\[UndirectedEdge]"\","\"\[UndirectedEdge]"\","\"\[UndirectedEdge]"\","\"\[UndirectedEdge]"\","\"\[UndirectedEdge]"\","\"\[UndirectedEdge]"\","\"\[UndirectedEdge]"\","\"\[UndirectedEdge]"\","\"\[UndirectedEdge]"\","\"\[UndirectedEdge]"\","\"\[UndirectedEdge]"\","\"\[UndirectedEdge]"\","\"\[UndirectedEdge]"\"};
FindHamiltonianPath[g,"\","\"]
GraphPlot[g,VertexLabeling->True]
FindHamiltonianPath[g,"\","\"]
HighlightGraph[g,PathGraph[FindHamiltonianPath[g,"\","\"]]]

List Hamiltonian path from vertex C to G

Clear[g]
g={"A"\[UndirectedEdge]"B","A"\[UndirectedEdge]"D","B"\[UndirectedEdge]"C","B"\[UndirectedEdge]"E","D"\[UndirectedEdge]"G","D"\[UndirectedEdge]"E","E"\[UndirectedEdge]"G","E"\[UndirectedEdge]"H","E"\[UndirectedEdge]"F","C"\[UndirectedEdge]"F","H"\[UndirectedEdge]"I","F"\[UndirectedEdge]"I","G"\[UndirectedEdge]"H"};
FindHamiltonianPath[g,"C","G"]
GraphPlot[g,VertexLabeling->True]
FindHamiltonianPath[g,"C","G"]
HighlightGraph[g,PathGraph[FindHamiltonianPath[g,"C","G"]]]

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,16},{1,5,17},{1,7,10},{2,3,24},{2,5,16},{5,4,17},{5,6,11},{5,7,12},{7,6,17},{6,4,15},{3,4,16}};
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 Maximum Flow: Ford-Fulkerson Algorithm Not working

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;
adjM[i_,j_]:=0/;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;
adjM[i_,j_]:=0/;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"]
FindMaximumFlow[g,3,7]
HighlightGraph[g,%,GraphHighlightStyle->"Thick"]

5. 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=10;
weightedEdges={{1,2,17},{1,3,18},{1,4,15},{2,7,27},{2,5,18},{3,5,15},{3,6,10},{4,6,14},{4,10,29},{5,7,6},{5,9,12},{5,6,4},{6,9,17},{6,10,13},{7,8,15},{9,8,11},{9,10,3},{10,8,13}};
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,1,8]
HighlightGraph[g,PathGraph[FindShortestPath[g,1,8]]]

6. 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

7. 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}]