Chemins, cycles, connexité

Chaînes et chemins, cycles et circuits, distance et diamètre, connexité d'un graphe, ponts, accessibilité et forte connexité d'un graphe orienté.

Le programme, thème par thème

Le poids de chaque thème suit celui que lui donne l'examen.

Chaîne : de quoi s'agit-il ?
Voir la réponse
Suite de sommets dans laquelle deux sommets consécutifs sont toujours reliés par une arête ; son nombre d'arêtes est sa longueur.
A-B-C est une chaîne de longueur 2 si A-B et B-C sont des arêtes. Dans un graphe non orienté, on peut la lire dans les deux sens.
Un graphe a pour arêtes A-B, B-C, C-D, A-E et E-D. Quelle est la distance de A à D ?
- 2
- 3
- 4
- 5
Voir la réponse
2
A-E-D relie A à D en 2 arêtes. La chaîne A-B-C-D (3) existe aussi, mais la distance est la plus courte. 5 est la longueur du cycle entier, 4 le nombre de sommets de A-B-C-D.
L'… d'un sommet est sa plus grande distance à un autre sommet ; le … est la plus grande excentricité.
Voir la réponse
L'excentricité d'un sommet est sa plus grande distance à un autre sommet ; le diamètre est la plus grande excentricité.
Le diamètre est donc la plus grande distance du graphe. Il se mesure avec des plus courtes chaînes, jamais avec la plus longue chaîne.
Chemin : de quoi s'agit-il ?
Voir la réponse
Suite de sommets d'une structure orientée où chaque arc est parcouru dans son sens, du départ vers l'arrivée.
Une chaîne ignore le sens des arcs, un chemin le respecte : avec A → B et C → B, A-B-C est une chaîne mais pas un chemin.