Course Title : Graph Theory

Code 90300
Course Year
Term 2nd term
Class day & Period
Location
Credits 2
Restriction
Lecture Form(s) Lecture
Language
Instructor Shuichi Miyazaki

Course Description

We learn basic theories of graphs and their applications, and fundamental algorithms for solving graph problems.

Grading

Mainly evaluated by the final exam. Exercises and discussions in class may be considered.

Course Goals

The goal of this course is to learn basic theories of graphs and their applications, and fundamental algorithms for solving graph problems.

Course Topics

Theme Class number of times Description
Graphs and algorithm 3 I explain definition of graphs and basic properties of graphs. I also briefly review the basics of algorithms and their complexity.
Minimum spanning trees 2 Kruskal's algorithm, Prim's algorithm, Steiner tree problem.
Shortest path problems 1 Dijkstra's algorithm
Hamilton circuit problem 2 Hamilton cycle, Euler cycle, Dirac's theorem.
Coloring problems 2 Vertex coloring, edge coloring.
Maximum flow problems 2 Ford-Fulkerson's algorithm.
Matching 2 Hall's theorem, Hungarian method.
Exam 1

Textbook

No specification.

Textbook(supplemental)

I show some recommended books in class.

Prerequisite(s)

Web Sites

Additional Information