This page shows some corrected exercises on graph and tree modeling. The purpose of these exercises is to learn how to model a problem using the concepts and basics of graph theory. The majority of the problems presented are also solvable simplices with the classical method.
Exercise 1
Two players have 2 or more sets of matches. Each turn, the next player can remove a certain number of matches from a batch (depending on the chosen rule). The player who removes the last match loses.
Model this game with a graph in the case where there are two stacks each containing three matches, and where a player can remove one or two matches each.
What move must the first player make to win the game?
The graph should be read from left to right. A player starts on node 3.3 and each move takes the path from one edge to another node. The player reaching 0.0 loses.
If player 1 plays, he has won if the set of paths to 0.0 is of odd size, which is never the case, there is no automatically winning strategy.
Exercise 2
The following graphic shows the corridors of a museum. A guard placed in a corridor can monitor two junctions placed at its ends. How many guards are needed (and how should they be placed) so that all intersections are guarded?
If we now place guards at intersections, assuming one guard can monitor all the hallways leading to that intersection, how many guards are needed?
Each guard will be placed on an edge and can monitor two intersections (vertices). The graph has 11 vertices; at least six guards will be needed. It is therefore necessary to find a (minimum) set of at least six edges, such that each vertex is incident to at least one of these edges. The graph below provides a solution (thicker edges).
This time, the guards are at the tops and watching the ridges. There must be a set of vertices such that every edge is incident to at least one of these vertices. The graph below provides a solution using 6 vertices (white vertices).
Exercise 3
Skynet is a network with 15 vertices. You can go from each vertex to at least seven other vertices per link. Can we go by link from one vertex X to each of the others?
Let A be any vertex. X is linked to at least 7 different cities. So we have a network of 8 vertices connected by links. Within a vertex, you can also connect to at least seven other vertices; so there is a new network of 8 vertices. There must be a shared vertex in these networks, otherwise the network would have at least 16 vertices. X is connected to A in at most two planes, by this common vertex; it is connected to all the other cities.
Exercise 4
A network is made up of seven factories. A city is linked to exactly two factories. Two factories share exactly one city. How many cities are served by the network?
The factories are the vertices and the cities are represented by an edge connecting two vertices. Rule 2 implies that there are no multiple edges and that any pair of vertices are adjacent; that is, the graph is complete; it is K7, complete graph of 7 vertices, that is 21 links.
Exercise 5
Let's consider it linear program next :
Where X is 0 or 1. Determine, with a graph problem, a solution that maximizes the objective function (sum of the Xs).
A vertex represents a variable. Two vertices are connected if they are in the same inequality. The problem is to find a maximum set of vertices where no pair of vertices has a direct link.
Exercise 6
Considering a set of dominoes using the numbers 0, 1, 2, 3, 4, as on each domino comprises two distinct digits, such as 1 and 3, the following problem is proposed: is it possible to line up all the dominoes so that when two pawns "touch" the numbers "in contact" are identical?
Show the problem as a complete graph K5. The problem is to find an Eulerian cycle in the graph.
Exercise 7
In a group of people, there are always two individuals who know exactly the same number of group members. Demonstrate this.
We must prove that in a simple graph (without double edges, without loops), there are always two vertices which have the same degree. We will reason by absurd and suppose that there is a simple graph with n vertices of which all the degrees are different. Then the degrees of the vertices are between 0 and n−1, and therefore if all the degrees are different, as we have n vertices and simply n possibilities for the degrees, all these possibilities must be taken.
In particular, there must be a vertex of degree 0 and a vertex of degree n−1. But it is impossible, because this last vertex should have an edge towards all the others, and it is not possible since a vertex is of degree 0, therefore isolated.
Exercise 8
Let G be a simple undirected graph of order 2p (number of edges). We assume that the degree of each vertex is at least equal to p. Prove that this graph is connected.
Suppose by absurd that this graph is not connected, and let x,y be two vertices such that there is no path linking x to y. Then, x has at least p neighbors, and so does y. But the neighbors of x are necessarily all distinct from the neighbors of y: otherwise, there would exist a chain of length 2 joining x to y.
The graph therefore includes at least 1+1+p+p=2p+2 vertices (x, y, the neighbors of x, the neighbors of y). We therefore obtain a contradiction since the graph is of order 2p.
Exercise 9
A goat, a cabbage and a wolf are on the bank of a river; a smuggler wishes to transport them to the other bank but, his boat being too small, he can only transport one of them at a time. How should he proceed in order never to leave the wolf and the goat, or the goat and the cabbage, together and unattended?
This situation can be modeled using a graph. Let us denote by P the ferryman, by C the goat, by X the cabbage and by L the wolf. The vertices of the graph are pairs specifying who is on the initial edge, who is on the other edge.
Thus, the couple (PCX,L) means that the ferryman is on the initial bank with the goat and the cabbage (which are therefore under surveillance), while the wolf is on the other bank. An edge connects two vertices when the setter can pass from one situation to another.
By transporting the goat, the ferryman passes for example from the top (PCX,L) to the top (X,PCL). The graph thus obtained is bipartite: the vertices for which the setter is on the initial bank are only connected to the vertices for which the setter is on the other bank.
Naturally, we will not consider the vertices of which one of the components is CX or LC because these situations are prohibited. It is then sufficient to find a path (the shortest for example) between the initial situation (PCXL,-) and the desired final situation (-,PCXL). The following figure gives such a path:
Exercise 10
In the following bipartite graph, vertices T1, …, T6 represent workers and vertices E1, …, E6 jobs. An edge connects a worker to a job if the worker has the qualifications for that job. How to assign jobs to workers in order to minimize the number of unemployed?
Assigning a job to a person is like “selecting” an edge. Each person can only hold one job, and a job can only be held by one person, so it is necessary to select a maximum number of edges in such a way that these edges have no common vertex (such a set is called maximum stable).
Exercise 11
Every day, a group of 12 children goes for a walk, in rows of two. How many days can they go for a walk if we don't want a child to have the same neighbor twice? And if now the walk is done in rows of three?
Consider the complete graph K12 with 12 vertices, each vertex representing a child. The number of edges in this graph is 12 x 11 / 2 = 66. A walk corresponds to a set of 6 non-incident edges (having no vertex in common): each edge represents a row (two children) and each child can only belong to one row during a walk.
It is therefore necessary to find the largest number of sets (11 = 66/6) respecting this rule:
1-2, 3-12, 4-11, 5-10, 6-9, 7-8 ; 2-3, 12-4, 11-5, 10-6, 9-7, 8-1 ; 1-3, 4-2, 5-12, 6-11, 7-10, 8-9 ; 3-4, 2-5, 12-6, 11-7, 10-8, 9-1 ; 1-4, 5-3, 6-2, 7-12, 8-11, 9-10 ; 4-5, 3-6, 2-7, 12-8, 11-9, 10-1 ; 1-5, 6-4, 7-3, 8-2, 9-12, 10-11 ; 5-6, 4-7, 3-8, 2-9, 12-10, 11-1 ; 1-6, 7-5, 8-4, 9-3, 10-2, 11-12 ; 6-7, 5-8, 4-9, 3-10, 2-11, 12-1 ; 1-7, 2-12, 3-11, 4-10, 5-9, 6-8
Exercise 12
We are interested in graphs in which all the vertices are of degree three. Construct such graphs having 4 vertices, 5 vertices, 6 vertices, 7 vertices. What do you deduce from this?
Graphs with all vertices of degree three are called 3-regular graphs or cubic graphs. The figure below shows two cubic graphs, having 4 and 6 vertices respectively. Indeed, it is easy to see that there are no cubic graphs with an odd number of vertices: the number of edges of a cubic graph with n vertices is 3n/2 which is integer only when n is even.
Exercise 13
A server can route a maximum of packages at the same time. Seven substations are linked to one server, one substation cannot send parcels if some substations are already using the link. The following table shows each substation's capacity to send a parcel in relation to the others. For example, a parcel from A cannot be sent if there is already a parcel from D but can be sent when B has sent a parcel.
Substation | TO | B | VS | D | E | F | G |
is not with | OF | D, E, F, G | E, G | A, B, E | A, B, C, D, F, G | B, E, G | B, C, E, F |
Represent the links in a graph. How many packets should the server handle at the same time (maximum value)?
Exercise 14
A school must pass written tests to four students: Pierre, Jean, Guillermo and Ibrahim. Seven disciplines are involved: math, physics, biology, French, English, Spanish and history.
Pierre must pass mathematics, physics and English, Jean mathematics, biology and French, Guillermo mathematics, English and Spanish and Ibrahim physics, French and history.
What is the minimum number of time slots to be provided so that no student has to take two tests simultaneously? What is the chromatic number of a complete graph? How to bound chromatic numbers in a graph?
A vertex represents a discipline, an edge connects two disciplines if they cannot take place at the same time. The problem can be solved by looking for a minimum number of colors. The largest complete subgraph is K3, so there are at least 3 colors. The maximum degree is five, so there are at most 5 colors. By experiment, the graph is 3-chromatic.
Exercise 15
The following diagram represents a crossroads.
Each branch has its own traffic light with arrow indication of the authorized direction, and here are the possible crossings of this crossroads.
Cars with a green light must not cross each other, thus AC and BE cannot be authorized simultaneously.
Propose a solution allowing to alternate the authorization of traffic lights in this intersection.
The graph modeling the crossroads is shown below. Its chromatic number is equal to 4 (it is 4-colorable and contains a K4 grouping the vertices AC, BD, CD and DA). A set of vertices of the same color, for example ED, AC, AE and CA groups together a set of paths that can be performed at the same time (no incompatibility).
The chromatic number then corresponds to the minimum number of "cycles" that the traffic lights of this intersection must respect.
For our example, we will have: 1. ED, AC, AE and CA 2. BA, BE, BD and EC 3. DC and DA 4. CD. Other solutions (4-colorations) are of course possible.
Exercise 16
Consider an undirected graph with vertices. Prove that all of the following properties are equivalent:
- is a tree
- is connected and if we remove an edge, the graph is no longer connected
- is connected with n-1 edges
- has no cycle until we add an edge
- has no cycle with n-1 edge
- a single path between any pair of vertices
No solution since it is in the course on trees!
Exercise 17
We want to add a farm in a network. The following graph shows the cost of sending energy between two substations in the network and the amount of energy sent by a substation. You should place the battery in a substation while minimizing the total cost.
Calculate the sum of all costs at each substation, i.e. the cost of each path between any substation and the chosen substation (edge * vertex).
Exercise 18
We are going to see a very important principle in graph theory (related to social issues) which is centrality (there is a lot of centrality calculus).
A robot walks on the graph below. Starting from any vertex s, called the storage vertex, he must drop a cube on each of the other vertices. He has enough cubes on the storage apex, but can only carry one cube at a time (so he must pass through the storage apex before delivering another cube).
Calculate, for each of the vertices of the graph, the minimum path that the robot must cover if this vertex is a storage vertex. What is the "best" storage vertex?
For a given vertex, it is necessary to calculate the sum of the lengths of the shortest paths from this vertex to the other vertices (easy since we are dealing with almost a tree). The following figure gives this value for vertex A, then for all the vertices of the graph. The best storage vertex is therefore vertex X.
Exercise 19
The commissioning of a new mining deposit requires the performance of a certain number of tasks. The following table represents these different tasks with their anteriority relations.
A vertex of a scheduling graph contains 3 elements:
- The name of the task, the earliest completion time and the latest completion time.
- An arc shows the dependency of one task on another with a weighting of the number of days of the previous task. So A and B are linked with a weight of 120.
(instead of an arc it is also possible to make a hierarchical graph, ie the highest vertex is the root, its direct successors are on the next height).
A thin vertex is related to tasks without a successor.
The earliest completion time is the longest path from one task to another in the sense of the hierarchy.
The latest completion time is the shortest path in the opposite direction of the hierarchy.
The critical path is the path from the first task to the end whose earliest and latest times coincide.
Build the scheduling graph.
By using the MPM method, we get the graph below. Earliest and latest dates are calculated "by levels." The critical tasks, and the critical path are indicated in bold. The minimum completion time of the whole can be read on the top FIN: 1170 days.
Exercise 20
A group of 9 students meets every day around a round table. How many days can they meet if we don't want anyone to have the same neighbor twice?
Let us denote by 1,2,…,9 the 9 persons and consider the complete graph K9 with 9 vertices. A composition of the table corresponds to a cycle Hamiltonian of K9 (a cycle passing once and only once through each vertex).
If two table compositions correspond to two cycles having a common edge, it means that the two people connected by this edge are found side by side. Thus, the problem amounts to determining the number of disjoint Hamiltonian cycles of K9.
The graph K9 having 9 x 8 / 2 = 36 edges and each cycle using 9 edges, this number is at most equal to 4… It is effectively equal to 4, as proven by the following 4 disjoint Hamiltonian cycles:
1,2,3,9,4,8,5,7,6 — 1,3,4,2,5,9,6,8,7 — 1,4,5,3,6,1,7,9,8 — 1,5,6,4,7,2,8,1.9
Exercise 21
This time, these daily meetings concern a group of 12 students, 6 girls and 6 boys. We always want no one to have the same neighbor twice, but this time we also want each girl to be surrounded by two boys. How many days can they meet?
The basic idea is the same as for the previous exercise, but this time, due to the imposed girl/boy alternation, we reason on the complete bipartite graph K6,6 (six girls and six boys).
This graph includes 6 x 6 = 36 edges, and each Hamiltonian cycle requires 12 of them. There are therefore at most 3 solutions. In fact, three solutions are indeed possible (fi represents the i-th girl, gi the i-th boy), for example:
( f1,g1,f2,g2,f3,g3,f4,g4,f5,g5,f6,g6) — (f1,g3,f2,g4,f3,g5,f4,g6,f5,g1,f6,g2) —
(f1,g5,f2,g6,f3,g1,f4,g2,f5,g3,f6,g4)
Exercise 22
A group of eight people meet for dinner. The graph opposite specifies the “mood incompatibilities” between the people in this group (an edge connecting two people indicates that they get along very moderately…).
Propose a seating plan (the table is round) for this group, avoiding placing two “incompatible” people side by side.
This time it is a matter of finding Hamiltonian cycles in the complement of the graph. Here is one: B,C,H,A,F,G,E,D.
EN 
FR 
ES