On considère le graphe 𝒢 ci-dessous :
En justifiant la réponse, dire si ce graphe admet une chaîne eulérienne. Si oui, donner une telle chaîne.
Les degrés des sommets du graphe sont :
| Sommets | A | B | C | D | E | F | G | H | I | J | K |
| Degrés | 3 | 3 | 4 | 3 | 4 | 6 | 3 | 3 | 3 | 3 | 3 |
Le nombre de sommets de degré impair est supérieur à 2 donc le graphe 𝒢 n'admet pas une chaîne eulérienne.
On considère la matrice M ci-après (a, b, c et d sont des nombres réels).
Déterminer les réels a, b, c et d pour que la matrice M représente la matrice d'adjacence associée au graphe 𝒢, les sommets étant pris dans l'ordre alphabétique.
Les sommets C et D ne sont pas adjacents donc
Les sommets D et G sont adjacents donc
Les sommets I et E sont adjacents donc
Les sommets K et E ne sont pas adjacents donc
remarque :
Le graphe 𝒢 n'est pas orienté, on peut donc déterminer les réels a, b, c et d en utilisant la symétrie de la matrice M par rapport à la diagonale.
On donne Déterminer, en justifiant, le nombre de chemins de longueur 3 reliant A à J. Préciser ces chemins.
Le nombre de chaînes de longueur 3 reliant A à J est égal au terme situé à l'intersection de la première ligne et de la dixième colonne de la matrice .
il y a donc 5 chaînes de longueur 3 reliant A à J : , , , , .
On oriente et on pondère le graphe 𝒢 ci-dessus pour qu'il représente un réseau d'irrigation.
Déterminer un chemin de longueur minimale entre le départ d'eau en A et le bassin d'infiltration en K et donner sa longueur.
Pour déterminer la chaîne de poids minimal entre les sommets A et K on utilise l'algorithme de Dijkstra :
| A | B | C | D | E | F | G | H | I | J | K | Sommet sélectionné |
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | A (0) |
| 2 (A) | 5 (A) | 3 (A) | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | B (2) | |
| 5(A) | 3 (A) | 8 (B) | 4 (B) | ∞ | ∞ | ∞ | ∞ | ∞ | D (3) | ||
| 5(A) | 8 (B) | 4 (B) | 8 (D) | ∞ | ∞ | ∞ | ∞ | F (4) | |||
| 5(A) | 8 (B) | 8 (D) | 7 (F) | 8 (F) | 9 (F) | ∞ | C (5) | ||||
| 8 (B) | 8 (D) | 7 (F) | 8 (F) | 9 (F) | ∞ | H (7) | |||||
| 8 (B) | 8 (D) | 8 (F) | 9 (F) | 9 (H) | E (8) | ||||||
| 8 (D) | 8 (F) | 9 (F) | 9 (H) | G (8) | |||||||
| 8 (F) | 9 (F) | 9 (H) | I (8) | ||||||||
| 9 (F) | 9 (H) | J (9) | |||||||||
| 9 (H) | K (9) |
Le sommet K étant marqué, pour lire la chaîne de poids minimal, on part de K et on "remonte" la chaîne en suivant les prédécesseurs. .
Le chemin de longueur minimale entre le départ d'eau en A et le bassin d'infiltration en K est A - B - F - H - K d'une longueur de 9 km.
Les documents présentés ne sont pas libres de droits. Vous pouvez les télécharger et diffuser (en indiquant la provenance) à condition de ne pas en faire un usage commercial.