Număr cromatic

Numărul cromatic al graficului G este numărul minim de culori în care este posibil să se coloreze [1] vârfurile graficului G astfel încât capetele oricărei muchii să aibă culori diferite. Notat de obicei χ( G ).

Definiție

Numărul cromatic al unui graf este numărul minim astfel încât mulțimea vârfurilor grafului poate fi împărțită în clase disjunse : $k$ $V$ $k$ $C_{1},C_{2},\ldots,C_{k}$

V=\bigcup _{i}^{{}}C_{i};\ C_{i}\cap C_{j}=\varnothing ,

astfel încât vârfurile din fiecare clasă sunt independente , adică nicio margine a graficului nu conectează vârfurile aceleiași clase.

Definiții înrudite

Un grafic K-colorabil este un grafic al cărui număr cromatic nu depășește . Adică, vârfurile sale pot fi colorate cu nu mai mult de culori, astfel încât fiecare margine să se termine într-o culoare diferită. $K$ $K$
Un grafic K-cromatic este un grafic al cărui număr cromatic este . Adică vârfurile graficului pot fi colorate cu culori astfel încât orice muchie să se termine în culori diferite, dar nu se mai poate colora cu culori în acest fel. $K$ $K$ $K-1$

Colorarea marginilor

Clasa cromatică a unui grafic G este numărul minim de culori în care marginile graficului G pot fi colorate astfel încât marginile adiacente să aibă culori diferite. Notat χ'( G ). Problema colorării muchiilor unui graf cubic plan arbitrar fără punți cu trei culori este echivalentă cu celebra problemă a patru culori . Colorarea marginilor definește o factorizare 1 a unui grafic.

Polinom cromatic

Dacă luăm în considerare numărul de colorări diferite ale unui grafic etichetat ca o funcție a numărului disponibil de culori t , atunci se dovedește că această funcție va fi întotdeauna un polinom în t . Acest fapt a fost descoperit de Birkhoff și Lewis [2] în timp ce încercau să demonstreze problema celor patru culori .

Polinoame cromatice ale unor grafice

Triunghi $K_{3}$	$t(t-1)(t-2)$
Graficul complet $K_n$	$t(t-1)(t-2)...(t-(n-1))$
arbore cu vârfuri $n$	$t(t-1)^{{n-1}}$
Ciclu $C_{n}$	$(t-1)^{n}+(-1)^{n}(t-1)$
Contele de Petersen	$t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t- 352)$

Găsirea polinomului cromatic al unui graf arbitrar

Pentru un grafic de vârfuri, polinomul cromatic este $t$

|V(G)|=1\Rightarrow P(G,t)=t.

Polinomul cromatic al unui grafic este egal cu produsul polinoamelor cromatice ale componentelor sale

G_{1}\cap G_{2}=\emptyset \Rightarrow P((G_{1}\cup G_{2}),t)=P(G_{1},t)P(G_{2},t ).

Există și o relație recursivă - teorema lui Zykov [3] , așa-numita formulă de îndepărtare și contracție

P(G,t)=P(G-(u,v),t)-P(G/(u,v),t),

unde și sunt vârfuri adiacente, este un grafic obținut dintr-un grafic prin eliminarea unei muchii și este un grafic obținut dintr-un grafic prin contractarea unei muchii la un punct. Puteți folosi formula echivalentă $u$ $v$ $G-(u,v)$ $G$ $(u, v),$ $G/(u,v)$ $G$ $(u,v)$

P(G,t)=P(G+(u,v),t)+P(G/(u,v),t),

unde și sunt vârfuri neadiacente și este graficul obținut din grafic prin adăugarea unei muchii $u$ $v$ $G+(u,v)$ $G$ $(u,v).$

Proprietățile polinomului cromatic

Pentru toate numerele întregi pozitive $t$

P(G,t)\geq 0.

Numărul cromatic este cel mai mic număr întreg pozitiv pentru care $\chi (G)$ $t$

P(G,t)>0.

Gradul unui polinom cromatic este egal cu numărul de vârfuri:

\deg P(G,t)=|V(G)|

Generalizări

De asemenea, numărul cromatic poate fi luat în considerare pentru alte obiecte, cum ar fi spațiile metrice . Astfel, numărul cromatic al unui plan este numărul minim de culori χ pentru care există o astfel de colorare a tuturor punctelor planului într-una dintre culori, încât nu există două puncte de aceeași culoare la o distanță de exact 1 de fiecare. alte. Același lucru este valabil pentru orice dimensiune spațială. Se dovedește în mod elementar că pentru avion , însă, nu a fost posibil să se deplaseze mai departe pentru o lungă perioadă de timp. Pe 8 aprilie 2018, matematicianul britanic Aubrey de Gray a demonstrat că [4] [5] . Această problemă se numește problema Nelson-Erdős-Hadwiger . $4\leqslant\chi\leqslant 7$ $\chi >4$

Semnificația pentru teoria graficelor

Multe probleme profunde din teoria grafurilor sunt ușor de formulat în termeni de colorare. Cea mai faimoasă dintre aceste probleme, problema celor patru culori , a fost acum rezolvată, dar apar altele noi, cum ar fi o generalizare a problemei celor patru culori, conjectura Hadwiger .

Vezi și

Note

↑ Pagina de colorat
↑ Birkhoff, GD și Lewis, DC „Chromatic Polynoals”. Trans. amer. Matematică. soc. 60, 355-451, 1946.
↑ Acest domeniu este parcat de Timeweb
↑ de Grey, Aubrey DNJ (2018-04-08), Numărul cromatic al avionului este de cel puțin 5
↑ Vladimir Korolev. Matematicienilor le lipseau patru culori pentru a colora avionul . nplus1.ru. Data accesului: 11 aprilie 2018. (nedefinit)

Literatură

O. Minereu . Teoria grafurilor. — M .: Nauka, 1986.