Graph Theory
|
Course Objectives
|
| The aim is to understand the theoretical background of graphs and to apply graph algorithms into the most known problems. |
|
Course materials
|
- D. B. West, Introduction to Graph Theory,Prentice-Hall of India/Pearson, 2009.
- J. A. Bondy and U. S. R. Murty, Graph Theory and Applications, 2008.
|
|
Assessment
|
|
40% Midterm exam + 60% Final exam
|
|
Prerequisites
|
there is no formal prerequisite.
|
| Week |
Subjects |
|
| 1. |
Introduction to Graphs, isomorphism, subgraphs, matrix representations, degree |
|
| 2. |
Connected graphs, paths, distance, cut-vertices, cut-edges, weighted graphs, shortest path |
|
| 3. |
Spanning trees, minimum spanning trees |
|
| 4. |
Bipartite graphs, line graphs, chordal graphs |
|
| 5. |
Eulerian graphs, Fleury’s algorithm, chinese-postman problem |
|
| 6. |
Hamilton graphs |
|
| 7. |
Review for midterm exam |
|
| 8. |
Midterm exam |
|
| 9. |
Independent-covering-mathcing graphs, perfect matchings
|
|
| 10. |
Vertex colorings, chromatic number and cliques, greedy coloring, coloring of chordal graphs, Brook’s theorem |
|
| 11. |
Edge colorings, Gupta-Vizing theorem, class-1 and class-2 graphs, equitable edge-coloring |
|
| 12. |
Planar graphs, polyhedrons and planar graphs, planarity testing, 4 and 5 coloring |
|
| 13. |
Directed graph, underlying graph, outdegree, in-degree, connectivity, orientation, Eulerian directed graphs, Hamilton directed graphs, tournaments |
|
| 14. |
Students Presentations |
|
| 15. |
Review for final exam |
|
| |
Final Exam |
|
|