THE UNIVERSITY of EDINBURGH

DEGREE REGULATIONS & PROGRAMMES OF STUDY 2015/2016

University Homepage
DRPS Homepage
DRPS Search
DRPS Contact
DRPS : Course Catalogue : School of Mathematics : Mathematics

Undergraduate Course: Combinatorics and Graph Theory (MATH10072)

Course Outline
SchoolSchool of Mathematics CollegeCollege of Science and Engineering
Credit level (Normal year taken)SCQF Level 10 (Year 3 Undergraduate) AvailabilityAvailable to all students
SCQF Credits10 ECTS Credits5
SummaryA 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-requisitesNone
High Demand Course? Yes
Course Delivery Information
Academic year 2015/16, 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.
KeywordsCGT
Contacts
Course organiserDr Aram Karakhanyan
Tel: (0131 6)50 5056
Email: aram.karakhanyan@ed.ac.uk
Course secretaryMr Thomas Robinson
Tel: (0131 6)50 4885
Email: Thomas.Robinson@ed.ac.uk
Navigation
Help & Information
Home
Introduction
Glossary
Search DPTs and Courses
Regulations
Regulations
Degree Programmes
Introduction
Browse DPTs
Courses
Introduction
Humanities and Social Science
Science and Engineering
Medicine and Veterinary Medicine
Other Information
Combined Course Timetable
Prospectuses
Important Information
 
© Copyright 2015 The University of Edinburgh - 18 January 2016 4:24 am