Kromaattinen numero

Graafin G kromaattinen luku on värien minimimäärä, jolla on mahdollista värittää [1] graafin G kärjet siten, että minkä tahansa reunan päissä on eri värit. Yleensä merkitään χ( G ).

Määritelmä

Graafin kromaattinen luku on pienin määrä , jonka perusteella graafin kärkijoukko voidaan jakaa hajallaan oleviin luokkiin : $k$ $V$ $k$ $C_{1},C_{2},\ldots ,C_{k}$

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

siten, että kunkin luokan kärjet ovat riippumattomia , eli mikään graafin reuna ei yhdistä saman luokan pisteitä.

Aiheeseen liittyvät määritelmät

K-värittävä graafi on graafi, jonka kromaattinen luku ei ylitä . Eli sen kärjet voidaan värjätä korkeintaan väreillä siten, että jokainen reuna päättyy eri väriin. $K$ $K$
K-kromaattinen graafi on graafi, jonka kromaattinen luku on . Toisin sanoen graafin kärjet voidaan värjätä väreillä niin, että mikä tahansa reuna päättyy eri väreihin, mutta väreillä ei voi värittää tällä tavalla. $K$ $K$ $K-1$

Reunojen väritys

Graafin G kromaattinen luokka on värien vähimmäismäärä, jolla graafin G reunat voidaan värjätä siten, että vierekkäiset reunat ovat erivärisiä. Merkitään χ'( G ). Ongelma mielivaltaisen tasomaisen kuutiograafin ilman siltoja kolmella värillä värjäykseen vastaa kuuluisaa neljän värin ongelmaa . Reunojen väritys määrittää graafin 1-kertoimen .

Kromaattinen polynomi

Jos tarkastelemme merkityn graafin eri värien määrää käytettävissä olevan värien määrän t funktiona, niin tämä funktio on aina polynomi t :ssä . Tämän tosiasian löysivät Birkhoff ja Lewis [2] yrittäessään todistaa neljän värin ongelmaa .

Joidenkin graafien kromaattiset polynomit

Kolmio $K_{3}$	$t(t-1)(t-2)$
Täydellinen kaavio $K_n$	$t(t-1)(t-2)...(t-(n-1))$
puu , jossa on pisteet $n$	$t(t-1)^{{n-1}}$
Kierrä $C_{n}$	$(t-1)^{n}+(-1)^{n}(t-1)$
Petersenin kreivi	$t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t- 352)$

Mielivaltaisen graafin kromaattisen polynomin löytäminen

Piikkigraafin kromaattinen polynomi on $t$

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

Graafin kromaattinen polynomi on yhtä suuri kuin sen komponenttien kromaattisten polynomien tulo

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

On myös rekursiivinen relaatio - Zykovin lause [3] , ns. poisto- ja supistumiskaava

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

jossa ja ovat vierekkäisiä kärkipisteitä, on graafi, joka saadaan graafista poistamalla reuna , ja on graafi, joka saadaan graafista supistamalla reuna pisteeseen. Voit käyttää vastaavaa kaavaa $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),

missä ja ovat ei-vierekkäisiä kärkipisteitä, ja on graafista saatu graafi lisäämällä reuna $u$ $v$ $G+(u,v)$ $G$ $(u,v).$

Kromaattisen polynomin ominaisuudet

Kaikille positiivisille kokonaisluvuille $t$

P(G,t)\geq 0.

Kromaattinen luku on pienin positiivinen kokonaisluku , jolle $\chi (G)$ $t$

P(G,t)>0.

Kromaattisen polynomin aste on yhtä suuri kuin pisteiden lukumäärä:

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

Yleistykset

Kromaattista lukua voidaan myös harkita muille objekteille, kuten metrisille avaruuksille . Täten tason kromaattinen luku on värien vähimmäismäärä χ, jolle tason kaikki pisteet on värjätty jollain väreistä niin, ettei kaksi samanväristä pistettä ole täsmälleen 1:n etäisyydellä jokaisesta. muu. Sama pätee mihin tahansa tilaulottuvuuteen. Alkuperäisesti on todistettu, että lentokoneella ei kuitenkaan ollut mahdollista liikkua pidemmäksi aikaa. 8. huhtikuuta 2018 brittiläinen matemaatikko Aubrey de Gray todisti, että [4] [5] . Tätä ongelmaa kutsutaan Nelson-Erdős-Hadwiger-ongelmaksi . $4\leqslant\chi\leqslant 7$ $\chi >4$

Merkitys graafiteorialle

Monet graafiteorian syvälliset ongelmat muotoillaan helposti värityksen suhteen. Tunnetuin näistä ongelmista, neljän värin ongelma , on nyt ratkaistu, mutta uusia on tulossa, kuten neljän värin ongelman yleistys, Hadwigerin arvelu .

Katso myös

Muistiinpanot

↑ Värityssivu
↑ Birkhoff, GD ja Lewis, DC "Kromaattiset polynomit." Trans. amer. Matematiikka. soc. 60, 355-451, 1946.
↑ Tämä verkkotunnus on pysäköity Timewebin toimesta
↑ de Grey, Aubrey DNJ (2018-04-08), Tason kromaattinen numero on vähintään 5
↑ Vladimir Korolev. Matemaatikoilta puuttui neljä väriä koneen värittämiseksi . nplus1.ru. Käyttöönottopäivä: 11.4.2018. (määrätön)

Kirjallisuus

O. Malmi . Graafiteoria. - M .: Nauka, 1986.