Graafi värvimise uurija

Lohista tippe, joonista servi ja värvi graaf käsitsi või ahne algoritmiga — vaata, kuidas kliki alampiir paljastab, mitut värvi tegelikult vaja on.

Näidisarvutus — Graafi värvimise uurija

Tipud	3
Servad	3
Kasutatud värve	0
Konfliktid	0

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

kui palju värve sul tegelikult vaja on? 🖖

Kromaatiline arv χ(G) on minimaalne värvide arv, mille korral ükski serv ei ühenda kahte samavärvilist tippu. Selle täpne leidmine on NP-raske — parim üldine garantii jääb kliki alampiiri (iga suurusega k klikk nõuab vähemalt k värvi) ja ahne ülempiiri vahele (Welsh-Powelli värvimine kahaneva astme järgi ei kasuta kunagi rohkem kui Δ+1 värvi, kus Δ on maksimaalne aste). Tasapinnaliste graafide jaoks — need, mida saab joonistada ilma servade ristumiseta — garanteerib neljavärviteoreem, et alati piisab 4 värvist; see tõestati esimest korda arvuti abil 1976. aastal ja on siiani üks vähestest olulistest teoreemidest, mis nõuab ammendavat arvutipõhist juhtumite kontrolli. Graafi värvimine on aluseks reaalsetele jaotusprobleemidele: registrite jaotamine kompilaatorites, eksamite ajakavastamine ja raadiosageduste jaotamine taanduvad kõik konfliktigraafi värvimisele.

naabrid peavad erinema — see ongi kogu mäng 🖖

Graafi värvimine taandub ühele reeglile: ükski serv ei tohi ühendada kaht sama värvi tippu ning värve tahad kasutada võimalikult vähe. See ainus tingimus otsustab kõik. Kasulik test: iga paarisarvulise pikkusega tsükkel saab hakkama 2 värviga, kuid iga paaritu pikkusega tsükkel vajab 3 — nii et kolmnurka (väikseimat paaritut tsüklit) ei saa kunagi 2 värviga värvida. Ehita mõlemad tööriistas ja jälgi konfliktide arvu.

ahne värvimine võib vägevalt läbi kukkuda 🖖

Tippude värvimine ükshaaval, valides alati madalaima vaba värvi, tundub turvaline, kuid järjekord on äärmiselt oluline. Nn kroongraafide puhul — 2n tippu, mis vajavad vaid 2 värvi — sunnib pahatahtlik järjekord ahne meetodi kasutama hoopis n värvi. Selle halvim juht on tõkestamata, mistõttu tööriista automaatvärvimine järjestab tipud kahaneva astme järgi (Welsh-Powell), et selliseid lõkse vältida.

Ülesanded täielikult lahendatud

Peterseni graafi tegelik kromaatiline arv 5 sammu
Peterseni graafil on 10 tippu, 15 serva ja selles pole ühtegi kolmnurka. Paneel kuvab seetõttu χ ≥ 2. Leidke tegelik kromaatiline arv. See on olek Peterseni graaf.
1. Mis tahes graafist saab tasuta kaks tõket: see vajab vähemalt nii palju värve, kui on selle suurimas klikis, ega vaja kunagi rohkem kui ühe võrra üle oma maksimaalse astme.
  
  $ω (G) \leq χ (G) \leq Δ (G) + 1 : Petersen has ω = 2, Δ = 3 ⟹ 2 \leq χ \leq 4$
2. Peterseni graafi vööde on 5, seega ei ole selles ühtegi kolmnurka ja kliki tõke taandub triviaalsele väärtusele 2. See on arv, mida paneel kuvab.
  
  $girth = 5 ⟹ no triangle ⟹ ω = 2, yet the graph is not bipartite$
3. Kaks värvi on võimalikud vaid siis, kui graaf on kahepoolne, ning kahepoolne tähendab paaritu tsükli puudumist. Välimine pentagon on 5-tsükkel, seega kaks värvi ei tule kõne alla.
  
  $bipartite ⟺ no odd cycle; the outer 5-cycle is odd ⟹ χ \geq 3$
4. Kolmest värvist piisab ning ühe sobiva värvingu esitamine tõestab täielikult ülemise tõkke. Värvige välimise viisnurga tipud ringjoont mööda järjest 1, 2, 1, 2, 3 ning seejärel viis sisemist tippu samas järjekorras 2, 1, 3, 3, 2; iga sisemine tipp on oma kodara kaudu ühendatud vastava välimise tipuga. Vaadake läbi kõik viisteist serva: ühegi serva otspunktid ei ole sama värvi.
  
  $a 3-colouring exists ⟹ χ = 3, strictly above the clique bound ω = 2$
5. Brooksi teoreem ütleb sama asja ülaltpoolt: sidus graaf, mis ei ole täielik ega paaritu tsükkel, vajab maksimaalselt Δ värvi, ning Δ on siin 3.
  
  $∣ V ∣ = 10, ∣ E ∣ = 15, Δ = 3 : Brooks’ theorem gives χ \leq 3 for a connected non-complete graph$
Vastus

3, mis on rangelt suurem tõkest, mida paneel suudab tõestada. Suurim klikk Peterseni graafis on üksik serv, mistõttu kliki tõke annab vaid χ ≥ 2 ja eksib ühe võrra. Vahe on olulisem kui paistab: Peterseni graaf on standardne vastunäide intuitsioonile, et värvimise keerukus tuleneb klikkidest, ning on olemas kolmnurgavabu graafe, mis vajavad nelja värvi, viit või mis tahes arvu — Mycielski konstruktsioon tekitab neid tellimustööna. Seega on klikiarv alumine tõke, mis võib olla suvaliselt kaugel, mistõttu kromaatilise arvu leidmine on NP-raske, samal ajal kui kolmnurga leidmine seda ei ole. Peterseni graafi täpse väärtuse 3 määravad paaritu tsükkel altpoolt ja Brooksi teoreem ülaltpoolt.

$χ (Petersen) = 3 > ω = 2 : the clique bound is not tight$
χ piiride võrdlemine täielikul K4 graafil 5 sammu
Nüüd K₄ — neli tippu, kõik kuus serva olemas. Arvutage χ ja võrrelge tõkkeid sellega, mida need tegid Peterseni graafi puhul. See on olek Täielik K4.
1. Loenda servad pildi usaldamise asemel: iga nelja tipu paar on ühendatud ning paare on kokku kuus.
  
  $K_{4} : ∣ V ∣ = 4, ∣ E ∣ = (2 4) = 6, every pair adjacent$
2. Iga tipp on külgnev iga teise tipuga, seega ei tohi ühelgi kahel tipul olla sama värvi. See on alumine tõke 4 ja see ei vaja muud argumenti peale definitsiooni.
  
  $all four vertices are mutually adjacent ⟹ ω = 4 ⟹ χ \geq 4$
3. Neli värvi on ilmselgelt piisav, seega tõke on saavutatud. Sama arutluskäik annab χ(Kₙ) = n iga n korral, mis teeb täielikud graafid lihtsaks juhtumiks.
  
  $four colours suffice trivially ⟹ χ (K_{n}) = n$
4. Aseta need kaks graafi kõrvuti. Sama küsimus, samad kaks tõket, ja nendevaheline vahe moodustabki kogu teema.
  
  $here ω = χ = 4 : the bound is tight, and Petersen showed it need not be$
5. Pane tähele, kus asub siin Brooksi teoreem. Selle tõke Δ = 3 oleks K₄ puhul vale, mistõttu täielikud graafid on sellest nimepidi välja jäetud.
  
  $Δ + 1 = 4 as well — Brooks’ theorem excludes complete graphs for exactly this reason$
Vastus

4, ning siin on iga tõke korraga täpne. Klikiarv on 4, sest terve graaf on klikk, Δ + 1 on 4, sest iga tipp ühendub ülejäänud kolmega, ning tegelik vastus on nende vahele pigistatud ilma et tal oleks kuskile minna. See on juhtum, millele inimesed oma intuitsiooni rajavad, ja see on täpselt see juhtum, mille Brooksi teoreem välistab — tema tõke Δ kehtib iga sidusa graafi kohta, välja arvatud täielikud graafid ja paaritud tsüklid, ning need kaks ülesannet on mõlema erandi põhjuseks. Peterseni graaf ja K₄ tähistavad kahte äärmust: üks, kus kliki tõke eksib ühe võrra, ja teine, kus see ei saa üldse eksida.

$χ (K_{4}) = ω (K_{4}) = Δ + 1 = 4$

Allikad (2)

Insight block 1 — the four colour theorem, and the computer proof it needed: K. Appel and W. Haken, "Every planar map is four colorable. Part I: Discharging." Illinois Journal of Mathematics 21(3), 429–490, 1977.
And the descending-degree ordering the auto-colour button uses: D. J. A. Welsh and M. B. Powell, "An upper bound for the chromatic number of a graph and its application to timetabling problems." The Computer Journal 10(1), 85–86, 1967.

42Mathi meeskond · Uuendatud 2026-06-16

Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud. Toimetamispõhimõtted · Parandused

Kõik Arvutustehnika õppetunnid →

Graafi värvimise uurija

kui palju värve sul tegelikult vaja on? 🖖

naabrid peavad erinema — see ongi kogu mäng 🖖

ahne värvimine võib vägevalt läbi kukkuda 🖖

Näiteülesanded