Teaching‎ > ‎

Graph Theory 2016

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 Mid-semester: 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, Cut-sets and Cut-vertices, 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 (2-1, Deo), Subgraph (2-2, 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 25-27, Wilson), Eulerian Graphs(3.5, Wilson)
  • Randomly Traceable Graphs (2-8, Deo)
  • Hamiltonian Graphs (3.6, Wilson), Ore's and Dirac's theorem
  • Shortest Path, Chinese Postman, Travelling Salesman (3.7, Wilson)
  • Operations on Graphs (2-7, 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 240-241)
  • Spanning Trees, Fundamental Circuits, Finding All Spanning trees
Week 6: Cut-sets and Cut-vertices [Chapter 4, Deo], Matrix Representations of Graphs [Chapter 7, Deo]
  • Cut-sets, Properties of a cut-set, All cut-sets in a graph (Proof of Theorem 4-4 is excluded, example is included)
  • Fundamental circuits and cut-sets
  • Connectivity and Separability (up to Theorem 4-10)
  • Incidence Matrix (page 137-139)
  • Adjacency Matrix (157-161) 
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, Self-dual Graphs 
Week 9: Graph Coloring [Chapter 6, Wilson]
  • Coloring Vertices (6-17)
  • Brook's Theorem (6-18, without Proof), Coloring Maps (6-19, Up to Theorem 19.1)
  • Coloring Edges (6-20, Up to Theorem 20.2)
  • Chromatic Polynomials (6-21)
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, Max-Flow Min-Cut Theorem (14-1, Deo). Proof of Theorem 14-2 is excluded.
  • Extensions of Max-Flow Min-Cut Theorem (14-2, Deo)
  • Finding Maximum Flow: Greedy Algorithm, Ford-Fulkerson 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 [14-10, 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
Ċ
DAG.pdf
(107k)
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
Comments