Textbooks:1. Graph Theory with Application to Engineering and Computer Science. Narsingh Deo 2. Introduction to Graph Theory. Robin J. Wilson
Announcements:  Semester Final: Week 6,7, 8 are excluded. Everything else is in.
 Quiz 4 will be on May 2, 10 am. The syllabus of the quiz are materials covered in Weeks 12, 13 and 14.
 Quiz 3 will be on April 19, Tuesday 2.00 pm. The syllabus of the quiz are materials covered in Weeks 9, 10 and 11.
 Syllabus of the Midsemester: Contents covered so far, i.e., Week 1 to Week 8.
 Quiz 2 will be on March 2, Wednesday 2.00 pm. The syllabus of the quiz is Trees, Cutsets and Cutvertices, i.e., Chapter 3 and 4 from Deo.
 Quiz 1 will be on 10 February, Wednesday, after class. The syllabus of the quiz is the materials covered in the first three weeks.
Timeline:
Week 1: Introduction (Chapter 1, Deo)  What is a Graph?
 Application of Graphs: Koenigsberg Bridge Problem, Three Utilities Problem
 Finite and Infinite Graphs, Incidence and Degree
 Isolated vertex, Pendant vertex, Null Graph
Week 2: Definitions and Examples  Definitions, Isomorphism, Connected and Disconnected graphs, Adjacency, Subgraphs, Matrix Representations (2.2, Wilson)
 More on Isomorphism (21, Deo), Subgraph (22, Deo)
 Examples: Null, Complete, Cycle, Path,Wheel, Regular, Platonic, Bipartite, Cube Graphs, Complement of a Graph (2.3, Wilson)
 Puzzles: Eight Circle Problem, Six People at a Party (2.4, Wilson)
Week 3: Paths and Cycles  Connectivity (Page 2527, Wilson), Eulerian Graphs(3.5, Wilson)
 Randomly Traceable Graphs (28, Deo)
 Hamiltonian Graphs (3.6, Wilson), Ore's and Dirac's theorem
 Shortest Path, Chinese Postman, Travelling Salesman (3.7, Wilson)
 Operations on Graphs (27, Deo)
Week 4: Trees [Chapter 3, Deo]  Definition and Properties of Tree (Chapter 3, Deo)
 Distance, Centers of Trees
 Rooted Tree, Binary Tree, Weighted Path Length
Week 5: Trees (Continued)  Counting Trees, Cayley's Theorem (Proof from Chapter 10, Page 240241)
 Spanning Trees, Fundamental Circuits, Finding All Spanning trees
Week 6: Cutsets and Cutvertices [Chapter 4, Deo], Matrix Representations of Graphs [Chapter 7, Deo]  Cutsets, Properties of a cutset, All cutsets in a graph (Proof of Theorem 44 is excluded, example is included)
 Fundamental circuits and cutsets
 Connectivity and Separability (up to Theorem 410)
 Incidence Matrix (page 137139)
 Adjacency Matrix (157161)
Week 7: Planar and Dual Graphs [Chapter 5, Deo] Combinatorial vs Geometric Graphs
 Planar Graphs, Kuratowski's Two Graphs
 Regions, Infinite Regions
 Euler's Formula (Proof from Wilson, Page 66)
Week 8: Planar and Dual Graphs [Chapter 5, Deo. Up to Page 107]  Detection of Planarity
 Geometric Dual, Combinatorial dual, Selfdual Graphs
Week 9: Graph Coloring [Chapter 6, Wilson]  Coloring Vertices (617)
 Brook's Theorem (618, without Proof), Coloring Maps (619, Up to Theorem 19.1)
 Coloring Edges (620, Up to Theorem 20.2)
 Chromatic Polynomials (621)
Week 10: Graph Matching: [Handout, PDF Uploaded]  Matching: Definition, Stable and Perfect Matching, Will you marry me?
 Stable Marriage Problem, Finding the Stable Matching, TMA: Algorithm, Example
 TMA: All the Theorem, Lemma and their proofs are included. Only the proof of Theorems 4 and 5 are excluded.
Week 11: Application of Graph Theory:Transport Networks  Transport Networks, Maximal Flow, Cut and capacity, MaxFlow MinCut Theorem (141, Deo). Proof of Theorem 142 is excluded.
 Extensions of MaxFlow MinCut Theorem (142, Deo)
 Finding Maximum Flow: Greedy Algorithm, FordFulkerson Algorithm [ Handout, PDF Uploaded]
Week 12: Directed Graph  Digraphs (Chapter 7, Wilson. Up to Page 105)
 DAG, Topological Sorting (Refer to the PDF 18.1.2, Without Proofs)
Week 13: Graphs in Game Theory [1410, Deo]  Basic types of games
 Simplified Nim
 Kernel of a game graph
 Winning strategy
Week 14: Matching and Covering [Handout, PDF Uploaded]  Matching, Covering (6.1)
 Hungarian Algorithm, Finding Augmenting Paths, Perefect Matching in Bipartite Graphs (6.2)
 Applications of Matching and Covering in Bipartite Graphs: (6.3, up to page 37)
 Domino Puzzle
 Structure rank of matrix

Updating...
Ċ Mohiuddin Khan, Apr 30, 2016, 11:17 PM
Ċ Mohiuddin Khan, Apr 6, 2016, 9:39 PM
Ċ Mohiuddin Khan, Jan 31, 2016, 11:46 PM
Ċ Mohiuddin Khan, Apr 30, 2016, 11:17 PM
Ċ Mohiuddin Khan, Apr 6, 2016, 9:39 PM
