Course finder
Semester 1
Combinatorics and Graph Theory (MATH10072)
Subject
Mathematics
College
SCE
Credits
10
Normal Year Taken
3
Delivery Session Year
2023/2024
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.
Course Summary
A first course in combinatorics and graph theory: Graphs, Euler's V-E+F=2 Theorem, Kuratowski's Theorem, Counting sets, Generating functions, Matching, Hall's Marriage Theorem, Polya counting, Counting paths in graphs.
Course Description
Graphs (including bipartite, Euler, Hamiltonian, Planar, trees) , Euler's V-E+F=2 Theorem, subdivisions, Kuratowski's Theorem. Counting sets, subsets, multisets, inclusion/exclusion, applications.Stirling numbers of first and second kinds, Bell numbers, partitions. Generating functions, binomial identities.Matching, Hall's Marriage Theorem, assignment problems.Polya counting.Counting paths in graphs, adjacency matrix.
Assessment Information
Written Exam 80%, Coursework 20%, Practical Exam 0%
Additional Assessment Information
Coursework 20%, Examination 80%
view the timetable and further details for this course
Disclaimer
All course information obtained from this visiting student course finder should be regarded as provisional. We cannot guarantee that places will be available for any particular course. For more information, please see the visiting student disclaimer: