La correction d'Exercice sur le plus grand nombre de sommets adjacents ( recherche opérationnelle )
a) il faut 3 couleurs pour colorer G1 et 4 pour colorer G2 .
b) La plus grande clique est de taille 2 dans le graphe G1 ainsi que dans G2.
On part de G2. pour chaque sommet de G2 on crée une copie . un sommet copié est alors relié aux voisins du sommet de départ . On ajoute ensuite un sommet u qu'on relie a toutes les copies .
Il fallait remarquer que les sommets v1 ,v2 ,v3,v4,et v5 de G2 forment G1.
a) il faut 5 couleurs pour colorer G3.
b) la plus grande clique est de taille 2