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.
There will be an emphasis on extremal results and a variety of methods.
- Matchings and Factors in Graphs
- Graph Connectivity
- Planar graphs and the four-color-map theorem
- Hamiltonian cycles
| 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 |
| term papers | Total. | |
|---|---|---|
| 1. | 25% | 25% |
| 2. | 25% | 25% |
| 3. | 25% | 25% |
| 4. | 25% | 25% |
| Total. | 100% | - |
Proof techniques such as mathematical induction and reduction to the absurd are required.
- Wednesday,18:00-19:00
I encourage you to come to my office to discuss graph problems.
- Course that cultivates an ability for utilizing knowledge
- Course that cultivates a basic problem-solving skills
| Work experience | Work experience and relevance to the course content if applicatable |
|---|---|
| N/A | N/A |
Last modified : Thu Mar 21 15:39:33 JST 2019