Les deux parties sont indépendantes.
On considère le graphe dont la matrice associée est .
Quel l'ordre du graphe ? Quel est le nombre d'arêtes de ce graphe ?
M est une matrice carrée de dimension symétrique par rapport à sa diagonale donc le graphe est d'ordre 8 non orienté. Par conséquent, la somme des degrés des sommets est égale au double du nombre d'arêtes.
| Sommets № | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | Somme |
| Degrés | 2 | 2 | 4 | 2 | 4 | 4 | 2 | 4 | 24 |
Le graphe est d'ordre 8 et il y a 12 arêtes.
On donne les deux matrices et . Quelle est la longueur de la plus courte chaîne entre les sommets 1 et 4 ?
Dans les matrices M et , le terme situé à l'intersection de la première ligne et de la quatrième colonne est nul donc il n'existe pas de chaîne de longueur 1 ou 2 entre les sommets 1 et 4.
Par contre le terme situé à l'intersection de la première ligne et de la quatrième colonne de la matrice est égal à 2 donc il existe deux chaînes de longueur 3 entre les sommets 1 et 4.
La distance entre les sommets 1 et 4 est égale à 3.
Ce graphe admet-il une chaîne eulérienne ? Justifier la réponse.
Tous les termes de la matrice sont non nuls. Par conséquent, pour toute paire de sommets du graphe, il existe au moins une chaîne de longueur 3 les reliant donc le graphe est connexe.
Le graphe est connexe et tous les sommets sont de degré pair donc il existe un cycle eulérien.
Le graphe ci-dessous, modélise le plan du quartier dans lequel un facteur effectue sa tournée à partir du sommet C.
Les nombres présents sur chacune des arêtes indiquent le temps moyen en minutes mis par le facteur pour distribuer le courrier dans chaque rue.
Le facteur souhaite effectuer sa tournée de manière à arriver le plus rapidement en A tout en distribuant le courrier dans chaque rue où il passe.
À l'aide d'un algorithme, déterminer le parcours permettant d'aller du sommet C au sommet A le plus rapidement possible. Préciser alors le trajet à emprunter.
Pour déterminer le trajet le plus court pour aller de C à A, on utilise l'algorithme de Dijkstra.
| A | B | C | D | E | F | G | H | Sommet sélectionné |
| ∞ | ∞ | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | C (0) |
| ∞ | 12 (C) | 8 (C) | 19 (C) | ∞ | ∞ | 21 (C) | D (8) | |
| ∞ | 12 (C) | 19 (C) | ∞ | ∞ | 20 (D) | B (12) | ||
| ∞ | 19 (C) | ∞ | ∞ | 20 (D) | E (19) | |||
| 52 (E) | 37 (E) | ∞ | 20 (D) | H (20) | ||||
| 52 (E) | 37 (E) | 27 (H) | G (27) | |||||
| 52 (E) | 36 (G) | F (36) | ||||||
50 (F) | A (50) |
Le sommet A étant marqué, pour lire la chaîne de poids minimal, on part de A et on remonte la chaîne en suivant les prédécesseurs. .
Le trajet le plus rapide pour aller de C à A est C - D - H - G - F - A en 50 minutes.
Est-il possible pour le facteur de revenir en C pour distribuer le courrier restant dans chacune des rues où il n'est pas passé sans avoir à repasser par une des rues déjà empruntée ? Si oui donner un parcours possible.
Quel est alors le temps mis par le facteur pour effectuer sa tournée complète ?
La matrice associée au graphe est la matrice M donnée dans la parie A. Par conséquent, le graphe admet un cycle eulérien pouvant commencer à partir du sommet C. Le début du cycle étant la chaîne C - D - H - G - F - A, on termine le cycle en ajoutant par exemple la chaîne A - E - F - H - C - E - B - C.
Chaque arête étant parcourue une seule fois, le temps mis pour effectuer la tournée est donné par la somme des poids des arêtes.
Le facteur peut effectuer sa tournée C - D - H - G - F - A - E - F - H - C - E - B - C en 180 minutes
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.