2020 Faculty Courses School of Engineering Major courses
Graph Theory with Engineering Application
- Academic unit or major
- Major courses
- Instructor(s)
- Shmuel Wimer
- Class Format
- Lecture
- Media-enhanced courses
- -
- Day of week/Period
(Classrooms) - 7-8 Tue (Zoom)
- Class
- -
- Course Code
- XEG.S404
- Number of credits
- 100
- Course offered
- 2020
- Offered quarter
- 4Q
- Syllabus updated
- Jul 10, 2025
- Language
- English
Syllabus
Course overview and goals
Graph theory results are widely used to model and solve many engineering, social and natural science problem; it is also an excellent mean to explore proof techniques in discrete mathematics. This course aims at introducing basic graph theory concepts, and it demonstrates how they can be used in facing real-life modeling and design problem.
Course description and aims
The main goal of this course is to equip the students with graph theory “state of mind” in facing engineering problems. The students will acquire graph theory basic knowledge and will experiencing solutions to some common problems, which will direct them towards utilizing analytical approach in their R&D challenges, in addition to simulation and experiments, which are commonly used in R&D.
Keywords
Graph theory, Algorithms, Complexity, Linear algebra, Combinatorics, and Probability
Competencies
- Specialist skills
- Intercultural skills
- Communication skills
- Critical thinking skills
- Practical and/or problem-solving skills
Class flow
This course aims at introducing basic graph theory concepts, and it demonstrates how they can be used in facing real-life modeling and design problem. Its approach it a mix of formal and intuition, where no previous knowledge in graph theory is assumed. There will be formal proofs of some important theorems (though few), while others will only be overviewed. Algorithms and complexity will only be briefly discussed as those are widely covered in other courses. Each of the topics will demonstrate related practical problems.
Course schedule/Objectives
| Course schedule | Objectives | |
|---|---|---|
| Class 1 | Matching | Maximum matching, bipartite graphs, perfect matching, matching algorithms. |
| Class 2 | Graph coloring | Vertex coloring, the chromatic number, perfect graphs, map coloring, edge coloring. |
| Class 3 | Connectivity | Vertex connectivity, edge connectivity, 3-connected graphs. |
| Class 4 | Cliques and independent sets | Shannon capacity, Turán’s theorem, Ramsey’s theorem. |
| Class 5 | The probabilistic method | Random graphs, expectation, variance, evolution of random graphs. |
| Class 6 | Planar graphs | JDuality, Euler formula, bridges, planarity recognition, the four-color problem. |
| Class 7 | Electrical networks | Circulations and tensions, the matrix-tree theorem, resistive electrical networks, perfect squares, random walks on graphs. |
Study advice (preparation and review)
To enhance effective learning, students are encouraged to spend approximately 100 minutes preparing for class and another 100 minutes reviewing class content afterwards (including assignments) for each class.
They should do so by referring to textbooks and other course material.
Textbook(s)
None
Reference books, course materials, etc.
All lectures slides will be available on-line.
J.A. Bondy and U.S.R. Murty, Graph Theory, Springer.
D.B. West, Introduction to Graph Theory, Prectice-Hall.
Evaluation methods and criteria
Learning achievement is evaluated by the quality of the written reports, exercise problems, and etc.
Related courses
- XEG.S405 ： Topics in Digital VLSI Design
- XEG.S605 ： Advanced Topics in Digital VLSI Design
Prerequisites
Students are supposed to have some background in algorithms, basic knowledge of linear algebra, combinatorics and probability.
Contact information (e-mail and phone) Notice : Please replace from ”[at]” to ”@”(half-width character).
atsushi [at] ict.e.titech.ac.jp
Office hours
Contact by e-mail in advance to schedule an appointment