Teaching‎ > ‎

Graph Theory

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 (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, 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 240-241)
  • Spanning Trees, Fundamental Circuits, Finding All Spanning trees
  • Shortest Spanning Trees: Prim's and Kruskal's algorithm
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)
  • Circuit Matrix, Fundamental Circuit Matrix (page 142-145)
  • Adjacency Matrix (157-161) (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 (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: 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 [14-10, 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, 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 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:
    • Domino Puzzle
Ċ
Mohiuddin Khan,
Jan 19, 2015, 11:02 PM
Comments