1 | Week | Date | Topic | |
---|---|---|---|---|
2 | ||||
3 | 1 | 6/3/17 - 10/3/17 | 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 | 13/3/17 - 17/3/17 | 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 | ||||
31 | 3 | 20/3/17 - 24/3/17 | 1.7 Traversability Problems in Graphs | |
32 | - Königsberg Bridge problem and Eulerian graphs, Hamiltonian circuits and paths, | |||
33 | and applications of Eulerian and Hamiltonian Graphs | |||
34 | ||||
35 | Tutorial | |||
36 | ||||
37 | ||||
38 | 4 | 27/3/17 - 31/3/17 | 2. Trees and Distance | |
39 | ||||
40 | 2.1 Basic Properties | |||
41 | ||||
42 | 2.2 Distances and centroids | |||
43 | ||||
44 | 2.3 Spanning Trees and Enumeration. | |||
45 | ||||
46 | 2.4 Optimization and Trees | |||
47 | - Minimum Cost Spanning Tree, Prim’s and Kruskal’s Algorithms, | |||
48 | the Shortest Path Algorithms, Dijkstra’s algorithm | |||
49 | ||||
50 | QUIZ 1 | |||
51 | ||||
52 | Tutorial | |||
53 | ||||
54 | ||||
55 | 5 | 3/4/17 - 7/4/17 | 2.5 Matrix Tree Computation | |
56 | ||||
57 | 2.6 Applications of Minimum Spanning Trees, Shortest Paths, | |||
58 | Dijkstra’s Algorithm, and Chinese Postman Problem | |||
59 | ||||
60 | 2.7 Rooted tree, Binary tree and Huffman’s Algorithm | |||
61 | ||||
62 | LAB ASSIGNMENT 1 | |||
63 | ||||
64 | Tutorial | |||
65 | ||||
66 | ||||
67 | 6 | 10/4/17 - 14/4/17 | 3. Matchings and Factors | |
68 | ||||
69 | 3.1 Matchings | |||
70 | ||||
71 | 3.2 Perfect, weighted, maximal and maximum matching | |||
72 | ||||
73 | 3.3 Hall’s Theorem – Hall’s Marriage Theorem | |||
74 | ||||
75 | 3.4 Min-Max Theorem (Cover) | |||
76 | ||||
77 | 3.5 König’s Theorem | |||
78 | ||||
79 | 3.6 Matchings in General Graphs | |||
80 | ||||
81 | 3.7 Tutte’s 1-factor Theorem | |||
82 | ||||
83 | Tutorial | |||
84 | ||||
85 | ||||
86 | 7 | 17/4/17 - 21/4/17 | 3.8 Algorithms and applications | |
87 | - Assignment Problems | |||
88 | - Hungarian Algorithm | |||
89 | ||||
90 | 4. Connectivity and Paths | |||
91 | ||||
92 | 4.1 Cuts and Connectivity | |||
93 | ||||
94 | 4.2 The Minimal Connector problem | |||
95 | ||||
96 | 4.3 Blocks and k-connected graphs | |||
97 | ||||
98 | QUIZ 2 | |||
99 | ||||
100 | Tutorial | |||
101 | ||||
102 | ||||
103 | 8 | 24/4/17 - 28/4/17 | 4.4 Closed Ear Decomposition, Menger’s Theorem(s), Proof of Menger’s Theorem(s) | |
104 | ||||
105 | 4.4 Network Flow Problems, Max-Flow/Min-Cut Theorem and Ford-Fulkerson Labeling Algorithm | |||
106 | ||||
107 | 4.5 PERT and Critical Path Mathod | |||
108 | ||||
109 | 4.6 Network Flow Algorithms | |||
110 | ||||
111 | Tutorial | |||
112 | ||||
113 | 24/4/17 (Mon) | Israk & Mikraj | ||
114 | ||||
115 | ||||
116 | 1/5/17 (Mon) | Labour Day | ||
117 | ||||
118 | 1/5/17 - 7/5/17 | Mid-Semester Break | ||
119 | ||||
120 | ||||
121 | 9 | 8/5/17 - 12/5/17 | 4.7 Transportation and scheduling problems | |
122 | ||||
123 | 4.8 Computational geometry Problems, | |||
124 | ||||
125 | 4.9 Applications of flow problems to water, oil, and electric distribution systems | |||
126 | ||||
127 | TEST 1 | |||
128 | ||||
129 | Tutorial | |||
130 | ||||
131 | ||||
132 | 10 | 15/5/17 - 19/5/17 | 5. Graph Colouring | |
133 | ||||
134 | 5.1 Colour Theorems | |||
135 | ||||
136 | 5.2 The Four / Five Colour Problems Vertex and Edge Colouring Problems | |||
137 | ||||
138 | 5.3 Hamiltonian Cycles, Chromatic Polynomials | |||
139 | ||||
140 | 5.4 k-Chromatic graphs, Upper Bounds and Enumerative Aspects | |||
141 | ||||
142 | LAB ASSIGNMENT 2 | |||
143 | ||||
144 | Tutorial | |||
145 | ||||
146 | 17/5/17 (Wed) | Raja Perlis' Birthday | ||
147 | ||||
148 | ||||
149 | 11 | 22/5/17 - 26/5/17 | 5.5 Vertex and edge colouring problems and colouring applied to scheduling problems. | |
150 | ||||
151 | 5.6 The Four Colour problems, assignment and scheduling problems, | |||
152 | physical layout problem, round-robin scheduling, exam timetabling, | |||
153 | transportation problems (minimum connector problem, the traveling salesman problem). | |||
154 | ||||
155 | QUIZ 3 | |||
156 | ||||
157 | Tutorial | |||
158 | ||||
159 | ||||
160 | 29/5/17 - 4/6/17 | Special Leave (Harvest Festival 30/5/17 - 31/5/17) | ||
161 | ||||
162 | ||||
163 | 12 | 5/6/17 - 9/6/17 | 6. Planar Graphs | |
164 | ||||
165 | 6.1 Characterization of Planar Graphs | |||
166 | ||||
167 | 6.2 Embeddings and Euler's Formula | |||
168 | ||||
169 | 6.3 Properties, Parameters and Testing of Planarity | |||
170 | ||||
171 | 6.4 Planar Graphs: Kuratowski's Theorem and Graph Minors Colouring | |||
172 | ||||
173 | 6.5 Plane Duality or Dual Graphs and Graphs of polyhedral | |||
174 | ||||
175 | BRAINSTORMING ON PROJECT FRAMEWORK | |||
176 | ||||
177 | Tutorial | |||
178 | ||||
179 | ||||
180 | 13 | 12/6/17 - 16/6/17 | 6.6 Applications: | |
181 | - Display of graphical data, i.e., flowcharts, organisational charts and scheduling conflicts, | |||
182 | - Design problems for circuits, subways and utility lines | |||
183 | - Algorithms for shortest paths in planar graphs | |||
184 | ||||
185 | WORKING ON PROJECT | |||
186 | ||||
187 | 12/6/17 (Mon) | Nuzul al-Quran | ||
188 | ||||
189 | ||||
190 | 14 | 19/6/17 - 23/6/17 | TEST 2 | |
191 | ||||
192 | REVIEW ON SELECTED TOPICS (FOR FINAL EXAM) | |||
193 | ||||
194 | COMPLETING AND SUBMISSION OF PROJECT | |||
195 | ||||
196 | ||||
197 | 25/6/17 (Sun) - 26/6/17 (Mon) | Hari Raya Puasa | ||
198 | ||||
199 | 26/6/17 - 2/7/17 | Revision Week | ||
200 | ||||
201 | ||||
202 | 3/7/17 - 23/7/17 | Final Examination | ||
203 | ||||
204 | ||||
205 | 24/7/17 - 10/9/17 | Semester Break | ||
206 | ||||
207 | ||||
208 | Assessment: | |||
209 | Final Examination - One 3-hour paper | : 60% | ||
210 | Continuous Assessments | : 40% | ||
211 | 2 Tests (20%) | |||
212 | 3 Quizzes (6%) | |||
213 | Assignments (4%) | |||
214 | 1 Group Project (10%) | |||
215 | ||||
216 | Recommended Text: | |||
217 | Wilson, R. J., Introduction to Graph Theory, 5th ed, Pearson, 2012, ISBN: 027372889X | |||
218 | ||||
219 | Gould, R., Graph Theory, Reprint Edition (August 30, 2013) (Dover Books on Mathematics), Dover Publications;, 2013, ISBN: 0486498069 | |||
220 | ||||
221 | References: | |||
222 | Gross, J. L., Yellen, J. & Zhang, P., Handbook of Graph Theory, Second Edition, 2nd edition, CRC Press, 2013, ISBN: 9781439880180 | |||
223 | ||||
224 | Mark Newman, Networks, 1st edition., OUP Oxford, 2010, ISBN: 9780199206650 | |||
225 | ||||
226 | Harris, J., Hirst, J. L. & Mossinghoff, M., Combinatorics and Graph Theory (Undergraduate Texts in Mathematics) | |||
227 | Undergraduate Texts in Mathematics , 2nd edition, Springer, 2008, ISBN: 978038779710 | |||
228 | ||||
229 | West, D. B., Introduction to Graph Theory, 2nd edition, Pearson, 2001, ISBN: 0130144002 |