Graph Theory (CSE 4533) is an optional course for third year CSE students. The objectives of the course are following:
 To introduce the important concepts of Graph Theory.
 To develop skills in solving basic exercises and proving theorems in
Graph Theory.
 To develop the ability to identity graph theoretic problems in
different problem domains and apply the knowledge to solve them.
Announcements:  Quiz #4 will take place on 29 April, Wednesday at classtime. Syllabus of the quiz is the materials covered in weeks 12, 13, 14 (up to 6.2).
 Quiz #3 will take place on 08 April, Wednesday at 2.00 pm in the classroom. Syllabus of the quiz is the materials covered in weeks 9, 10, 11.
 Quiz #2 will take place on 17 February, at 2.00 pm in the classroom. Syllabus of the quiz is the materials covered in weeks 4,5,6.
 Quiz #1 will take place on 28 January, at class time. 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, Properties
 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
 Shortest Spanning Trees: Prim's and Kruskal's algorithm
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)
 Circuit Matrix, Fundamental Circuit Matrix (page 142145)
 Adjacency Matrix (157161) (Not Included in Quiz #2)
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 [Continued]  Detection of Planarity
 Geometric Dual, Combinatorial dual
 Thickness and Crossing
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: Directed Graphs:  Digraphs (Chapter 7, Wilson. Up to Page 105)
 DAG, Topological Sorting (Refer to the PDF 18.1.2, Without Proofs)
Week 12: Graphs in Game Theory [1410, Deo]  Basic Types of Games
 Simplified Nim
 Kernel of a Digraph, Winning Strategy in a simple game
Week 13: Applicaton 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 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:

Updating...
Ċ Mohiuddin Khan, Jan 19, 2015, 11:02 PM
