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: 2014/15 Semester 2, Available to all students (SV1)
|
Learn enabled: Yes |
Quota: None |
|
Web Timetable |
Web Timetable |
| Course Start Date |
12/01/2015 |
| 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 %
|
| No Exam Information |
Summary of Intended Learning Outcomes
1. Ability to solve counting problems
2. Understanding the elements of Graph Theory. |
Assessment Information
| Coursework 5%, Examination 95% |
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 2014 The University of Edinburgh - 29 August 2014 4:20 am
|
University Homepage