Contents
ToggleCorrected exercises: graph modeling and coloring
This page contains various corrected exercises on the modeling of the graph theory and the problems of coloring of graph. Please see the page on graph theory to learn more about the basics of graph theory and various problems in graph theory.
Exercise 1
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 2
Think of the sequence 01110100 as being arranged in a circular pattern. Note that each of the eight possible binary triplets: 000, 001, 011, . . . , 111 appear exactly once in the circular list. Can you construct a similar list of length 16 where all four binary digit patterns appear exactly once each?
It is a graph with four vertices, each labeled with one of the possible pairs of binary digits. Imagine that each node is the last two digits of the pattern so far. Arrows leading away from a vertex are labeled 0 or 1: the two possible values for the next digit that can be added to the pattern, and the ends of the arrows indicate the new last two digits. For example, node 00 goes to 01 with an arc named 1, and goes to 00 with an arc named 0.
To get all possible three-digit combinations, we need to traverse the graph with an Eulerian cycle. Due to the result of the previous problem, there are always two outward arrows and two arrows to each vertex, and due to the result of the previous problem, there must be an Eulerian circuit.
The situation is the same for any number of digits except that the graph will become more and more complex. For the 4-digit version, there will be 8 vertices and 16 edges, and so on. But in any case, there will be two edges entering and two leaving each vertex, so an Eulerian circuit is possible.
Exercise 3
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)?
The graph is 4-chromatic.
Exercise 4
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.