Show The Graduate Center Menu
 
 

Graph Theory

Instructor: Professor Louis Petingi


Course Description

Graph theory has been applied to several areas of physics, chemistry, communication science, biology, electrical engineering, operations research, psychology, linguistics, among others fields, to solve problems that can be modelled as discrete objects called graphs.

Graph theory is intimately related to different branches of mathematics including group theory, matrix theory, numerical analysis, probability, topology, and combinatorics. Even though some of the problems in graph theory can be described in an elementary way, many of these problems represent a challenge to many researchers in mathematics.

The purpose of this course is two-fold: we will formally study fundamental concepts in graph theory such as flows and connectivity (e.g., Menger’s theorem), planarity (coloring), Eulerian and Hamiltonian graphs, and reliability theory; from an applications point of view students we will be able to measure performance objectives of communications networks modeled as probabilistic networks via network reliability theory, by incorporating previous theoretical knowledge acquired during the course.

Students will be also exposed to discrete probability theory and basic information theory tailored to evaluate the failure probability of communication channels in wireless networks, modelled as probabilistic graphs.  Some programming projects will be assigned to students to evaluate the reliability of existing communication networks. This course is envisioned as a first graduate level course to encourage students to pursue further research in graph theory.


Reading material

  • Textbook: Graph Theory (Graduate Texts in Mathematics), Authors: J. A. Bondy, and U.S.R. Murty, Springer-Verlag, 2008, ISBN: 978-1-84628-969-9

  • Research papers in Reliability Theory (A. Satyanarayana, F. Boesch, C. Suffel, L. Petingi) to be handed-out to students.


Exams

  • Midterm 30%

  • Final 30%

  • Homework/Programming Projects 30%

  • Class Participation 10%


Content

  • PART I (Graph Theory Fundamentals)

    • Week 1: Fundamentals

      • Graphs.

      • Subgraphs.

      • Connected graphs.

      • Trees.

      • Homework assignment.

    • Weeks 2-3: Flows and Connectivity

      • Non-separable graphs.

      • Flows in networks.

      • Connectivity

        • Edge-connectivity.

        • Vertex-connectivity.

      • Homework assignment.

    • Week 4: Graph Representation and Algorithms.

      • Adjacency matrix.

      • Adjacency-linked lists.

      • Definition of Class Graph.

      • Dijkstra's Shortest Path Algorithm (DSPA).

      • Programming Assignment. Implement DSPA in C++ representing graphs as adjacency-linked lists data-structures. This procedure will be used later in the course in conjunction with other programs to implement reliability algorithms.

    • Week 5:  Planarity and the Four-Colour Problem. Homework assignment.

    • Weeks 6-7: Independent Sets and Cliques, Matching, Eulerian and Hamiltonian Cycles. Homework assignment.

    • Week 8: Vertex-Covers, and Dominating-Sets. Homework assignment.

    • Week 9: Midterm.

  • PART II (Network Reliability Models) Handouts will be distributed to students.

    • Weeks 9-10: Classical Network Reliability measures (edge and vertex case)

      • Probabilistic networks vs. binary networks.

      • Networks modelled as undirected graphs (all-terminal, K-terminal, and source-terminal reliability measures).

      • Networks modelled as directed graphs (source-to-all-terminal, and source-to-K-terminal reliability)

      • Computational Complexity of exact methods of evaluation and Monte Carlo estimation of the reliability.

      • Programming assignment. Exact evaluation of the reliability using subroutines developed during weeks 4 and 5.

    • Weeks 11-12:  K-terminal-to-sink (KTS) reliability derived from the classical reliability.

      • Applications of the KTS to assess performance objectives of sensor networks.

      • Information theory models to assess the reliability (functional probability) of links representing communication channels in wireless networks.

      • Programming assignment. Implementation of the KTS using a crude Monte Carlo approach applied to evaluate performance objectives of sensor networks.

    • Weeks 13-14: Discussion of benefits of using KTS to evaluate performance objectives of sensor networks modeled as probabilistic networks vs. current methodologies (dominating-sets) and representation of wireless networks (binary networks). Open problems.

    • Week 15: Final


Learning Objectives

Learning Objectives How Objectives Can be Met

Students will be able to formally apply graph-theoretic terminology and notation. Even though most students conceptually understand graph theory, they have a hard time with definitions.

Homework assignments, midterm, and final.

Students will be able to formally understand and prove theorems/lemmas and relevant results in graph theory.

Class participation, homework assignments, midterm and final.

Students will be able to apply theoretical knowledge acquired to solve realistic problems in real life. Applicability of theoretical concepts to address network design problems.

Thru class participation (and internet research), students will be asked to address network design problems (e.g., VLSI design using planarity concepts, GPS technology based on Dijkstra's SPA).

Hands-on implementation of algorithms to evaluate the reliability of given networks by applications of programming techniques (e.g., MC, Dijkstra's SPA) and theoretical background (e.g., connectivity, probability, and information theory).

Programming assignments.

Students will be aware of the benefits of representing networks as probabilistic graphs vs. the traditional binary representation. Also they will learn about open problems in reliability theory.

Discussion weeks 13-14