Undergraduate Course: Combinatorics and Graph Theory (MATH10072)
Course Outline
| School | School of Mathematics |
College | College of Science and Engineering |
| Course type | Standard |
Availability | Available to all students |
| Credit level (Normal year taken) | SCQF Level 10 (Year 3 Undergraduate) |
Credits | 10 |
| Home subject area | Mathematics |
Other subject area | None |
| Course website |
None |
Taught in Gaelic? | No |
| Course description | 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. |
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) |
| Additional Costs | None |
Information for Visiting Students
| Pre-requisites | None |
| Displayed in Visiting Students Prospectus? | No |
Course Delivery Information
|
| Delivery period: 2013/14 Semester 1, Available to all students (SV1)
|
Learn enabled: Yes |
Quota: None |
Web Timetable |
Web Timetable |
| Course Start Date |
17/09/2013 |
| Breakdown of 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 )
|
| Additional Notes |
|
| Breakdown of Assessment Methods (Further Info) |
Written Exam
95 %,
Coursework
5 %,
Practical Exam
0 %
|
| Exam Information |
| Exam Diet |
Paper Name |
Hours:Minutes |
|
|
| Main Exam Diet S2 (April/May) | MATH10072 Combinatorics and Graph Theory | 2:00 | | | | Main Exam Diet S1 (December) | Combinatorics and Graph Theory (Visiting Students Semester 1 only) | 2:00 | | |
Summary of Intended Learning Outcomes
1. Ability to solve counting problems
2. Understanding the elements of Graph Theory. |
Assessment Information
| See 'Breakdown of Assessment Methods' and 'Additional Notes' above. |
Special Arrangements
| None |
Additional Information
| Academic description |
Not entered |
| Syllabus |
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. |
| Transferable skills |
Not entered |
| 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 |
| Study Abroad |
Not Applicable. |
| Study Pattern |
See 'Breakdown of Learning and Teaching activities' above. |
| 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 2013 The University of Edinburgh - 10 October 2013 4:52 am
|
University Homepage