COURSE OUTLINE: MH3300

Course Title

Graph Theory

Course Code

MH3300

Offered Study Year 3, Semester 1
Course Coordinator Gary Greaves (Dr) gary@ntu.edu.sg 6513 8652
Pre-requisites {MH1201 and MH1301} OR {MH2802}
AU 4
Contact hours Lectures: 39, Tutorials: 12
Approved for delivery from AY 2020/21 semester 1
Last revised 8 Jan 2020, 10:18

Course Aims

This course serves as an introduction to graph theory. As well as establishing some of the fundamentals of graph theory, this course aims to exhibit the wide range of applications enjoyed by graphs. The fundamentals of graph theory will be covered in a rigorous manner and you will be introduced to various graph invariants. You will see how these graphs invariants can be use to solve real-world problems. In particular, you will learn how to use graphs to solve scheduling problems, discrete optimization problems, and assignment problems.

Intended Learning Outcomes

Upon successfully completing this course, you should be able to:

  1. Determine whether or not two graphs are isomorphic
  2. Count the number of certain walks, paths, and cycle in a graph
  3. Identify smallest vertex and edge cuts
  4. Count the number of spanning trees in a graph
  5. Apply the augmenting path algorithm to find a maximal matching
  6. Use eigenvectors of the Laplacian matrix to draw a graph
  7. Find minimum vertex covers
  8. Apply the Kuhn-Munkres algorithm to find a largest weight diagonal of a matrix
  9. Find the chromatic number and chromatic polynomial of a graph
  10. Find the maximum flow in a network
  11. Find a minimum cut in a network
  12. Apply techniques from the course to solve real-world problems

Course Content

Cayley's formula and the matrix-tree theorem

The Laplacian matrix and graph orientations

Berge's lemma, Konig's theorem, and Hall's marriage theorem

Brook's theorem

The Ford-Fulkerson algorithm and the max-flow min-cut theorem

Menger's theorem

Assessment

Component Course ILOs tested SPMS-MAS Graduate Attributes tested Weighting Team / Individual Assessment Rubrics
Continuous Assessment
Tutorials
Homework 1, 2, 3, 4, 12 1. a, b, c, d
2. b, c, d
3. a, b
7.5 both See Appendix for rubric
Homework 1 5, 6, 7, 8, 12 1. a, b, c, d
2. b, c, d
3. a, b
7.5 both See Appendix for rubric
Mid-semester Quiz
Short Answer Questions 1, 2, 3, 4, 5, 7, 12 1. a, b, c, d
2. b, c, d
3. a
25 individual See Appendix for rubric
Examination (2 hours)
Short Answer Questions 1, 2, 3, 4, 5, 7, 9, 10, 11, 12 1. a, b, c, d
2. b, c, d
3. a
60 individual See Appendix for rubric
Total 100%

These are the relevant SPMS-MAS Graduate Attributes.

1. Competence

a. Independently process and interpret mathematical theories and methodologies, and apply them to solve problems

b. Formulate mathematical statements precisely using rigorous mathematical language

c. Discover patterns by abstraction from examples

d. Use computer technology to solve problems, and to communicate mathematical ideas

2. Creativity

b. Build on the connection between subfields of mathematics to tackle new problems

c. Develop new applications of existing techniques

d. Critically analyse data from a multitude of sources

3. Communication

a. Present mathematics ideas logically and coherently at the appropriate level for the intended audience

b. Work in teams on complicated projects that require applications of mathematics, and communicate the results verbally and in written form

Formative Feedback

Homework: formative feedback is written in your homework solution, which will be handed back to you

Midterm Test: formative feedback is written in your midterm script, which will be handed back to you. Feedback on common mistakes midterm test scripts will be given in a feedback lecture.

You will also receive formative feedback for all learning outcomes in the Examiner's report (available on ntuLearn are the exam period).

Learning and Teaching Approach

Lectures
(39 hours)

Derivations and proofs:
Explanations of concepts and proof ideas will help you digest the course content.

Examples:
Many concrete examples will be provided in the lectures to help you understand abstract ideas

Tutorials
(12 hours)

Tutorials provide an environment where it is OK to make mistakes and ask for extra help. Tutorials will help you obtain clarification for concepts that are troubling or confusing.

Reading and References

J. A. Bondy and U. S. R. Murty GRAPH THEORY WITH APPLICATIONS, ISBN-13: 978-0444194510
D. B. West INTRODUCTION TO GRAPH THEORY, ISBN-13: 978-0130144003

Course Policies and Student Responsibilities

(1) General

You are expected to complete all assigned class readings and activities, attend classes punctually and take all scheduled assignments and tests by due dates. You are expected to take responsibility to follow up with course notes and assignments, and to participate in tutorial discussions and activities.

(2) Absenteeism

Absence from class without a valid reason will affect your overall course grade. Valid reasons include falling sick supported by a medical certificate and participation in NTU’s approved activities supported by an excuse letter from the relevant bodies.

If you miss a lecture, you must inform the course instructor via email prior to the start of the class.

(3) Absence Due to Medical or Other Reasons

If you are sick and not able to attend a quiz or midterm, you have to submit the original Medical Certificate (or another relevant document) to the administration to obtain official leave. In this case, the missed assessment component will not be counted towards the final grade.

Academic Integrity

Good academic work depends on honesty and ethical behaviour. The quality of your work as a student relies on adhering to the principles of academic integrity and to the NTU Honour Code, a set of values shared by the whole university community. Truth, Trust and Justice are at the core of NTU’s shared values.

As a student, it is important that you recognize your responsibilities in understanding and applying the principles of academic integrity in all the work you do at NTU. Not knowing what is involved in maintaining academic integrity does not excuse academic dishonesty. You need to actively equip yourself with strategies to avoid all forms of academic dishonesty, including plagiarism, academic fraud, collusion and cheating. If you are uncertain of the definitions of any of these terms, you should go to the Academic Integrity website for more information. Consult your instructor(s) if you need any clarification about the requirements of academic integrity in the course.

Course Instructors

Instructor Office Location Phone Email
Gary Greaves (Dr) MAS-05-03 6513 8652 gary@ntu.edu.sg

Planned Weekly Schedule

Week Topic Course ILO Readings/ Activities
1

Basic notions of graphs: Graphs, subgraphs, graph isomorphism, adjacency and incidence matrices, walks, paths, and cycles.

1, 2, 12

Lecture notes/tutorial problems

2

Basic notions of graphs: Graphs, subgraphs, graph isomorphism, adjacency and incidence matrices, walks, paths, and cycles.

1, 2, 12

Lecture notes/tutorial problems

3

Trees, cuts, and connectivity: Classifications of trees, cut-vertices, cut-edges, spanning trees, recursive counting, Cayley’s formula, vertex cuts and connectivity, edge cuts and edge-connectivity.

3, 4, 12

Lecture notes/tutorial problems

4

Trees, cuts, and connectivity: Classifications of trees, cut-vertices, cut-edges, spanning trees, recursive counting, Cayley’s formula, vertex cuts and connectivity, edge cuts and edge-connectivity.

3, 4, 12

Lecture notes/tutorial problems

5

The Laplacian matrix: The Laplacian matrix, orientations, signed incidence matrices, finding edge cuts, counting connected components, the matrix-tree theorem, how to draw a graph.

4, 6

Lecture notes/tutorial problems

6

The Laplacian matrix: The Laplacian matrix, orientations, signed incidence matrices, finding edge cuts, counting connected components, the matrix-tree theorem, how to draw a graph.

4, 6

Lecture notes/tutorial problems

7

Matchings: Motivating problems, matchings, alternating paths, augmenting paths, Berge’s lemma, the augmenting path algorithm, vertex coverings, Konig’s theorem, Hall’s Marriage theorem, weighted matchings, the Kuhn-Munkres algorithm.

5, 7, 8, 12

Lecture notes/tutorial problems

8

Matchings: Motivating problems, matchings, alternating paths, augmenting paths, Berge’s lemma, the augmenting path algorithm, vertex coverings, Konig’s theorem, Hall’s Marriage theorem, weighted matchings, the Kuhn-Munkres algorithm.

5, 7, 8, 12

Lecture notes/tutorial problems

9

Graph colouring: Motivating problems, k-colouring, the chromatic number, bipartite graph classification, subgraph inheritance, excluding subgraphs, greedy algorithm for colouring, Brook’s theorem, chromatic polynomials

9, 12

Lecture notes/tutorial problems

10

Graph colouring: Motivating problems, k-colouring, the chromatic number, bipartite graph classification, subgraph inheritance, excluding subgraphs, greedy algorithm for colouring, Brook’s theorem, chromatic polynomials

9, 12

Lecture notes/tutorial problems

11

Network Flow: Motivating problems, directed graphs, networks, capacity functions, flows, Ford-Fulkerson algorithm, Max-flow problem, Min-cut problem, Max-flow min-cut theorem, Menger’s theorem.

10, 11, 12

Lecture notes/tutorial problems

12

Network Flow: Motivating problems, directed graphs, networks, capacity functions, flows, Ford-Fulkerson algorithm, Max-flow problem, Min-cut problem, Max-flow min-cut theorem, Menger’s theorem.

10, 11, 12

Lecture notes/tutorial problems

13

Revision and Review

1, 2, 3, 4, 5, 7, 9, 10, 11, 12

Lecture notes/tutorial problems

Appendix 1: Assessment Rubrics

Rubric for Tutorials: Homework (7.5%)

Point-based marking (not rubrics based)

Collaboration is encouraged for your homework because peer-to-peer learning helps you  understand the subject better and working in a team trains you to better communicate with  others in your profession. As part of academic integrity, crediting others for their contribution  to your work promotes ethical practice.

You must write up your solutions by yourself and understand anything that you hand in.

If you do collaborate, you must write on your solution sheet the names of the students you  worked with. If you did not collaborate with anyone, please explicitly write "No collabora tors". Failure to do so constitutes plagiarism.

If you use an outside source, you must reference it in your solution.

Rubric for Tutorials: Homework 1 (7.5%)

Point-based marking (not rubrics based)

Collaboration is encouraged for your homework because peer-to-peer learning helps you  understand the subject better and working in a team trains you to better communicate with  others in your profession. As part of academic integrity, crediting others for their contribution  to your work promotes ethical practice.

You must write up your solutions by yourself and understand anything that you hand in.

If you do collaborate, you must write on your solution sheet the names of the students you  worked with. If you did not collaborate with anyone, please explicitly write "No collabora tors". Failure to do so constitutes plagiarism.

If you use an outside source, you must reference it in your solution.

Rubric for Mid-semester Quiz: Short Answer Questions (25%)

Point-based marking (not rubrics based)

Rubric for Examination: Short Answer Questions (60%)

Point-based marking (not rubrics based)