• Join over 1.2 million students every month
• Accelerate your learning by 29%
• Unlimited access from just £6.99 per month

# Graph Theory review notes.

Extracts from this document...

Introduction

Graph theory review

Graph types

Simple: no loops or multiple edges

Complete: has every pair of vertices adjacent. One move can get you from one vertex to any other vertex. (n vertices--->Kn)

Connected: has every vertex accessible from every other vertex, but not necessarily directly.

Bipartite: has vertices in two sets and each edge joins one vertex from each set. Vertices within each set are not joined.

Complete Bipartite: has every vertex in one set joined to every other vertex in the other set (m vertices in one set, n vertices in the other--->Km,n)

Wheel: has every vertex connected to a central hub. (Wn)

Two graphs are isomorphic:

Equal size + Equal order + Same Degrees + Connectivity is preserved

The complement of a graph

Middle

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:

1. Select an edge with the smallest weight.

Conclusion

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.

1. Find the shortest route between the 2 odd vertices.
2.  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:

1. Select any vertex, X, and find the sum of the 2 smallest weights that touch X.
2. Remove vertex X, with its edges, from the graph and find the minimum spanning tree for this new network.
3. 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.

This student written piece of work is one of many that can be found in our International Baccalaureate Maths section.

## Found what you're looking for?

• Start learning 29% faster today
• 150,000+ documents available
• Just £6.99 a month

Not the one? Search for your essay title...
• Join over 1.2 million students every month
• Accelerate your learning by 29%
• Unlimited access from just £6.99 per month • Over 160,000 pieces
of student written work
• Annotated by
experienced teachers
• Ideas and feedback to 