1 | Week | Date | Topic | |
---|---|---|---|---|

2 | ||||

3 | 1 | 7/9/15 - 11/9/15 | 1. Definitions and Fundamental Concepts | |

4 | ||||

5 | 1.1 Graph Basics and Definitions | |||

6 | - Vertices/Nodes, Edges, Adjacency, Incidence | |||

7 | - Degree, In-Degree, Out-Degree | |||

8 | - Subgraphs, Unions, Isomorphism | |||

9 | - Adjacency Matrices | |||

10 | - Degree Sequences | |||

11 | ||||

12 | 1.2 Walk, Paths, Cycles, and Trails | |||

13 | ||||

14 | 1.3 Vertex Degrees and Counting | |||

15 | ||||

16 | Tutorial | |||

17 | ||||

18 | ||||

19 | 2 | 14/9/15 - 18/9/15 | 1.4 Types of Graphs | |

20 | - Trees, Undirected graphs, Simple graphs, Multigraphs, Pseudographs, | |||

21 | Directed Graphs (Digraphs), Directed Multigraphs, Regular, Bipartite and Complete Graphs, | |||

22 | Cycles, Wheels, Cubes, Complete Bipartite | |||

23 | ||||

24 | 1.5 Operations and properties | |||

25 | ||||

26 | 1.6 Proof styles | |||

27 | ||||

28 | Tutorial | |||

29 | ||||

30 | 16/9/15 (Wed) | Hari Malaysia | ||

31 | ||||

32 | ||||

33 | 3 | 21/9/15 - 25/9/15 | 1.7 Traversability Problems in Graphs | |

34 | - Königsberg Bridge problem and Eulerian graphs, Hamiltonian circuits and paths, | |||

35 | and applications of Eulerian and Hamiltonian Graphs | |||

36 | ||||

37 | Tutorial | |||

38 | ||||

39 | 24/9/15 (Thu) - 25/9/15 (Fri) | Raya Haji | ||

40 | ||||

41 | ||||

42 | 4 | 28/9/15 - 2/10/15 | 2. Trees and Distance | |

43 | ||||

44 | 2.1 Basic Properties | |||

45 | ||||

46 | 2.2 Distances and centroids | |||

47 | ||||

48 | 2.3 Spanning Trees and Enumeration. | |||

49 | ||||

50 | 2.4 Optimization and Trees | |||

51 | - Minimum Cost Spanning Tree, Prim’s and Kruskal’s Algorithms, | |||

52 | the Shortest Path Algorithms, Dijkstra’s algorithm | |||

53 | ||||

54 | QUIZ 1 | |||

55 | ||||

56 | Tutorial | |||

57 | ||||

58 | ||||

59 | 5 | 5/10/15 - 9/10/15 | 2.5 Matrix Tree Computation | |

60 | ||||

61 | 2.6 Applications of Minimum Spanning Trees, Shortest Paths, | |||

62 | Dijkstra’s Algorithm, and Chinese Postman Problem | |||

63 | ||||

64 | 2.7 Rooted tree, Binary tree and Huffman’s Algorithm | |||

65 | ||||

66 | LAB ASSIGNMENT 1 | |||

67 | ||||

68 | Tutorial | |||

69 | ||||

70 | ||||

71 | 6 | 12/10/15 - 16/10/15 | 3. Matchings and Factors | |

72 | ||||

73 | 3.1 Matchings | |||

74 | ||||

75 | 3.2 Perfect, weighted, maximal and maximum matching | |||

76 | ||||

77 | 3.3 Hall’s Theorem – Hall’s Marriage Theorem | |||

78 | ||||

79 | 3.4 Min-Max Theorem (Cover) | |||

80 | ||||

81 | 3.5 König’s Theorem | |||

82 | ||||

83 | 3.6 Matchings in General Graphs | |||

84 | ||||

85 | 3.7 Tutte’s 1-factor Theorem | |||

86 | ||||

87 | Tutorial | |||

88 | ||||

89 | 14/10/15 (Wed) | Awal Muharram | ||

90 | ||||

91 | ||||

92 | 7 | 19/10/15 - 23/10/15 | 3.8 Algorithms and applications | |

93 | - Assignment Problems | |||

94 | - Hungarian Algorithm | |||

95 | ||||

96 | 4. Connectivity and Paths | |||

97 | ||||

98 | 4.1 Cuts and Connectivity | |||

99 | ||||

100 | 4.2 The Minimal Connector problem | |||

101 | ||||

102 | 4.3 Blocks and k-connected graphs | |||

103 | ||||

104 | QUIZ 2 | |||

105 | ||||

106 | Tutorial | |||

107 | ||||

108 | ||||

109 | 8 | 26/10/15 - 30/10/15 | 4.4 Closed Ear Decomposition, Menger’s Theorem(s), Proof of Menger’s Theorem(s) | |

110 | ||||

111 | 4.4 Network Flow Problems, Max-Flow/Min-Cut Theorem and Ford-Fulkerson Labeling Algorithm | |||

112 | ||||

113 | 4.5 PERT and Critical Path Mathod | |||

114 | ||||

115 | 4.6 Network Flow Algorithms | |||

116 | ||||

117 | Tutorial | |||

118 | ||||

119 | ||||

120 | 9 | 2/11/15 - 6/11/15 | 4.7 Transportation and scheduling problems | |

121 | ||||

122 | 4.8 Computational geometry Problems, | |||

123 | ||||

124 | 4.9 Applications of flow problems to water, oil, and electric distribution systems | |||

125 | ||||

126 | TEST 1 | |||

127 | ||||

128 | Tutorial | |||

129 | ||||

130 | ||||

131 | 9/11/15 - 15/11/15 | Mid-Semester Break | ||

132 | ||||

133 | 10/11/15 (Tue) | Deepavali | ||

134 | ||||

135 | ||||

136 | 10 | 16/11/15 - 20/11/15 | 5. Graph Colouring | |

137 | ||||

138 | 5.1 Colour Theorems | |||

139 | ||||

140 | 5.2 The Four / Five Colour Problems Vertex and Edge Colouring Problems | |||

141 | ||||

142 | 5.3 Hamiltonian Cycles, Chromatic Polynomials | |||

143 | ||||

144 | 5.4 k-Chromatic graphs, Upper Bounds and Enumerative Aspects | |||

145 | ||||

146 | LAB ASSIGNMENT 2 | |||

147 | ||||

148 | Tutorial | |||

149 | ||||

150 | ||||

151 | 11 | 23/11/15 - 27/11/15 | 5.5 Vertex and edge colouring problems and colouring applied to scheduling problems. | |

152 | ||||

153 | 5.6 The Four Colour problems, assignment and scheduling problems, | |||

154 | physical layout problem, round-robin scheduling, exam timetabling, | |||

155 | transportation problems (minimum connector problem, the traveling salesman problem). | |||

156 | ||||

157 | QUIZ 3 | |||

158 | ||||

159 | Tutorial | |||

160 | ||||

161 | ||||

162 | 12 | 30/11/15 - 4/12/15 | 6. Planar Graphs | |

163 | ||||

164 | 6.1 Characterization of Planar Graphs | |||

165 | ||||

166 | 6.2 Embeddings and Euler's Formula | |||

167 | ||||

168 | 6.3 Properties, Parameters and Testing of Planarity | |||

169 | ||||

170 | 6.4 Planar Graphs: Kuratowski's Theorem and Graph Minors Colouring | |||

171 | ||||

172 | 6.5 Plane Duality or Dual Graphs and Graphs of polyhedral | |||

173 | ||||

174 | BRAINSTORMING ON PROJECT FRAMEWORK | |||

175 | ||||

176 | Tutorial | |||

177 | ||||

178 | ||||

179 | 13 | 7/12/15 - 11/12/15 | 6.6 Applications: | |

180 | - Display of graphical data, i.e., flowcharts, organisational charts and scheduling conflicts, | |||

181 | - Design problems for circuits, subways and utility lines | |||

182 | - Algorithms for shortest paths in planar graphs | |||

183 | ||||

184 | WORKING ON PROJECT | |||

185 | ||||

186 | ||||

187 | 14 | 14/12/15 - 18/12/15 | TEST 2 | |

188 | ||||

189 | REVIEW ON SELECTED TOPICS (FOR FINAL EXAM) | |||

190 | ||||

191 | COMPLETING AND SUBMISSION OF PROJECT | |||

192 | ||||

193 | ||||

194 | 21/12/15 - 27/12/15 | Revision Week | ||

195 | ||||

196 | 24/12/15 (Thu) | Maulidur Rasul | ||

197 | 25/12/15 (Fri) | Christmas | ||

198 | ||||

199 | 28/12/15 - 19/1/15 | Final Examination | ||

200 | ||||

201 | ||||

202 | Assessment: | |||

203 | Final Examination - One 3-hour paper | : 60% | ||

204 | Continuous Assessments | : 40% | ||

205 | 2 Tests (20%) | |||

206 | 3 Quizzes (6%) | |||

207 | Assignments (4%) | |||

208 | 1 Group Project (10%) | |||

209 | ||||

210 | Recommended Text: | |||

211 | Wilson, R. J., Introduction to Graph Theory, 5th ed, Pearson, 2012, ISBN: 027372889X | |||

212 | ||||

213 | Gould, R., Graph Theory, Reprint Edition (August 30, 2013) (Dover Books on Mathematics), Dover Publications;, 2013, ISBN: 0486498069 | |||

214 | ||||

215 | References: | |||

216 | Gross, J. L., Yellen, J. & Zhang, P., Handbook of Graph Theory, Second Edition, 2nd edition, CRC Press, 2013, ISBN: 9781439880180 | |||

217 | ||||

218 | Mark Newman, Networks, 1st edition., OUP Oxford, 2010, ISBN: 9780199206650 | |||

219 | ||||

220 | Harris, J., Hirst, J. L. & Mossinghoff, M., Combinatorics and Graph Theory (Undergraduate Texts in Mathematics) | |||

221 | Undergraduate Texts in Mathematics , 2nd edition, Springer, 2008, ISBN: 978038779710 | |||

222 | ||||

223 | West, D. B., Introduction to Graph Theory, 2nd edition, Pearson, 2001, ISBN: 0130144002 |