Mathématiques discrètes - Coloriage Vertex

Question

J'ai un devoir qui m'a été confié il y a environ une semaine. La chose est, je ne comprends pas ce que mon professeur a enseigné mais il nous a donné un devoir ...

A = {a, b, s}, B = {b, h, t}, C = {a , t, s}, D = {h, ​​t, s}, E = {a, b}, F = {b, t, s}

Comment créer une coloration vertex minimale, A, B, C, D, E et F sont les vertex?

Je sais colorier un sommet mais je ne sais pas comment créer les graphes à partir des ensembles donnés. Toute aide? J'ai essayé de regarder sur internet mais je ne suis pas tombé sur une question comme celle-ci.

Answer 1

Si le graphique doit être interprété de telle sorte que les sommets A, B, C, D, E, F sont destinés à être connectés si et seulement si elles se croisent, une coloration optimale a 5 couleurs.

Le graphique résultant est presque le graphe complet sur 6 sommets - {E,F} et {E,D} sont les seuls bords qui manquent. Cela étant dit, il contient le graphe complet sur 5 sommets via le sous-graphe induit par {A,B,C,D,F}. Par conséquent, toute coloration de vertex ne peut pas utiliser moins de 5 couleurs. Au total, la coloration

F : 1 
A : 2 
B : 3 
C : 4 
D : 5 
E : 1 

est une 5-coloration du graphique qui est optimale.