Deux postes peuvent-ils se parler ?
Un graphe est un ensemble de points, les sommets, reliés par des traits, les arêtes. Il décrit tout réseau : des ordinateurs et leurs câbles, des stations de métro, des amis.
Dans une salle informatique, cinq postes sont reliés par des câbles. Un câble est débranché. Les deux groupes de postes peuvent-ils encore se parler ? Un graphe répond avec un chemin.
À la fin de cette leçon
Remarque
Je peux décrire un réseau par un graphe et trouver un chemin entre deux sommets.
Mots-clés
| Mot | Ce que ça veut dire |
|---|---|
| Sommet | un point du graphe, par exemple un poste |
| Arête | un trait qui relie deux sommets, par exemple un câble |
| Degré | le nombre d’arêtes qui touchent un sommet |
| Chemin | une suite de sommets, deux voisins se touchant par une arête |
| Graphe connexe | un graphe où un chemin relie deux sommets quelconques |
| Arbre | un graphe connexe sans cycle |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Un graphe se décrit par ses arêtes
Notre salle a cinq postes, A, B, C, D et E. Les arêtes sont A-B, B-C, C-A et D-E. Il suffit de les écrire, une par ligne.
Le degré d’un sommet est le nombre d’arêtes qui le touchent. A touche deux arêtes, donc son degré est 2.
Exemple travaillé : le degré de chaque poste
| Poste | Arêtes qui le touchent | Degré |
|---|---|---|
| A | A-B, C-A | 2 |
| B | A-B, B-C | 2 |
| C | B-C, C-A | 2 |
| D | D-E | 1 |
| E | D-E | 1 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Compter le degré de chaque poste
printf 'A B\nB C\nC A\nD E\n' | tr ' ' '\n' | sort | uniq -cAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Un chemin suit des arêtes
Un chemin de A à C est la suite A, B, C : chaque voisin est relié au suivant. Un graphe est connexe si un chemin relie deux sommets quelconques.
Pour le vérifier, on part d’un sommet. On note ses voisins, puis les voisins de ceux-là, jusqu’à ce que plus rien de nouveau n’arrive.
Exemple travaillé : un parcours depuis A
| Étape | Sommet regardé | Nouveaux sommets | Sommets vus |
|---|---|---|---|
| 1 | A | B, C | A, B, C |
| 2 | C | rien | A, B, C |
| 3 | B | rien | A, B, C |
| 4 | fin | D et E jamais atteints | A, B, C |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Un parcours avec une liste
# Quels postes un message venu de A peut-il atteindre ?
liens = [["A", "B"], ["B", "C"], ["C", "A"], ["D", "E"]]
vus = ["A"]
a_voir = ["A"]
while len(a_voir) > 0:
courant = a_voir.pop()
for lien in liens:
if lien[0] == courant and lien[1] not in vus:
vus.append(lien[1])
a_voir.append(lien[1])
if lien[1] == courant and lien[0] not in vus:
vus.append(lien[0])
a_voir.append(lien[0])
print("Postes atteints :", vus)
# Ajoutez ["C", "D"] à liens puis relancez : D et E sont atteints.
Un arbre est connexe et sans cycle
Un cycle est un chemin qui revient à son point de départ, comme A, B, C, A. Un arbre est connexe et n’a aucun cycle.
Un arbre de n sommets a toujours n moins 1 arêtes. Cinq postes en arbre ont quatre câbles : chaque câble de plus crée un cycle.
Compter les câbles de cinq postes
printf 'A B\nB C\nC D\nB E\n' | wc -lAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Erreur fréquente
Attention
Beaucoup pensent qu’un graphe de n sommets et n moins 1 arêtes est toujours un arbre. Ce n’est pas le cas. Un triangle A, B, C avec D isolé a quatre sommets et trois arêtes. Il a un cycle et n’est pas connexe. Vérifiez les deux conditions.
Pour aller plus loin
Dessinez sur papier un réseau de six postes en arbre. Comptez ses arêtes avec la règle « n moins 1 ».
Ajoutez une arête entre deux postes qui ne se touchent pas. Écrivez le cycle que vous venez de créer, puis retirez une arête du cycle pour retrouver un arbre.