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 |

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.

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

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

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

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, d2. b, c, d3. a, b | 7.5 | both | See Appendix for rubric |

Homework 1 | 5, 6, 7, 8, 12 | 1. a, b, c, d2. b, c, d3. 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, d2. b, c, d3. 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, d2. b, c, d3. 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

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).

Lectures (39 hours) | Derivations and proofs: Examples: |

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. |

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

(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.

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.

Instructor | Office Location | Phone | |
---|---|---|---|

Gary Greaves (Dr) | MAS-05-03 | 6513 8652 | gary@ntu.edu.sg |

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 |

*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.*

*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.*