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, Counting sets, Generating functions, Matching, Hall's Marriage Theorem, Polya counting, Counting paths in graphs. |
| Course description |
Graphs (including bipartite, Euler, Hamiltonian, Planar), Euler's V-E+F=2 Theorem, classification of Platonic solids, subdivisions, Kuratowski's Theorem.
Counting sets, subsets, multisets, inclusion/exclusion, applications.
Stirling numbers of first and second kinds, Bell numbers.
Generating functions, binomial identities.
Matching, Hall's Marriage Theorem, assignment problems.
Polya counting.
Counting paths in graphs.
|
Information for Visiting Students
| Pre-requisites | None |
| High Demand Course? |
Yes |
Course Delivery Information
|
| Academic year 2018/19, 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) | MATH10072 Combinatorics & Graph Theory | 2:00 | |
Learning Outcomes
On completion of this course, the student will be able to:
- Solve counting problems.
- Understand the elements of Graph Theory.
|
Reading List
Reference books which contain some material relevant to the course:
* Discrete Mathematics with Applications, by H. F. Mattson, Jr.
* Discrete Mathematics and Its Applications, by K. H. Rosen
* Discrete Algorithmic Mathematics, by S B Maurer and A Ralston
* Discrete Mathematics with Applications, by Susanna S Epp
Each of these books has a chapter on Counting and a chapter on Graph Theory. A book containing some of the basic material on graphs is :
* Graphs An Introductory Approach, by R J Wilson and J J Watkins
Hall's Marriage Theorem is discussed in
* Introduction to Graph Theory, by R J Wilson |
Additional Information
| Graduate Attributes and Skills |
Not entered |
| Study Abroad |
Not Applicable. |
| Keywords | CGT |
Contacts
| Course organiser | Dr Harry Braden
Tel: (0131 6)50 5072
Email: Harry.Braden@ed.ac.uk |
Course secretary | Miss Sarah McDonald
Tel: (0131 6)50 5043
Email: sarah.a.mcdonald@ed.ac.uk |
|
|
University Homepage