MAS341 Graph Theory
Note: This is an old module occurrence.
You may wish to visit the module list for information on current teaching.
|Semester 2, 2017/18||10 Credits|
|Lecturer:||Dr Paul Johnson||Home page||Timetable||Reading List|
|Aims||Outcomes||Teaching Methods||Assessment||Full Syllabus|
A "graph" is a simple mathematical structure consisting of a collection of points, some pairs of which are joined by lines. Their basic nature means that they can be used to illustrate a wide range of situations. The aim of this course is to investigate the mathematics of these structures and to use them in a wide range of applications. Topics covered include trees, Eulerian and Hamiltonian graphs, planar graphs, embedding of graphs in surfaces, and graph colouring.
Prerequisites: MAS211 (Advanced Calculus and Linear Algebra)
No other modules have this module as a prerequisite.
- Definition and examples
- Eulerian graphs
- Hamiltonian graphs
- The Travelling Salesman Problem
- The Shortest and Longest Path Algorithms
- Planar graphs
- Embedding graphs in surfaces
- Vertex colouring
- Edge colouring
- Face colouring
- To expound the theory of graphs with brief consideration of some algorithms
- Draw standard graphs
- Know when a connected graph is a tree and how trees arise in applications
- Prove Euler's result on Eulerian graphs and apply Fleury's algorithm
- Prove Ore's result on Hamiltonian graphs and be able to find good upper and lower bounds to a Travelling Salesman problem
- Apply the Shortest and Longest Paths Algorithms and handle an Activity Network
- Show that a graph is not planar by finding a subgraph which is a subdivision of K3,3 or K5
- Apply the Planarity Algorithm
- State and prove Euler's Formula and use it
- Embed given graphs in a Möbius band or on a torus
- Calculate the chromatic number and chromatic index of a given graph
- Prove the Five Colour Theorem
- Calculate the chromatic polynomial of a graph using the algorithm
Lectures, problem solving
20 lectures, no tutorials
One formal 2.5 hour written examination. All questions compulsory.
1. Definitions and examples
A connected graph with v vertices has at least v−1 edges and is a tree if and only if it has exactly v−1 edges; spanning trees; fundamental systems of circuits; Kruskal's Algorithm; aliphatic compounds in chemistry; bracings; electrical networks. 3. Eulerian graphs
The edges of a graph can be partitioned into disjoint circuits if and only if every vertex has even degree; a connected graph is Eulerian/semi-Eulerian if and only if every vertex has even degree/it has exactly two vertices of odd degree; Fleury's Algorithm; the Chinese Postman Problem. 4. Hamiltonian graphs
Ore's Theorem and Dirac's Theorem; the Travelling Salesman Problem. 5. The Shortest/Longest Path Algorithm
Activity Networks. 6. Planar graphs
K3,3 and K5 are not planar; Kuratowski's Theorem (statement only); the Planarity Algorithm for Hamiltonian graphs; Euler's Formula for a plane, connected graph. 7. Embedding graphs in surfaces (survey)
The torus, Möbius strip and Klein bottle; genus; generalization of Euler's formula. 8. Vertex- and face- colouring
The chromatic number; a simple graph is bipartite if and only if every circuit is of even length; a simple graph with maximum vertex-degree ∆ is (∆+ 1)-vertex-colourable; Brooks' Theorem (statement); proof of the five-colour Theorem; Heawood's Formula and the Ringel-Youngs Theorem (statement); the chromatic polynomial. 9. Edge-colouring
The chromatic index; χ′(Kn); Vizing's Theorem; χ′(G)=∆(G) for every bipartite G; relationship between edge- and face- colouring for 3-regular planar graphs.
|B||Bryant||Aspects of combinatorics||519.21 (B)||Blackwells||Amazon|
|B||Wilson||Introduction to graph theory||513.83 (W)||Blackwells||Amazon|
|C||Wilson||Four colours suffice||513.83 (W)||Blackwells||Amazon|
(A = essential, B = recommended, C = background.)
Most books on reading lists should also be available from the Blackwells shop at Jessop West.
|Fri||09:00 - 09:50||lecture||Hicks Lecture Theatre 7|
|Fri||16:00 - 16:50||lecture||Hicks Lecture Theatre 1|