On considère le graphe Γ ci-dessous.
Donner la matrice M associée au graphe Γ (les sommets seront rangés dans l'ordre alphabétique).
La matrice d'adjacence du graphe Γ est .
On donne : et .
Déterminer, en justifiant, le nombre de chaînes de longueur 3 reliant B à H. Les citer toutes.
Le terme de la matrice situé à l'intersection de la deuxième ligne et de la dernière colonne est égal à 4. Il existe quatre chaînes de longueur 3 entre les sommets B et H : B-A-F-H, B-A-G-H, B-E-F-H et B-F-E-H.
Quelle est la distance entre les sommets B et G ?
La distance de entre les sommets B et G, est la longueur d'une plus courte chaîne de Γ reliant B à G.
D'après la matrice , il existe une chaîne de longueur 2 entre B et G.
La distance de entre les sommets B et G est égale à 2.
Quel est le diamètre du graphe Γ ?
Soit D la matrice qui donne les distances entre deux sommets du graphe :
Les termes non nuls de la matrice M permettent de compléter D avec | Les termes non nuls de la matrice permettent de compléter D avec | Les termes non nuls de la matrice permettent de compléter D avec |
La plus grande distance entre deux sommets est 3 donc le diamètre du graphe est 3.
Déterminer en justifiant si le graphe Γ est complet.
Les sommets A et H ne sont pas adjacents donc le graphe Γ n'est pas complet.
Déterminer en justifiant si le graphe Γ est connexe.
Le diamètre du graphe est égal à 3 par conséquent, pour toute paire de sommets distincts, il existe au moins une chaîne de longueur inférieure ou égale à 3 ayant pour extrémités ces deux sommets.
Pour toute paire de sommets distincts, il existe une chaîne les reliant donc le graphe Γ est connexe.
Le graphe Γ modélise le plan d'un parc. Les arêtes du graphe représentent les allées du parc et les sommets du graphe sont les intersections.
En fin de journée, un agent du service d'entretien fait le tour du parc pour nettoyer les allées.
Est-il possible de planifier un parcours pour que cet agent passe par toutes les allées sans emprunter plusieurs fois la même allée ? Justifier la réponse. Si oui proposer un parcours.
Organiser la tournée en passant par toutes les allées du parc sans emprunter plusieurs fois la même allée c'est chercher si il existe une chaîne eulérienne.
Sommets | A | B | C | D | E | F | G | H |
Degré | 3 | 4 | 2 | 2 | 4 | 4 | 2 | 3 |
Le graphe est connexe et il n'y a que deux sommets A et H de degré impair, il existe donc une chaîne eulérienne d'extrémités A et H.
Il est possible d'organiser un parcours qui passe par toutes les allées du parc sans emprunter plusieurs fois la même allée. Par exemple A-B-E-D-C-B-F-E-H-F-A-G-H.
Pour rationaliser le nettoyage des allées, on souhaite établir un circuit commençant et finissant par l'entrée du parc G et qui passe par toutes les allées une et une seule fois.
Quel est le nombre minimal d'allées qu'il faudrait tracer pour obtenir un tel circuit.
Pour qu'un graphe connexe admette un cycle eulérien, il suffit que tous ses sommets soient de degré pair.
Il suffit de rajouter une allée entre les intersections A et H pour qu'un tel circuit soit possible.
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.