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

 Midterm Final Assignment Total 30% 50% 20% 100%

 4. Instructor

Name 