“Super useful” mathematics born from the exploration of one-stroke writing!
Postal delivery, traffic control, infrastructure development, work assignments, mazes and Sudoku puzzle solving… Do you know the mathematical “graph theory” that is applied in every aspect of everyday life? It is also an indispensable weapon for cutting-edge research that forms the basis of generative AI, such as data science and machine learning.
Graph theory, which is an important theme in modern mathematics, is explained in “Graph Theory”, which can be understood from zero knowledge with abundant concrete examples.Introduction to graph theory “super” New mathematics born from Euler’s ideas” (Kodansha Bluebacks). In this article series, we will carefully select interesting topics covered in this book, such as the “traveling salesman problem” to find a business route in the shortest time, and the “traffic control problem” to reduce accidents on one-way streets.
This time, let’s explain what graph theory is, using the combination of sports and other matches as an example.
*This article is based on “Introduction to graph theory “super” New mathematics born from Euler’s ideas” (Bluebacks) has been reconstructed and re-edited.
“Graph theory” based on match combinations
「graph theoryWhat does that mean?
In order to understand the basic idea, let’s start by explaining the situation by using the situation of “setting up a match” in sports as an example to get a general idea.
There are many sports competitions in which two players or teams compete, such as table tennis, badminton, soccer, and baseball. Here we will take tennis as an example and think about match combinations. Please note that there will be no competition between the same people.
Five players (A, B, C, D, E) play tennis.
- Can everyone play a match with 4 people?
- Can everyone play a match with 3 people?
- Can everyone play a match with two people?
It takes a lot of effort to think about these kinds of problems one by one while building a match.
On the other hand, you can get answers more easily by using diagrams called “graphs.” So, what is a “graph”?
“Vertex”, “Edge” and “Degree”
A “graph” in graph theory consists of several “vertex” and connecting those vertices with “side”.
In addition, the number of edges coming out from a vertex can be calculated as “frequency”.
Generally speaking, when we think of graphs, we think of graphs of straight lines or curves drawn on the xy plane, but graph theory graphs are different from graphs of these functions, so they are sometimes called “discrete graphs.”
In the case of this problem, consider the five “people” as the vertices, the “games” as the edges, and the “number of games” played by a person as the degree. Then, if you can draw a graph under each of the conditions 1. to 3., you can actually set up a match, and conversely, if you can set up a match, you can draw a graph.
| Match combination | graph |
| people | vertex |
| Number of matches | side |
| number of matches played by a person | frequency |
You can set up a match ←→ You can draw a graph
Try testing under conditions 1. to 3.
1.The following figure“Diagram the match combinations”Match combinations like the graph shown on the left are possible. A and B, A and C, A and D, A and E, B and C, B and D, B and E, C and D, C and E, and D and E will play against each other, for a total of 10 games.
This number of matches matches the number of edges, 10.
2. For the reasons explained below, it is not possible to realize a match combination that meets the conditions.
3. Match combinations as shown in the graphs shown in the center and right of the following figure are possible. In the center graph, A and B, B and C, C and D, D and E, and E and A play each other, and in the right graph, A and B, B and E, E and D, D and C, and C and A play each other, for a total of 5 games each.
Similar to 1., this number of matches matches the number of edges, which is 5.
