Course title
6M008200
Graph Theory

 matsuda haruhide
Course content
The course aims to introduce students to discrete mathematics, a fundamental part of mathematics with many applications in computer science and related areas. The course provides an introduction to graph theory and combinatorics, the two cornerstones of discrete mathematics.
There will be an emphasis on extremal results and a variety of methods.
Purpose of class
To learn Graph Theory and its applications
Goals and objectives
  1. Matchings and Factors in Graphs
  2. Graph Connectivity
  3. Planar graphs and the four-color-map theorem
  4. Hamiltonian cycles
Language
Japanese(English accepted)
Class schedule

 Class schedule HW assignments (Including preparation and review of the class.) Amount of Time Required
1． Basics on graphs（degree, path, and cycle） Check this syllabus 10minutes
Confirm the definitions of degree, path and cycle. 70minutes
Solve problems that I asked in class. 100minutes
2． Basics on graphs（connectivity, tree，forest, bipartite，contraction and minor） Confirm the definitions of connectivity, tree，forest, bipartite，contraction and minor. 90minutes
Solve problems that I asked in class. 100minutes
3． Matching in bipartite graphs Confirm the definition of matching. 90minutes
Solve problems that I asked in class. 100minutes
4． Matching in general graphs Confirm the definition of matching. 90minutes
Solve problems that I asked in class. 100minutes
5． Tree of Graphs and the structures Confirm the definition of tree. 90minutes
Solve problems that I asked in class. 100minutes
6． Fundamental concepts of planar graphs Confirm the definitions of planar graph. 90minutes
Solve problems that I asked in class. 100minutes
7． Some theorems on planar grasphs Confirm the definition of plane graph. 90minutes
Solve problems that I asked in class. 100minutes
8． Graph colorings Confirm the definitions of coloring. 90minutes
Solve problems that I asked in class. 100minutes
9． The four-color-map theorem and the incomplete proof by Kempe. Confirm the counterexample of Kempe. 90minutes
Solve problems that I asked in class. 100minutes
10． The four-color-map theorem and graph minor Confirm the definition of graph minor. 90minutes
Solve problems that I asked in class. 100minutes
11． Euler graph and its structure Confirm the definitions of an Euler graph. 90minutes
Solve problems that I asked in class. 100minutes
12． Hamiltonian cycle Confirm the definition of a Hamiltonian cycle. 90minutes
Solve problems that I asked in class. 100minutes
13． Application of Hamiltonian cycle, in particular, Traveling salesperson problem Confirm what is a Traveling salesperson problem. 90minutes
Solve problems that I asked in class. 100minutes
14． Trees of graphs Confirm the definition of tree. 90minutes
Solve problems that I asked in class. 100minutes
Total. - - 2650minutes
Relationship between 'Goals and Objectives' and 'Course Outcomes'

 term papers Total.
1. 25% 25%
2. 25% 25%
3. 25% 25%
4. 25% 25%
Total. 100% -
Evaluation method and criteria
term papers
Textbooks and reference materials
Reference materials: Graph Theory, R. Diestel, Springer
Prerequisites
Proof techniques such as mathematical induction and reduction to the absurd are required.
Office hours and How to contact professors for questions
  • Wednesday,18:00-19:00
    I encourage you to come to my office to discuss graph problems.
Relation to the environment
Non-environment-related course
Regionally-oriented
Non-regionally-oriented course
Development of social and professional independence
  • Course that cultivates an ability for utilizing knowledge
  • Course that cultivates a basic problem-solving skills
Active-learning course
About half of the classes are interactive
Last modified : Wed Oct 17 07:54:27 JST 2018