Catalog Description: Building blocks of a graph, trees, connectivity, matchings, coverings, planarity, NP-complete problems, random graphs, and expander graphs; various applications and algorithms.
The audience: The course is primarily directed towards advanced undergraduate or graduate students in mathematics, computer science or operation research, but it can also be a fun class for any student generally interested in mathematics and familiar with basics of linear algebra.
The subject: Many real-world situations are conveniently described by diagrams consisting of a collection of points (nodes) together with lines or arrows connecting certain pairs of those points (edges). Obvious examples include transport or communication networks, but there are many more. A mathematical abstraction of this type of situation is called a graph. Graph Theory, besides being an important branch of Mathematics on its own right, is of paramount importance in areas such as Computer Science or Operations Research, particularly in the context of the so-called Combinatorial Optimization.
The topics: We will cover most of the first four chapters from the textbook and a selection of topics from the remaining chapters. Additional topics may include graph Laplacians and expander graphs.
Computing: Even though the topic of the course is closely related to computing and algorithms, there will be no major computational component in the coursework. However, some topics/problems may be most easily approached/solved using software packages such as Mathematica or Matlab, available through CWRUnet.
Grades: Your Final Grade in the course will be based on
Attendance/Homework/Class Participation (40%),
Midterm Exam (20%) and Final Exam (40%).
Students with special needs should contact Educational Services for Students.
Integrity: It is OK (and indeed encouraged) to discuss homework assignments with fellow students. However, any submitted work must be your own. Merely copying someone else's work is unethical, a waste of time, and may be penalized. (This includes copying solutions found on the internet.) See CWRU academic integrity policy.