Font size
WorksheetsRO-CM2
Total questions: 11
Worksheet time: 4mins
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
Le problème du calcul du nombre chromatique est un problème :
NP-complet
polynomial
ça dépend
