Graph Theory
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
Content
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
|