TOP

Graph and Network Theory

Autumn 2005

Tuesday 13:30 ~ 16:30

Electronic & Information Building  #217

last updated: 2005/12/01

1. Objectives

This course introduces Graph Theory to develop in students capability of modeling real world problems using graphs and solve them by using graph algorithms. In addition the course develops intuitive ideas in students to solve problems.

 

By the end of the course, students will be able to:

  • learn graph-theoretic concepts and important theorems and results.
  • learn how to formulate and model problems using graphs.
  • solve problems using graph algorithms.
  • learn examples of application of graph theory to computer problems.

 

In addition, students will be required to solve exercises in groups in order to inspire interaction and brainstorming for reaching a destination.

 

The course covers the following topics:

Fundamental Concepts:  what is a graph,  paths, cycles, trails, Bipartite graphs, Eulerian circuits, degrees and counting, Extremal problems, graphics sequences  Directed graphs: Eulerian digraphs, tournaments

 

Trees and Distances:  properties of trees, distances and disjoint trees, spanning trees and enumerations, spanning trees in graphs

 

Optimization and Trees: minimum spanning trees, shortest paths, trees in computer science, other spanning trees

 

Matchings and Covers: maximum matching, Hall’s matching condition,  min-

max theorems, independent sets and covers, dominating sets.

 

Algorithms and Applications: Maximum bipartite matching, weighted bipartite matching, stable matching, faster bipartite matching(optional)

 

Matching in General Graphs: Tutte’s 1-factor theorem, f-factors of a graph(optional), Edmond’s blossom algorithm

 

Connectivity and Paths: cuts and connectivity, k-connected graphs, applications of Menger’s theorem

 

Network Flow problems:  Maximum network flow, integral flows, supplies and demands(optional)

 

Colouring of Graphs, Planar Graphs: embeddings and Euler formula, characterization of planar graphs, parameters of planarity

 

Edges and Cycles: Line graphs, Hamiltonian cycles, planarity, colouring and cycles

 

Matroids: Hereditary systems, properties of matroids span function, dual of a matroid, matriod intersection, matroid union

 

Ramsey Theory: Pigeonhole principle, Ramsey’s theorem, Ramsey number, Graph Ramsey Theory

 

Eigenvalues of graphs: characteristic polynomial, linear algebra of real matrix, eigenvalues and graph parameters, eigenvalues of regular parameters

 

Recapitulation of the material and Open problems.

 

2. Textbooks

Recommended Book: Introduction to Graph Theory second Edition Douglas B WEST Pearson Asia Edition, 2002

Introduction to Graph Theory (Dover Books on Advanced Mathematics) by Richard J. Trudeau

Introduction to Graph Theory (4th Edition) by Robin J. Wilson

 

3. Grading Police

Midterm

Final

Assignment

Total

30%

50%

20%

100%

 

4. Instructor

Name

Mohammad Kaykobad (Bangladesh)

Contact Information

Tehephone : 031-201-2493
E-mail :

mkbd@oslab.khu.ac.kr

or kaykobad@gmail.com

Office :

Electronic & Information Bld. #B08

(Multimedia Laboratory)

    

5. Tentative Schedule

#

Date

(month/day)

Topic

Material

1

9/6

Fundamental Concepts:  History of graph theory, graph,  paths, cycles, trails

DOC

2

9/13

Bipartite graphs, Eulerian circuits, degrees and counting

DOC

3

9/20

Extremal problems, graphics sequences  Directed graphs: Eulerian digraphs, tournaments, Trees and Distances:  properties of trees, distances, radius, diameter                                         

DOC

4

9/27

Distances and disjoint trees, spanning trees and enumerations, spanning trees in graphs

DOC

5

10/4

Colloquium I

Minimum Spanning Trees and Majority Spanning Trees and Cotrees

DOC

PPT(11/21)

6

 

Algorithms for Majority Spanning Trees and Shortest paths

 

7

10/11

Matchings and Covers: maximum matching, Hall’s matching condition,  min-max theorems, independent sets and covers, dominating sets.

DOC

8

10/18

Algorithms and Applications: Maximum bipartite matching, weighted bipartite matching

DOC

9

10/25

MIDTERM EXAM

DOC

10

Colloquium II

Huffman and Dynamic Huffman Trees and Variations

 

11

11/1

Matching in General Graphs: Tutte’s 1-factor theorem, f-factors of a graph(optional), Edmond’s blossom algorithm

DOC

12

11/8

Network Flow problems:  Maximum network flow, integral flows, supplies and demands(optional)

DOC

13

11/15

Colouring of Graphs, Planar Graphs: embeddings and Euler formula, characterization of planar graphs, parameters of planarity

DOC

(modified:12/1)

14

11/22

Colloquium III

Hamiltonian paths and Cycles: New conditions for Hamiltonicity

PPT

(modified:12/1)

15

11/22

Edges and Cycles: Line graphs, Hamiltonian cycles, planarity, colouring and cycles

DOC

16

11/29

Matroids: Hereditary systems, properties of matroids span function, dual of a matroid, matroid intersection, matroid union

DOC

17

12/6

Ramsey Theory and Recapitulation of the course material and Open problems

DOC

18

12/13

FINAL EXAM

-

 topicon.gif