Undergraduate Course: Combinatorics and Graph Theory (MATH10072)
|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
|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.
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.
Counting paths in graphs, adjacency matrix.
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?
Course Delivery Information
|Academic year 2021/22, Available to all students (SV1)
|Learning and Teaching activities (Further Info)
Lecture Hours 22,
Seminar/Tutorial Hours 5,
Summative Assessment Hours 2,
Programme Level Learning and Teaching Hours 2,
Directed Learning and Independent Learning Hours
|Assessment (Further Info)
|Additional Information (Assessment)
||Coursework 20%, Examination 80%
||Hours & Minutes
|Main Exam Diet S1 (December)||2:00|
On completion of this course, the student will be able to:
- Solve counting problems.
- Identify properties of graphs (such as Eulerian/Hamiltonian/Planar/Bipartite/Connectedness).
- Solve matching problems using Hall's marriage theorem and equivalent bipartite graph formulations.
- Solve counting problems associated to graphs (such as numbers of paths)
|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
|Graduate Attributes and Skills
|Course organiser||Dr David Jordan
Tel: (0131 6)50 7210
|Course secretary||Miss Greta Mazelyte