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.
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?
Solution
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 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?
Solution
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?
Solution
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 plants. Two factories 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.
Solution
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's K7, or 21 links.
Exercise 5
Considering the following mathematical system:
Where X is 0 or 1. Determine, with a graph problem, a solution that maximizes the objective function (sum of the Xs).
Solution
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.
Modeling with tree
Exercise 6
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
Exercise 7
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.
Solution
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).
EN 
FR 
RU 
ES