Graphes eulériens et hamiltoniens
Parcourir chaque arête une fois (chaînes et cycles eulériens, théorème d'Euler, ponts de Königsberg, facteur chinois) ou chaque sommet une fois (chaînes et cycles hamiltoniens, voyageur de commerce) : deux questions voisines, deux difficultés très différentes.
- 30 cartes
- 6 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
- Mises en situation
- Comprendre
Quelques cartes du deck
Chaîne eulérienne : de quoi s'agit-il ?
Voir la réponse
Chaîne qui emprunte chacune des arêtes du graphe exactement une fois, mais qui peut passer plusieurs fois par un même sommet.
C'est le « tracé d'un seul trait sans lever le crayon ». Un sommet peut être repassé, une arête jamais.
Qu'affiche ce programme, qui décrit les sept ponts de Königsberg ?
```python
bridges = [("A", "C"), ("A", "C"), ("B", "C"), ("B", "C"), ("A", "D"), ("B", "D"), ("C", "D")]
degree = {}
for u, v in bridges:
degree[u] = degree.get(u, 0) + 1
degree[v] = degree.get(v, 0) + 1
print(sum(1 for d in degree.values() if d % 2 == 1))`4027
Voir la réponse
4Les degrés sont A = 3, B = 3, C = 5, D = 3 : les quatre sont impairs. Or une chaîne eulérienne en admet au plus deux, donc on ne peut pas franchir chaque pont une seule fois. 7 est le nombre de ponts, pas de sommets impairs.
Un graphe connexe admet un cycle eulérien si et seulement si tous ses sommets sont de degré ….
Voir la réponse
Un graphe connexe admet un cycle eulérien si et seulement si tous ses sommets sont de degré pair.
À chaque passage par un sommet, on entre par une arête et on sort par une autre : les arêtes se consomment par paires.
Cycle eulérien : de quoi s'agit-il ?
Voir la réponse
Chaîne eulérienne fermée : elle revient à son sommet de départ après avoir emprunté chaque arête une seule fois.
Le départ peut se faire de n'importe quel sommet, puisque le tracé revient à son point de départ.