| Teachers | KAMIDE, Norihiro | |
|---|---|---|
| Grade, Semester | Year 2 I/III [Department of Information Science Correspondence Course, Faculty of Science and Engineering] | |
| Category | Basic Major Subjects | |
| Classes | メディア授業 | |
| Elective, Credits | Elective 2credit | |
| Syllabus Number | 4B203 | |
In this course, basic graph theory in computer science is explained. The contents of the lectures are summarized as follows: (1) types of graphs (connected graph, planar graph, directed graph, network, etc.), (2) properties of graphs (connectivity, cyclicity, planarity, colorability, etc.), and (3) basic theorems in graph theory (Kuratowski's theorem, four color theorem, max-flow min-cut theorem, Menger's theorem, etc.).
The aim of this course is to understand the following items: (1) basic concepts of graphs, (2) types of graphs, (3) properties of graphs and (4) basic theorems in graph theory.
Students are evaluated by a term examination, some midterm examinations, and some quizzes.
| Kind | Title | Author | Publisher |
|---|---|---|---|
| Textbook | No textbook. The original slides and video contents are used. | ||
| References | No reference. The original slides and video contents are used. |
The slides of the lecture should be read. The video contents of the lecture should be viewed.
LMS is used in this course.
| 1 | Introduction: Outline of graph theory and its applications. |
| 2 | Basic concepts of graph: Definitions of technical terms in graph theory. |
| 3 | Connected graph (1): Eulerian graph. Euler's theorem. |
| 4 | Connected graph (2): Hamiltonian graph. Ore's theorem. Dirac's theorem. |
| 5 | Tree: Spanning tree. Cayley's theorem. |
| 6 | Planar graph (1): Kuratowski's theorem. Euler's formula. |
| 7 | Planar graph (2): Dual graph. Graph on curved surfaces. |
| 8 | Infinite graph: Konig's lemma. Midterm examination. |
| 9 | Coloring Problem (1): Vertex coloring. Face coloring. Four color theorem. |
| 10 | Coloring Problem (2): Edge coloring. Chromatic polynomial. |
| 11 | Directed graph (1): Strong orientation. Eulerian orientation. |
| 12 | Directed graph (2): Network. Flow. Max-flow min-cut theorem. |
| 13 | Hall's theorem: Bipartite graph. Hall's marriage theorem. |
| 14 | Menger's theorem: Menger's theorem. Relation to other theorems. |
| 15 | Advanced topics: Computational geometry. Term examination. |
