Graph Theory (MA522)
This is the homepage of MA522 for the academic year 2009-2010. The
page will be regularly updated throughout the first semester.
Any suggestions for
improving it are welcomed by its author, Rachel Quinlan.
Contents
Lecturer
Course Content
Course Activities - what students do
Learning Outcomes
Assessment and Feedback
Weekly Problems to Think About
Recommended Reading
Dr Rachel Quinlan
Office : Room 105, Ground Floor, Áras de Brún
Phone : (49)3796
email : rachel.quinlan@nuigalway.ie
Graphs are mathematical constructions used to describe collections of
objects some pairs of which are related to each other. For example a
family tree is a collection of people in which some are related to
others by parentage. Another example would be an airline's route map
in which services are indicated by lines joining different
airports. Mathematical graphs can be represented as diagrams involving
collections of vertices (dots), some pairs of which are connected by
edges (lines). In this course we will consider the first four topics
from the following list, and some of the last four according to the
preferences of the class.
- Basic concepts of graph theory
- Trees
- Bipartite graphs and matching
- Colouring problems
- Connectivity
- Networks and flows
- Algebraic methods in graph theory
- Planarity
Prerequisites
No particularly advanced knowledge from any other area of mathematics
is needed for the study of graph theory. Some knowledge of linear
algebra, particularly matrix algebra, would be helpful. Otherwise what
is needed is general mathematical experience. This is an advanced
course and students will be expected both to construct and to
critically assess mathematical proofs of moderate complexity, and to
demonstrate proficiency in the communication of mathematical ideas.
There will be three components to the course activities.
-
Study of the course text
The course text is (some of) the book Graph Theory with
Applications, by J.A. Bondy and U.S.R. Murty. This book is freely
available online
here.
Students
are expected to engage in independent study of this text or at least
in certain prescribed sections of it. Consultation of other books on
graph theory is also encouraged.
-
Seminar Series
We will have two weekly seminars. Seminars will be held in C219 at
1.00 on Tuesdays and at 4.00 on Wednesdays. The online dictionary
dictionary.com defines seminar as follows :
``a small group of students, as in a university, engaged in advanced
study and original research with a member of the faculty and meeting
regularly to exchange information and hold discussions.''
Each seminar session will focus on a particular section or sections of the
lecture notes; these should be studied in advance of the seminar.
Topics for seminar discussion will include :
-
key concepts from the text and questions arising;
-
investigation of questions posed for seminar discussion;
-
Occasional presentation by students of key items from the syllabus;
-
Strategies for thinking about graph theory and about mathematics
generally;
-
Proofs in graph theory;
-
Mathematical writing.
-
Working on Assigned Tasks
The course will include at least four sets of assigned tasks. These
tasks will include some very specific problems to solve and also some more
open-ended topics to investigate. They will also include presentations
of specific
topics to the class.
Note on Workload
This module accounts for 9 ECTS credits. One ECTS credit is
considered to equate to 25 to 30 hours of work by a student. This
means that you should expect to spend upwards of 200 hours in total
working on
this Graph
Theory course.
Upon successful completion of this module students will be able to
-
Demonstrate knowledge of the syllabus material;
-
Write precise and accurate mathematical definitions of objects in
graph
theory;
-
Use mathematical definitions to identify and construct examples and to
distinguish examples from non-examples;
-
Validate and critically assess a mathematical proof;
-
Use a combination of theoretical knowledge and independent
mathematical thinking in creative
investigation of questions
in graph theory;
-
Reason from definitions to construct mathematical proofs;
-
Write about graph theory in a coherent and
technically accurate
manner.
Assessment : a combination to be decided of written assignments,
presentations, and participation in seminars. Feedback
will be provided on all submitted work and opportunities to obtain
feedback before final submission will be available.
. . . and discuss in the seminars. Problems that have particular relevance
to the general theory are marked with a dagger. Problems that I think
are hard are marked with a star.
- A Course in Combinatorics, Van Lint and Wilson (511.6 LIN)
- Graphs - an Introductory Approach, Wilson and Watkins (511.5 WIL)
- Schaum's Outlines Graph Theory, Balakrishnan (511.5076 BAL)
- Graph Theory, Merris (511.5 MER)
Note The picture at the top of this page is of a German stamp
issued in 1983, honouring
Leonhard Euler. For more stamps featuring mathematics and
mathematicians, see
this site.
NUI, Galway
School of Mathematics, Statistics and Applied Mathematics