RO-CM2

Une coloration d'un graphe réfère au nombre minimal de couleur qu'il faut pour colorier les sommets de ce graphe :

• VRAI

• FAUX

L'indice chromatique est nombre minimal de couleurs nécessaire pour colorier chaque sommet du graphe de façon à ce que deux sommets adjacents soient de couleurs différentes :

• VRAI

• FAUX

Un graphe est k-colorable si l'on peut colorer ses sommets avec k couleurs distinctes, sans que deux sommets voisins aient la même couleur :

• VRAI

• FAUX

Quand on parle de coloration d'un graphe on fait par défaut référence à la coloration des sommets :

• VRAI

• FAUX

Un graphe complet à n sommets est k-colorable avec k

• = n

• < n

• < = n

• > n

• > = n

L'indice chromatique d'un graphe G est :

• > = degréMax(G)

• < = degreMax(G) + 1

• > = degreMin(G)

• < = degreMin(G) + 1

Un graphe est biparti s’il existe une partition de son ensemble de sommets en deux sous-ensembles V1 et V2 telle que chaque arête ait une extrémité dans V1 et l’autre dans V2 :

• VRAI

• FAUX

La taille de la clique maximale d'un graphe est toujours :

• < = nombreChromatique(G)

• > = nombreChromatique(G)

Si mon graphe G est k-colorable alors j'ai :

• k stable(s) dans G

• k+1 stable(s) dans G

• k - 1 stable(s) dans G

Un algorithme "difficile" ne fournit aucune solution :

• VRAI

• FAUX