Coloration de graphe
Colorer les sommets d'un graphe pour que deux voisins diffèrent : nombre chromatique, bornes par les cliques et le degré maximum, coloration gloutonne et ordre des sommets, graphes bipartis, et problèmes d'emploi du temps vus comme des colorations.
- 28 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
Coloration propre : de quoi s'agit-il ?
Voir la réponse
Attribution d'une couleur à chaque sommet telle que deux sommets voisins ne reçoivent jamais la même.
Une seule arête dont les deux bouts ont la même couleur suffit à rendre la coloration invalide : on vérifie arête par arête.
Combien de couleurs ce programme utilise-t-il pour colorer la chaîne A-B-C-D ?
```python
adj = {"A": ["B"], "B": ["A", "C"], "C": ["B", "D"], "D": ["C"]}
color = {}
for v in ["A", "D", "B", "C"]:
used = {color[w] for w in adj[v] if w in color}
c = 0
while c in used:
c += 1
color[v] = c
print(len(set(color.values())))`3241
Voir la réponse
3A et D reçoivent 0, B reçoit 1, puis C voit B (1) et D (0) et doit prendre 2. Dans l'ordre A, B, C, D, le même graphe se colorerait avec 2 couleurs : l'ordre de traitement compte.
Un graphe qui contient une … de taille k a un nombre chromatique d'au moins ….
Voir la réponse
Un graphe qui contient une clique de taille k a un nombre chromatique d'au moins k.
Un triangle force 3 couleurs, un K₄ en force 4. C'est la borne inférieure qu'on cherche sur le dessin.
Nombre chromatique : de quoi s'agit-il ?
Voir la réponse
Plus petit nombre de couleurs avec lequel on peut colorer proprement les sommets d'un graphe, noté χ(G).
Pour prouver que χ(G) = k, il faut deux choses : une coloration à k couleurs, et une preuve qu'avec k − 1 couleurs c'est impossible (une clique de taille k, par exemple).