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, which are the two cornerstones of discrete mathematics.
The course provides an introduction to graph theory and combinatorics, which are the two cornerstones of discrete mathematics.
- To understand matchings and factors in graphs
- To understand a graph connectivity
- To understand planar graphs and the four-color-map theorem
- To understand Hamiltonian cycles
| term papers | Solving problems | Total. | |
|---|---|---|---|
| 1. | 20% | 5% | 25% |
| 2. | 20% | 5% | 25% |
| 3. | 20% | 5% | 25% |
| 4. | 20% | 5% | 25% |
| Total. | 80% | 20% | - |
| Class schedule | HW assignments (Including preparation and review of the class.) | Amount of Time Required | |
|---|---|---|---|
| 1． | Basics on graphs（a degree, a path, and a cycle） | Check this syllabus | 20minutes |
| Confirm the definitions of degree, path and cycle. | 70minutes | ||
| Solve problems given in class. | 100minutes | ||
| 2． | Basics on graphs（a connectivity, a tree，a forest, bipartite graphs） | Confirm the definitions of connectivity, tree，forest, bipartite，contraction and minor. | 90minutes |
| Solve problems given in class. | 100minutes | ||
| 3． | Matching in bipartite graphs | Confirm the definition of matching. | 90minutes |
| Solve problems given in class. | 100minutes | ||
| 4． | Matching in general graphs | Confirm the definition of matching. | 90minutes |
| Solve problems given in class. | 100minutes | ||
| Consider the unsolved problems expected from the theorems in Section 2.1 - 2.3 of the textbook. | 60minutes | ||
| 5． | Tree of graphs and the structures | Confirm the definition of tree. | 90minutes |
| Solve problems given in class. | 100minutes | ||
| 6． | Fundamental concepts of planar graphs | Confirm the definitions of planar graph. | 90minutes |
| Solve problems given in class. | 100minutes | ||
| 7． | Some theorems on planar graphs | Confirm the definition of plane graph. | 90minutes |
| Solve problems given in class. | 100minutes | ||
| 8． | Graph colorings | Confirm the definitions of coloring. | 90minutes |
| Solve problems given in class. | 100minutes | ||
| 9． | The four-color-map theorem and the incomplete proof by Kempe. | Confirm the four-color-map theorem. | 90minutes |
| Investigate the counterexample by Heawood. | 100minutes | ||
| Investigate the modified results of Melzak's algorithm. | 70minutes | ||
| 10． | The four-color-map theorem | Confirm the definition of graph minor. | 90minutes |
| Solve problems given in class. | 100minutes | ||
| 11． | Euler graph and the structure | Confirm the definitions of an Euler graph. | 90minutes |
| Solve problems given in class. | 100minutes | ||
| 12． | Hamiltonian cycle | Confirm the definition of a Hamiltonian cycle. | 90minutes |
| Solve problems given in class. | 100minutes | ||
| 13． | Application of Hamiltonian cycle, in particular, Traveling salesperson problem | Confirm what is a Traveling salesperson problem. | 90minutes |
| Solve problems given in class. | 100minutes | ||
| 14． | Consideration of engineering applications of graphs | Confirm a Traveling salesperson problem. | 100minutes |
| P and NP in the theory of computation should be investigated. | 90minutes | ||
| Total. | - | - | 2790minutes |
The assignment will be conducted four times, and a score of 60 percent or more of the total score will be considered passing.
The criterion for passing the exam (60 points) is that the student should be able to correctly perform "selection of applicable methods" and "calculation to arrive at a solution" for each of the assignments on the fundamentals of graph theory and its applications.
The criterion for passing the exam (60 points) is that the student should be able to correctly perform "selection of applicable methods" and "calculation to arrive at a solution" for each of the assignments on the fundamentals of graph theory and its applications.
| ways of feedback | specific contents about "Other" |
|---|---|
| The Others | 初回の授業で紹介する。 |
Proof techniques such as mathematical induction and reduction to the absurd are required.
- 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 applicable |
|---|---|
| N/A | N/A |
Last modified : Wed Feb 12 04:09:07 JST 2025