Please enable JavaScript.
Coggle requires JavaScript to display documents.
Graph Theory - Coggle Diagram
Graph Theory
Terminology
path
walk with no edge / vertex repeated
circuit
trail - starts and end at same vertex
trail
a walk with no edge is repeated
cycle
circuit - no vertex repeated except start and end point
walk
Sequence of vertices - each successive pair of vertices is adjacent
tree
connected simple graph with no cycle
loop
An edge from a vertex to itself
degree
In degree
no. of edges coming into vertex
Out degree
no. of edges coming out from vertex
Euler (Chinese Postman Problem)
Eulerian Graph
Even degrees
contains an Eulerian circuit
Semi-Eulerian
exactly two vertices of odd degree
1) pairing the odd vertices
2) Choose the pairing with least weight
3) The chosen edges is the edges that will be traverses twice.
Eulerian circuit
a circuit that traverses each edges exactly once
Eulerian trail
traverses each edge exactly once, but does not start and end at same vertex
Hamiltonian
Semi-hamiltonian
path
visits each vertex once but not start and end at same vertex
Hamiltonian
cycle
visits each vertex exactly once except start and end point
Travelling Salesman Problem
Classical
Lower Bound
Deleted Vertex Algorithm
1) choose a vertex
2) Delete the vertex and all edges connected to it
3) Find min spanning tree from remaining graph
4) add weight of spanning tree together with length of two shortest deleted edges
Upper Bound
Nearest Neighbour Algorithm
1) Choose starting vertex
2) Follow edge of least weight to unvisited vertex
3) Repeat step 2 until all vertices are visited
4) Return to starting vertex
Properties
Closed
Hamiltonian Cycle
Complete Graph
Start and end at same vertex
Practical
converts to classical
table of least distance
Transition matrix
movement opposite to adjacency matrix
from column to row
steady state probability
indicate proportion on time that would be spent at each vertex (for a long period random walk)
Adjacency matrix with power of large number
Spanning Tree
subgraph which is a tree and contains all the vertices
Prim Algorithm
Vertex
1) Start with any vertex
2) Join this vertex with nearest vertex
3) Join the vertex which is nearest to either of those already connected
4) Continue joining connected vertices to the nearest unconnected vertex until all vertices are connected
Adjacency Table
1) Select any vertex at random
2) Delete the row of the chosen vertex
3) Number the column of the chosen vertex
4) Circle the lowest undeleted entry in any numbered columns. The row of circled entry gives us the new chosen vertex
5) Repeat steps 2 to 4 until all rows are deleted. the circled entries is the edges of min spanning tree
Kruskal Algorithm
2) Choose the shortest edge remaining that
does not
complete a cycle
3) Repeat step 2 until n-1 edges have been chosen
1) Start with the least weighted edges