Undergraduate Course: Combinatorics and Graph Theory (MATH10072)
Course Outline
| School | School of Mathematics |
College | College of Science and Engineering |
| Credit level (Normal year taken) | SCQF Level 10 (Year 3 Undergraduate) |
Availability | Available to all students |
| SCQF Credits | 10 |
ECTS Credits | 5 |
| Summary | A first course in combinatorics and graph theory: graphs, Euler's V-E+F=2 theorem, Kuratowski's theorem, colourings of graphs, matching, Hall's marriage theorem, applications |
| Course description |
Typical course contents might include the following: Graphs, digraphs, paths and cycles: Eulerian and Hamiltonian graphs, connectivity, adjacency matrices. Applications: shortest path problem, critical path problem, Guan¿s postman problem, travelling salesman problem.
Trees: properties, counting trees, minimum connector problem and other applications.
Planar graphs, Kuratowski¿s theorem, Euler's V-E+F=2 theorem, dual graphs.
Vertex-colourings, edge-colourings, and face-colourings of graphs, chromatic polynomials, four-colour theorem.
Matching, Hall's marriage theorem, Menger¿s theorem, max-flow min-cut theorem and application to network flow problems.
|
Information for Visiting Students
| Pre-requisites | Equivalence relations, permutations, set theory, group theory, binomial coefficients. Visiting students are advised to check that they have studied the material covered in the syllabus of each prerequisite course before enrolling. |
| High Demand Course? |
Yes |
Course Delivery Information
|
| Academic year 2024/25, Available to all students (SV1)
|
Quota: None |
| Course Start |
Semester 1 |
Timetable |
Timetable |
| Learning and Teaching activities (Further Info) |
Total Hours:
100
(
Lecture Hours 22,
Seminar/Tutorial Hours 5,
Summative Assessment Hours 2,
Programme Level Learning and Teaching Hours 2,
Directed Learning and Independent Learning Hours
69 )
|
| Assessment (Further Info) |
Written Exam
80 %,
Coursework
20 %,
Practical Exam
0 %
|
| Additional Information (Assessment) |
Coursework 20%, Examination 80% |
| Feedback |
Not entered |
| Exam Information |
| Exam Diet |
Paper Name |
Hours & Minutes |
|
| Main Exam Diet S1 (December) | Combinatorics and Graph Theory (MATH10072) | 2:00 | |
Learning Outcomes
On completion of this course, the student will be able to:
- Identify properties of graphs (such as Eulerian/Hamiltonian/Planar/Bipartite/Connectivity/Colourablity).
- Write proofs based on properties of graphs.
- Solve application problems (such as the shortest path problem, critical path problem, Guan¿s postman problem, minimum connector problem, network flow problems).
- Make computations associated to graphs.
|
Reading List
Reference books which contain some material relevant to the course:
* A First Course in Combinatorial Mathematics by Ian Anderson
* Aspects of Combinatorics by Victor Bryant.
* Graphs An Introductory Approach, by R J Wilson and J J Watkins
* Introduction to Graph Theory, by R J Wilson |
Additional Information
| Graduate Attributes and Skills |
Not entered |
| Keywords | CGT |
Contacts
| Course organiser | Dr Ana Rita Pires
Tel: (0131 6)50 5079
Email: apires@ed.ac.uk |
Course secretary | Miss Greta Mazelyte
Tel:
Email: greta.mazelyte@ed.ac.uk |
|
|
University Homepage