1 | Week | Date | Topic | |
---|---|---|---|---|
2 | Updated on 10/9/2019 | |||
3 | 1 | 3/9/2019-8/9/2019 | 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 | 9/9/2019-15/9/2019 | 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 | Tutorial | |||
27 | ||||
28 | 9/9/2019 | Agong's Birthday | ||
29 | ||||
30 | ||||
31 | 3 | 16/9/2019-22/9/2019 | 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 | - Eulerian Graph Theorem | |||
35 | - Semi-Eulerian Graph Theorem | |||
36 | ||||
37 | Tutorial | |||
38 | ||||
39 | 16/9/2019 | Hari Malaysia | ||
40 | ||||
41 | ||||
42 | 4 | 23/9/2019-27/9/2019 | 2. Trees and Distance | |
43 | ||||
44 | 2.1 Basic Properties | |||
45 | ||||
46 | 2.2 Distances and centroids | |||
47 | ||||
48 | 2.3 Spanning Trees | |||
49 | ||||
50 | 2.4 Matrix Tree Computation and Enumeration | |||
51 | - Kirchoff’s theorem (Matrix tree theorem) | |||
52 | - Cayley's Theorem | |||
53 | ||||
54 | QUIZ 1 | |||
55 | ||||
56 | Tutorial | |||
57 | ||||
58 | ||||
59 | 5 | 30/9/2019-6/10/2019 | 2.4 Optimization and Trees | |
60 | - Minimum Cost Spanning Tree, Prim’s and Kruskal’s Algorithms, | |||
61 | the Shortest Path Algorithms, Dijkstra’s algorithm | |||
62 | - Applications of Minimum Spanning Trees, Shortest Paths, | |||
63 | Dijkstra’s Algorithm, and Chinese Postman Problem. | |||
64 | ||||
65 | Tutorial | |||
66 | ||||
67 | ASSIGNMENT 1 (LAB) | |||
68 | ||||
69 | ||||
70 | 6 | 7/10/2019-13/10/2019 | 3. Matchings and Factors | |
71 | ||||
72 | 3.1 Matchings | |||
73 | ||||
74 | 3.2 Perfect, weighted, maximal and maximum matching | |||
75 | ||||
76 | 3.3 Hall’s Theorem – Hall’s Marriage Theorem | |||
77 | ||||
78 | 3.4 Min-Max Theorem (Cover) | |||
79 | - Vertex cover | |||
80 | - Edge cover | |||
81 | - König’s Theorem | |||
82 | ||||
83 | 3.5 Matchings in General Graphs | |||
84 | ||||
85 | 3.6 Tutte’s 1-factor Theorem (Perfect Matching) | |||
86 | ||||
87 | Tutorial | |||
88 | ||||
89 | ||||
90 | 7 | 14/10/2019-20/10/2019 | 3.8 Algorithms and applications | |
91 | - Assignment Problems | |||
92 | - Hungarian Algorithm | |||
93 | ||||
94 | 4. Connectivity and Paths | |||
95 | ||||
96 | 4.1 Cuts and Connectivity | |||
97 | - vertex cut, cut-vertex | |||
98 | - edge cut, cut-edges (bridge) | |||
99 | - cutset | |||
100 | - Whitney’s Theorem | |||
101 | ||||
102 | 4.2 The Minimal Connector problem | |||
103 | ||||
104 | 4.3 Blocks and k-connected graphs | |||
105 | ||||
106 | Tutorial | |||
107 | ||||
108 | TEST 1 | |||
109 | ||||
110 | ||||
111 | 8 | 21/10/2019-26/10/2019 | 4.4 Network Flow Problems, Max-Flow/Min-Cut Theorem and Ford-Fulkerson Labeling Algorithm | |
112 | ||||
113 | 4.5 Example: PERT and Critical Path Mathod | |||
114 | ||||
115 | 4.5 Example: Transportation and scheduling problems | |||
116 | ||||
117 | Tutorial | |||
118 | ||||
119 | ||||
120 | 27/10/2019-3/11/2019 | Mid-semester Break | ||
121 | ||||
122 | 27/10/2019 | Deepavali | ||
123 | ||||
124 | ||||
125 | 9 | 4/11/2019-10/11/2019 | 4.9 Applications of flow problems to water, oil, and electric distribution systems (circuits) | |
126 | ||||
127 | Tutorial | |||
128 | ||||
129 | ||||
130 | 10 | 11/11/2019-17/11/2019 | 5. Graph Colouring | |
131 | ||||
132 | 5.1 Colour Theorems | |||
133 | - Brooks Theorem | |||
134 | - Upper bound, lower bound | |||
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 | - Upper bound | |||
142 | - Maximum degree | |||
143 | ||||
144 | 5.5 Clique | |||
145 | ||||
146 | Tutorial | |||
147 | ||||
148 | QUIZ 2 | |||
149 | ||||
150 | ||||
151 | 11 | 18/11/2019-24/11/2019 | 5.5 Vertex and edge colouring problems and colouring applied to scheduling problems. | |
152 | ||||
153 | 5.6 Example: The Four Colour problems, assignment and scheduling problems, | |||
154 | physical layout problem, timetimetabling, transportation problems. | |||
155 | ||||
156 | Tutorial | |||
157 | ||||
158 | ||||
159 | 12 | 25/11/2019-1/12/2019 | 6. Planar Graphs | |
160 | ||||
161 | 6.1 Characterization of Planar Graphs | |||
162 | ||||
163 | 6.2 Embeddings and Euler's Formula | |||
164 | ||||
165 | 6.3 Properties, Parameters and Testing of Planarity | |||
166 | ||||
167 | 6.4 Planar Graphs: Kuratowski's Theorem and Graph Minors Colouring | |||
168 | ||||
169 | 6.5 Example: Plane Duality or Dual Graphs and Graphs of polyhedral | |||
170 | ||||
171 | BRAINSTORMING ON ASSIGNMENT 2 FRAMEWORK (PROJECT) | |||
172 | ||||
173 | Tutorial | |||
174 | ||||
175 | ||||
176 | 13 | 2/12/2019-8/12/2019 | 6.6 Applications: | |
177 | - Display of graphical data, i.e., flowcharts, organisational charts and scheduling conflicts, | |||
178 | - Design problems for circuits, subways and utility lines | |||
179 | - Algorithms for shortest paths in planar graphs | |||
180 | ||||
181 | TEST 2 | |||
182 | ||||
183 | ||||
184 | 14 | 9/12/2019-15/12/2019 | WORKING ON ASSIGNMENT 2 | |
185 | ||||
186 | REVIEW ON SELECTED TOPICS (FOR FINAL EXAM) | |||
187 | ||||
188 | COMPLETING AND SUBMISSION OF ASSIGNMENT 2 | |||
189 | ||||
190 | ||||
191 | 16/12/2019-22/12/2019 | Revision Week | ||
192 | ||||
193 | 23/12/2019-29/12/2019 | Special Break | ||
194 | ||||
195 | 25/12/2019 | Christmas Day | ||
196 | ||||
197 | 30/12/2020-20/1/2020 | Final Examination | ||
198 | ||||
199 | 21/1/2020-23/2/2020 | Semester Break | ||
200 | ||||
201 | Reference: https://hea.uitm.edu.my/v3/index.php/calendar/academic-calendars | |||
202 | ||||
203 | Assessment: | |||
204 | Final Examination - One 3-hour paper | : 60% | ||
205 | Continuous Assessments | : 40% | ||
206 | 2 Tests | : 20% | ||
207 | 2 Quizzes | : 6% | ||
208 | Assignment 1 | : 4% | ||
209 | Assignment 2 | : 10% | ||
210 | ||||
211 | Recommended Texts: | |||
212 | Deo, N. Graph Theory with Applications to Engineering and Computer Science. First Edition | |||
213 | (March 9, 2017). Dover Publications, 2017, ISBN: 0486807932. | |||
214 | ||||
215 | References: | |||
216 | 1. West, D. B., Introduction to Graph Theory (Classic Version), 2nd edition, Pearson, 2018, ISBN: 9780131437371. | |||
217 | 2. Diestel, R., Graph Theory (Graduate Texts in Mathematics), 5th Edition, Springer-Verlag, Berlin, 2017, ISBN: 9783662536216. | |||
218 | 3. Erciyes, K., Complex Networks: An Algorithmic Perspective. 1st Edition. CRC Press, 2017, ISBN: 9781138033894. | |||
219 | 4. Thulasiraman, K., Arumugam, S., Brandstädt , A. & Nishizeki, T. (Editors). Handbook of Graph Theory, Combinatorial Optimization, | |||
220 | and Algorithms, 1st Edition, Chapman & Hall/CRC, 2015, ISBN-13: 978-1584885955. | |||
221 | 5. Gross, J. L., Yellen, J. & Zhang, P., Handbook of Graph Theory, 2nd edition, CRC Press, 2013, ISBN: 9781439880180. | |||
222 | 6. Wilson, R. J., Introduction to Graph Theory, 5th edition (International Edition), Pearson Education, 2012, ISBN-13: 9780273728894. |