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.
|
Entry Requirements (not applicable to Visiting Students)
| Pre-requisites |
Students MUST have passed:
Fundamentals of Pure Mathematics (MATH08064)
|
Co-requisites | |
| Prohibited Combinations | |
Other requirements | Must not have taken :
MATH08010 Discrete Mathematics (Year 2) or MATH09001 Discrete Mathematics (Year 3) |
Information for Visiting Students
| Pre-requisites | None |
Course Delivery Information
|
| Academic year 2014/15, Available to all students (SV1)
|
Quota: None |
| Course Start |
Semester 2 |
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
95 %,
Coursework
5 %,
Practical Exam
0 %
|
| Additional Information (Assessment) |
Coursework 5%, Examination 95% |
| Feedback |
Not entered |
| Exam Information |
| Exam Diet |
Paper Name |
Hours & Minutes |
|
| Main Exam Diet S2 (April/May) | Combinatorics and Graph Theory (MATH10072) | 2:00 | |
Learning Outcomes
1. Ability to solve counting problems
2. Understanding 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 Aram Karakhanyan
Tel: (0131 6)50 5056
Email: aram.karakhanyan@ed.ac.uk |
Course secretary | Mrs Kathryn Mcphail
Tel: (0131 6)50 4885
Email: k.mcphail@ed.ac.uk |
|
© Copyright 2014 The University of Edinburgh - 12 January 2015 4:21 am
|
University Homepage