# Syllabus 2014

IMPORTANT

Our syllabus can be seen at the website of KULASIS since 2019.

Common Portal for All Students (Login to KULASIS)

Common Portal for All Students (Login to KULASIS)

## 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.