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 | ||
| For a set with integer distances, summarize the difference between a finite number of point sets and infinite number of point sets. | 70minutes | ||
| 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 | ||
| 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 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 | ||
| Confirm the difference between art gallery problems and fortress problems. | 70minutes | ||
| 7． | Some theorems on planar grasphs | Confirm the definition of plane graph. | 90minutes |
| Solve problems that I asked in class. | 100minutes | ||
| Confirm the difference between art gallery problems, fortress problems, and gard-person problems. | 70minutes | ||
| 8． | Graph colorings | Confirm the definitions of coloring. | 90minutes |
| Solve problems that I asked in class. | 100minutes | ||
| Confirm the difference between the minimum spanning tree problem and the Steiner problem. | 70minutes | ||
| 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 | ||
| Investigate the modified results of Melzak's algorithm. | 70minutes | ||
| 10． | The four-color-map theorem and graph minor | Confirm the definition of graph minor. | 90minutes |
| Solve problems that I asked in class. | 100minutes | ||
| Summarize the packing method the unit circle in the 3 * 1000 area. | 60minutes | ||
| 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 | ||
| Solve the problem on page 154. | 60minutes | ||
| Total. | - | - | 3180minutes |
| term papers | Solve exercises | Total. | |
|---|---|---|---|
| 1. | 20% | 5% | 25% |
| 2. | 20% | 5% | 25% |
| 3. | 20% | 5% | 25% |
| 4. | 20% | 5% | 25% |
| Total. | 80% | 20% | - |
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 : Sun Mar 21 16:30:13 JST 2021