Teaching‎ > ‎

CSE 4533 - Graph Theory

This course is an introduction to the fundamental concepts of graph theory. In the latter portion of the course, we will focus on some advanced materials. Besides, you will also learn about applying graph theoretic approach to solve problems. 


Quiz Marks
Quiz marks, along with attendance and mid-semester marks, is uploaded (see the file section below). I have found one script each in Quiz #1 and Quiz #2 without any student id written on it. If you are one of them, or if you think your marks are entered wrong, please contact me by Tuesday, 8 May.
Update: The missing roll numbers, for quiz 1 and 2, are 094427 and 094420, respectively. An updated version of the mark sheet is was uploaded.

Quiz #1 Date Announced
The first quiz will be held on Tuesday, 17 January at 10 am. The syllabus is the contents covered in the first three weeks.

Quiz #2 Date Announced
The second quiz will be held on Sunday, 12 February at 2 pm. The syllabus is the contents covered in weeks 4 to 7.

Quiz #3 Date Announced
The third quiz will be held on  28 March  1 April at 2 pm. The syllabus is the contents covered in weeks 11 to 13 (Planarity and Matrices).

Quiz #4 Date Announced
The fourth quiz will be held on Monday, 16 April at 2 pm. The syllabus is the contents covered in the weeks 14 and 15.

Timeline:
  1. Week 1: Introduction, History, Definitions, Incidence and Degree (Chapter 1, Deo. Excluding pages 5 and 6)
  2. Week 2
    • Some important graphs (Null, Complete, Regular, Platonic, Bipartite, Cubes etc) (Section 2.3, Wilson)
    • Isomorphism (2.1, Deo)
    • Subgraphs (2.2, Deo)
    • Walks, Paths and Circuits (2.4, Deo)
    • Connected, Disconnected graphs (2.5, Deo)
    • Matrix Representation (Page 14, Wilson)
  3. Week 3
    • Theorem 2-3 (Deo)
    • Eight circles problem, Six people at a party (Section 2.4, Wilson)
    • Euler graphs: 
      • Definition, Euler's Theorem (with proof), Fleury's algorithm (without proof) (3.6, Wilson)
      • Randomly/Arbitrarily traceable graphs (2.8, Deo)
    • Hamiltonian graphs:
      • Definitions, (3.7, Wilson, excluding theorem 7.1)
  4. Week 4:
    • Some algorithms (3.8, Wilson): Shortest path problem, The Chinese postman problem, The travelling salesman problem
  5. Week 5:
    • Trees (Chapter 3, Deo): Definition, Properties, Distance and Centers
  6. Week 6:
    • Trees: Rooted and binary trees, Counting trees
  7. Week 7:
    • Trees: Spanning Trees, Fundamental Circuits, Finding all spanning trees of a graph, Spanning trees in a weighted graph
  8. Week 8:
    • Cut-sets and cut-vertices (Chapter 4, Deo) : Cut-sets, Properties of cut-sets, all cut-sets in a graph, fundamental cut-sets, connectivity and separability.
  9. Week 9, 10: 
    • Mid-semester Exam. 
  10. Week 11: Planar and Dual graphs (Chapter 5, Deo)
    • Introduction, Kuratowski's two graphs, detection of planarity (5.1 - 5.5)
  11. Week 12: Planar and Dual graph (Chapter 5, Deo)
    • Homeomorphic graphs, Geometric dual, combinatorial dual, self-dual graphs, thickness and crossing (5.6, 5.7, 5.9)
    • Euler's formula (Theorem 5-6. The proof of this theorem is shown from page 66 of Wilson)
  12. Week 13Matrix representation of graphs (Chapter 7, Deo)
    • Incidence matrix ( 7.1, upto page 139)
    • Circuit matrix (7.3, excluding theorem 7.4)
    • Fundamental circuit matrix (7.4, pages 144 and 145)
    • Cut-set matrix (Only definition and example, excluding the properties)
    • Adjacency matrix (7.9, pages 157-160)
  13. Week 14: Colouring graphs (Chapter 6, Wilson)
    • Colouring vertices (6.17)
    • Colouring maps (6.19, up to theorem 19.4)
  14. Week 15: 
    • Colouring edges (6.20, up to theorem 20.3)
    • Chromatic Polynomial (6.21)
    • Digraphs (7.22, Wilson, up to theorem 22.1 excluding the proof)+(7.23, up to theorem 23.3 excluding the proof)
  15. Week 16: Graph Theory in Operations Research (Chapter 14, Deo)
    • Transport networks (14.1, Excluding "Linear programming formulation")
    • Theorem 14.1 (without proof), theorem 14.2 (without proof, but with example)
    • Extensions of max-flow min-cut theorem (14.2)

Textbooks:
  1. Graph theory with applications to engineering and computer science, Narsingh Deo (Available in IUT Library and Nilkhet)
  2. Introduction to graph theory, Fourth Edition, Robin J. Wilson (PDF available; contact with me) 
  3. Discrete Mathematics and Its Applications, Sixth Edition, Kenneth H. Rosen 
Comments