Graphs and Networks

Course Purpose
The students will understand the mathematical properties and fundamental algorithms on graph theory/network theory, which are used as various mathematical models in information science and the real world.
Learning Goals
The learning goals in this course are to understand the basic terminology and properties of graphs, to represent required problems using graphs, and to use algorithms for graphs to solve various problems.
Topic
Session 1Basic terms in graph theory
Session 2Connectivity and trees
Session 3Euler paths and Hamiltonian cycles
Session 4Directed graphs and search trees
Session 5Minimum spanning trees and their algorithms
Session 6Shortest path and its algorithms
Session 7Graph connectivity
Session 8Networks and flows
Session 9Matchings in bipartite graphs
Session 10Matchings in general graphs
Session 11Maximum weight matching and linear programming problems
Session 12Plane graphs
Session 13Graph coloring and the four-color problem
Session 14Ramsey theory
Session 15Regular exams
＊＊This content is based on April 1, 2025. For the latest syllabus information and details, please check the syllabus information inquiry page provided by the university.＊＊