| １． |
Outline |
|
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.).
|
| ２． |
Objectives |
|
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.
|
| ３． |
Grading Policy |
|
Students are evaluated by a term examination, some midterm examinations, and some quizzes.
|
| ４． |
Textbook and Reference |
|
No textbook or reference. The original slides and video contents are used.
|
| ５． |
Requirements (Assignments) |
|
The slides of the lecture should be read. The video contents of the lecture should be viewed.
|
| ６． |
Note |
|
LMS is used in this course.
|
| ７． |
Schedule |
|
１. Introduction: Outline of graph theory and its applications.
|
２. Basic concepts of graph: Definitions of technical terms in graph theory.
|
３. Connected graph (1): Eulerian graph. Euler's theorem.
|
４. Connected graph (2): Hamiltonian graph. Ore's theorem. Dirac's theorem.
|
５. Tree: Spanning tree. Cayley's theorem.
|
| ６. Planar graph (1): Kuratowski's theorem. Euler's formula. |
７. Planar graph (2): Dual graph. Graph on curved surfaces.
|
８. Infinite graph: Konig's lemma. Midterm examination.
|
９. 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.
|
|
| １． |
Outline |
|
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.).
|
| ２． |
Objectives |
|
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.
|
| ３． |
Grading Policy |
|
Students are evaluated by a term examination, some midterm examinations, and some quizzes.
|
| ４． |
Textbook and Reference |
|
No textbook or reference. The original slides and video contents are used.
|
| ５． |
Requirements (Assignments) |
|
The slides of the lecture should be read. The video contents of the lecture should be viewed.
|
| ６． |
Note |
|
LMS is used in this course.
|
| ７． |
Schedule |
|
１. Introduction: Outline of graph theory and its applications.
|
２. Basic concepts of graph: Definitions of technical terms in graph theory.
|
３. Connected graph (1): Eulerian graph. Euler's theorem.
|
４. Connected graph (2): Hamiltonian graph. Ore's theorem. Dirac's theorem.
|
５. Tree: Spanning tree. Cayley's theorem.
|
| ６. Planar graph (1): Kuratowski's theorem. Euler's formula. |
７. Planar graph (2): Dual graph. Graph on curved surfaces.
|
８. Infinite graph: Konig's lemma. Midterm examination.
|
９. 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.
|
|
|