The complement of a graph will have all of the same vertices but its edges will be all of the possible edges that the original graph does NOT have.
Handshaking Lemma: For any graph G, the sum of degrees of the vertices in G is twice the size of G.
Pigeonhole Principle: n pigeons in m holes, and n>m, then there must be at least one hole containing more than one pigeon.
Planar graph: a graph without any edges crossing each other
For graph, G, to be planar:
If G is a simple graph:
If G is a bipartite graph:
Any subgraph that contains K5 or K3,3 will not be planar
A connected graph has an Eulerian circuit if and only if ALL of its vertices are even.
A connected graph is semi- Eulerian if and only if it has exactly two vertices of odd degree. (roads)
Hamiltonian Graph is a connected graph G that has a cycle which included every vertex. (towns)
The number of different Hamiltonian cycles in a complete undirected graph on n vertices is (n-1)!/2 and in a complete directed graph on n vertices is (n-1)!
Find minimum spanning tree
Practice: 2008 Nov. Paper 3 Question #2
Kruskal’s method:
- Select an edge with the smallest weight.
- Select from the remaining edges, the edge of least weight which does not form a cycle.
- Repeat step 2 until n-1 edges have been chosen
Prim’s method:
- Select any vertex as a starting point.
- Consider the edges that connect to any vertex already chosen and choose the smallest .
- Repeat step 2 until all of the vertices have been chosen.
Prim’s method (matrix): SAME THING!!!
Dijkstra’s method: Find the shortest path from a start point to a finish point.
- Label the starting vertex with a (0,p) where ‘p’ means permanent. Label all other vertices with where ‘t‘ means temporary.
- Choose the least of all temporary labels adjacent to any permanent vertex. Then make it permanent.
- Repeat step 2 until the destination vertex has a permanent label.
Chinese postman (roads)
- Find the shortest route between the 2 odd vertices.
- Add all of the edges and then add the shortest route between the odd vertices (count this twice)
When there are more than 2 odd vertices: pair up odd vertices and find the smallest.
Practice: 2010 May Paper 3 Question #2
Traveling salesman (towns)
Lower bound:
- Select any vertex, X, and find the sum of the 2 smallest weights that touch X.
- Remove vertex X, with its edges, from the graph and find the minimum spanning tree for this new network.
- Add the totals in steps 1 &2.
Upper bound:
Double the weight of the minimum spanning tree.
A better upper bound would be to just head straight back to starting point.
