Catalog Description: Building blocks of a graph, trees, connectivity, matchings, coverings, planarity, NP-complete problems, random graphs, and expander graphs; various applications and algorithms.
Course Content (more "descriptive" than the official Catalog Description): Many real-world situations are conveniently described by diagrams consisting of a collection of nodes together with lines or arrows connecting certain pairs of those nodes, notable examples being transport or communication networks. A mathematical abstraction of this type of setting is called a graph. The present course will study basic concepts, properties and applications of graphs. This will include a discussion of several classical questions such as the Minimum Spanning Tree Problem, the Max-Cut Problem, or the Traveling Salesman Problem. Sample topics: building blocks of a graph, trees, connectivity, graph algorithms, matchings, coverings, planarity, NP-complete problems, random graphs, and expander graphs. 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 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 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 CWRU Network.
Grades: Your Final Grade in the course will be based on
Attendance/Homework/Quizzes/Class Participation (40%),
Midterm Exam (20%, early to mid October) and Final Exam (40%, Thursday, December 14, 12:30-15:00).
Students with special needs should contact
Division of Student Affairs/Disability Resources.
Please keep in mind that accommodations are not retroactive.
Assigments etc: Homework will be assigned weekly and there may be occasional quizzes. A very tentative schedule of assignments can be found here. Finalized assignments, solutions, and other documents will be progressively posted on Canvas.
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. Any substantive collaboration and/or usage of sources or AI tools has to be acknowledged. See CWRU academic integrity policy and Academic Integrity Board