Definiția. Un grafic G cu un număr cromatic χ (G) = 2 este considerat a fi bicromatic.
Teorema. Graficul G al bipartitului ↔ G este un grafic bichromatic.
Necesitate →. Fie G = (V1, V2, E) un grafic bipartit. Vitezele V1 sunt colorate într-o singură culoare, iar nodurile de la V2 la celelalte. Culoarea rezultată a vârfurilor este corectă, deoarece vârfurile colorate vecine, unul dintre V1, celălalt din V2, sunt colorate în culori diferite. În consecință, graficul este bicromatic.
← Suficiență. Fie G un grafic bichromatic, atunci mulțimea vârfurilor sale poate fi împărțită în două clase:
V1 - noduri de G, colorate într-o singură culoare.
V2 sunt noduri de G colorate într-o culoare diferită.
Marginile lui G pot conecta vârfuri numai din diferite clase → graficul G = (V1, V2, E) este bipartit.
Notă. Următoarele afirmații sunt echivalente:
1) Graficul G este bicromatic.
2) Graficul G este bipartit.
3) Toate ciclurile simple în G au o lungime uniformă.
Arborele este un grafic bichromatic, deoarece nodurile de niveluri uniforme ale graficului pot fi colorate într-o singură culoare, iar nivelele ciudate în cealaltă.
Aprobarea. Fie Kp un grafic complet cu vârfuri p, apoi χ (Kp) = p.
Dovada. Prin inducție pe p.
Bază: p = 3 (triunghi), χ (K3) = 3.
Presupuneri de inducție: presupunem că χ (Kp-1) = p-1 culori.
Pas: Se arată că χ (Kp) = p. De fapt, permiteți v fie un vertex în Kp. Eliminăm vârful v de la Kp împreună cu marginile care îi aparțin. Apoi graficul Kp - v = Kp-1 este p-1 colorat de ipoteza de inducție cu p-1 culori. 1,2,3 ... p-1. Vârful v al lui Kp poate fi colorat numai de noua vopsea p. Prin urmare, χ (Kp) = p. Se stabilește etapa de inducție. Propunere: este dovedit.
Corolar. Există un grafic cu un număr cromatic mare arbitrar (grafice complete).
Corolar. Există un grafic cu un număr cromatic arbitrar mic (grafice goale).
Articole similare
Trimiteți-le prietenilor: