This page shows some corrected exercises about graph theory modeling and trees. The goal of these exercises is to learn how to model a problem through graph theory concepts and basics.
Modeling with graph theory
Exercise 1
Two players have 2 or more batches of matches. At each turn, the next player may remove a number of matches of a lot (depending on the selected rule). The player who removes the last match loses.
Model this game with a graph in the case where one has from two piles each containing three matches, and where a player can remove one or two matches each.
What move the first player must play to win the game?
Edges are oriented from left to right. If we are in position or we win. Thus, the position verify that, whatever play your adversary, you can reach or
Exercise 2
The following graph 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 to place them) so that all intersections are monitored?
If we now place guards at intersections, assuming that a guard can monitor all corridors leading to this crossroad, how many guards are needed?
Each guard will be placed on an edge and can monitor two intersections (vertices). The graph has 11 vertices; it will take at least six guards. We must therefore find a set (minimum) 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 vertices and watch the edges. 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 4
Skynet is a network with 15 vertices. You can go from every vertex to at least seven other vertices by link. Can we go by link from a 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. In a vertex, you can also connect to at least seven other vertices; there is therefore a new network of 8 vertices. There must be a shared vertex in these networks, because otherwise the network would have at least 16 vertices. X is connected to A in at most two shots, through this common vertex; it is connected to all other cities.
Exercise 5
A network is composed of seven plants. A city is linked to exactly two plants. Two plants share exactly one city. How many cities are served by the network? Prove that a complete graph with vertices has n(n-1)/2 links.
Plants are the vertices and cities are represented by an edge connecting two vertices. Rule 2 implies that there is no multiple edge, and that any couple of vertices are adjacent; i.e. that the graph is complete; it’s K7, i.e. 21 links.
Exercise 6
Considering the following mathematical system:
Where is 0 or 1. Determine, with a graph problem, a solution that maximizes the objective function: .
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 couple of vertices has a direct link.
Modeling with tree
Exercise 7
Let be a non-oriented graph with vertices. Prove that all the following properties are equivalent:
- is a tree
- is connected and if we remove an edge, is no longer connected
- is connected with edge
- has no cycle until we add an edge
- has no cycle with edge
- Only one path between any couple of vertices
Exercise 8
We want to add a battery in a network. The following graph shows cost to send energy between two substations in the network, and the amount of energy sent by a substation. You have to place the battery at a substation while minimizing total cost.
Calculate the sum of all cost at each substation, i.e. the cost of each path between any substation to the chosen substation (edge*vertex).
FR 
EN 
ES