Corrected exercises - Graph theory - exerci... http://www.bibmath.net/resources/index.php?a...

[email protected]
Search on the site...

Bibm@th

Search the site...

Home Resources Libraries References Themes Forum

Bibliothèque d'exercicesBibliothèque de problèmes

Home

Resources
College
Math Prep
Specialized Math

Capes
Internal aggregate
BTS

Libraries
Exercise Library
Library of problems

References
Dictionary
Biography of mathematicians
Form
French/English glossary

Themes
Cryptography and secret codes
Games and riddles
Magic squares
Mathematics in everyday life
Files

Forum

Mathematics Resources>Graph Theory and Algorithm Exercises>

Access my account > Access my exercise sheet >

Corrected exercises - Graph theory - practical exercises

Exercise 1 Is it the same graph?[Report an error] [Add to my exercise sheet]

Statement
Say which of the following drawings represent the same graph:

1 of 6 1/30/18, 1:15 AM
Corrected exercises - Graph theory - exercise... http://www.bibmath.net/resources/index.php?a...

Indication
Corrected
The first two drawings represent the same graph. It is a pentagon where all the vertices are connected to three others (to form a cycle), except for one.
vertex that is connected to all the others. The third and fourth drawings do not represent the same graph. For example, the third one has a cycle.
of order 3, which is not the case for the fourth.

Exercise 2 - Without raising the pencil

Statement
We consider the following drawing:

Is it possible to draw it without lifting the pencil and passing through each line once and only once?

Indication

2 of 6 1/30/18, 1:15 AM
Corrected exercises - Graph theory - exercise... http://www.bibmath.net/resources/index.php?a...

Corrected
If we consider that this represents a graph, we are looking to trace an Eulerian path in this graph. According to Euler's theorem, it is possible if and
only if all the vertices have an even degree, except for at most one. Let's name the vertices, as shown in the following drawing:

So the peaksA, EandBare of degree 3. Therefore, it is impossible!

Exercise 3 Choice of options [Report an error] [Add to my exercise sheet]

Statement
In an exam, candidates can choose 2 or 3 options from the 6 options offered: graphs, cycling, regional language, guitar, Latin, and swimming. Some
Students chose the options graphs, regional language, guitar. Others chose cycling and Latin; others finally chose regional language and swimming. Students spend at most
a challenge every day. Using graph theory, answer the following questions:

How many optional exams can be scheduled at most in one day?

2. What is the minimum duration of all optional tests?

Indication
Corrected
We will associate a graph with this problem, where the vertices are the possible options, and where there is an edge between two vertices if and only if those two
options are chosen simultaneously by at least one student. We obtain the following graph (we have renumbered the 6 options as A, B, C, D, E, F in order).

1. According to the graph, we can offer up to 3 options in the same day.A, B, Ffor example.
2. The number of days required is obtained by calculating the chromatic number of the graph (a given color to a vertex means that the
épreuves ayant cette couleur ont lieu le même jour). Ici, notre graphe contient le graphe complet à 3 sommets. Son nombre chromatique est donc au
less than or equal to 3. In fact, it is exactly equal to it. For example
We giveC1à A, BandF ;
We giveC2à CandE ;
We giveC3à D.

Exercise 4 Dangerous transports [Report an error] [Add to my exercises]

Statement
A company must transport six chemical products, labeled P1,...,P6, by truck from the manufacturing plant to the end-user company. For reasons
For security reasons, certain products cannot be transported together: P1 and P2, P1 and P4, P2 and P3, P2 and P5, P3 and P4, P5 and P6. Determine the number
minimum number of trucks required.

Indication
Corrected
We introduce the graph whose vertices are the products, and an edge connects two vertices if they cannot be transported simultaneously. We obtain the
following graph:

We are looking for the chromatic number of this graph, which can be calculated using the Welch and Powell algorithm for example. We order the vertices by degree.
decreasing, for example P2, P1, P3, P4, P5, P6. Then we assign

a first color at P2, P4, and P6;

3 of 6 1/30/18, 1:15 AM
Corrected exercises - Graph theory - exercise... http://www.bibmath.net/resources/index.php?a...

a second color at P1, P3, P5.

The chromatic number of the graph is at most 2, and it is actually exactly 2 (one cannot color P1 and P2 with the same color). Therefore, it requires at least
at least two trucks to transport everything.

Exercise 5 Mood incompatibility

Statement
Eight young men want to work in a supermarket where three positions are available. The manager, concerned about avoiding problems, wants to
take into account the hostilities between these young men:

Adrien can't stand Damien and Cyril.

Cyril refuses to work with Benjamin;
Damien can't stand Greg;
Eric ne veut cotoyer ni Benjamin, ni Frank, ni Hector;
Frank does not appreciate Greg and Hector;
Greg does not get along with Adrien;
Hector refuses to work with Frank or Cyril.

1. Build an undirected graph representing this situation of mood incompatibility.

2.Eric has the best resume. Who can we hire with him?
3. Provide another possible combination of three young people, other than Eric, that can be hired.

Indication
Corrected

1. The graph consists of 8 vertices A, B, C, D, E, F, G, H representing the 8 young men and edges that express the mood incompatibilities.
then obtains the following graph:

2. It is necessary to hire two people who are not related to Éric, and who are not related to each other. For example, here we can also hire
Adrien and Cyril (this is not the only possible choice, we could have also recruited Cyril and Greg for example).
Once again, we need to find 3 vertices that have no edges between them. This is the case, for example, of A, C, and F. We could also have done a coloring.
of the graph, and find 3 vertices that are colored and of the same color.

Exercise 6 - Shortest path [Report an error] [Add to my exercise sheet]

Statement
Find the shortest path fromAà Kin the following graph. We will detail the calculations.

Indication
Corrected

4 of 6 1/30/18, 1:15 AM
Corrected exercises - Graph theory - exercises... http://www.bibmath.net/resources/index.php?a...

On applique l'algorithme de Dijkstra, et on obtient le tableau suivant :

A B C D E F G H I J K
0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
4 1(A) ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
3(C) 8 ∞ ∞ ∞ ∞ ∞
8 10 6(B) ∞ ∞ ∞ ∞ ∞
8(B) 10 16 ∞ ∞ ∞ ∞
10(F ) 16 ∞ ∞ ∞ ∞
15(E) 42 30 ∞ ∞
42 30 21(G) ∞
42 28(J) 51
36(I) 46
45(H)

The length ofAà Kis therefore equal to 45, and the shortest path isACBFEGJIHS .

Exercise 7 Man, woman, and mistress

Statement
A man, his jealous wife, and his mistress want to cross a river. But the ferryman's boat is too small, and he can only transport two.
people at the same time. How to do it, knowing that the jealous woman does not want her husband and the mistress to be alone on a shore, and that the man does not want
Not that his wife and mistress are alone on a riverbank?

Indication
Corrected
We will model the situation with a graph whose vertices are all the possible situations. We denote by P the ferryman, by H the man, by F the woman and
by M the mistress. The summit (PM/HF) means that on the first bank we have the ferryman and the mistress, and on the arrival bank, we have the man and his wife. We
do not include the prohibited vertices, such as (PF/HM) and (PF/FM). There is an edge between two vertices if one can move from one situation to another by a crossing.
of barque. The problem is to know if there is a path between the vertex (PHFM/) and the vertex (/PHFM). The graph that we obtain is:

It is indeed possible to find a path between the two desired vertices, which is represented on the graph by dashed lines. Let us note that
In a more complicated setting, involving more vertices, we could automate the search for the existence of a path by introducing the matrix.
of adjacency and by calculating its successive powers.

Forum discussions
Solvability of an equation ...
Can someone explain certain ...
sieve in python
How to calculate the angle ...
demonstration: condition …
Generalized solution of ...
Cryptography
Derivative functions
entire series
Peano's arithmetic s ...
Maths homework 1*S functions
Exercise 1 S
physics equation m ...
Help with estimation with ...
problem 4th number divisible
Access the forums

5 of 6 1/30/18, 1:15 AM
Corrected exercises - Graph theory - exerci... http://www.bibmath.net/resources/index.php?a...

Mathematician of the Month

Ernesto Cesàro (1859-1906)

All the biographies
Report an error, a spelling mistake Contribution to the site Credits
Contact us

6 of 6 1/30/18, 1:15 AM