Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Az A. 807. feladat (2021. október)

A. 807. Adott egy \(\displaystyle n \ge 2\) egész szám. Legyen \(\displaystyle G\) egy véges egyszerű gráf, melynek minden élén legfeljebb \(\displaystyle n\) kör halad át. Bizonyítandó, hogy a gráf kromatikus száma legfeljebb \(\displaystyle n+1\).

Javasolta: Schweitzer Ádám (Budapest)

(7 pont)

A beküldési határidő 2021. november 10-én LEJÁRT.


Válasszunk egy tetszőleges csúcsot, és csináljunk belőle egy mélységi bejárást. Ennek segítségével kapunk egy feszítőfát, minden csúcs akkor kerül bele a fába amikor először megtaláljuk, és a fában azzal a csúccsal van összekötve ahonnan megtaláltuk. Így találtunk \(\displaystyle G\)-ben egy feszítőfát, ezt mélységi fának fodjuk nevezni, és jelöljük ezt \(\displaystyle F\)-fel. Továbbá nevezzük a \(\displaystyle G\) nem \(\displaystyle F\)-beli éleit külső éleknek. Számozzuk meg a gráf csúcsait megtalálási sorrendben, a kiinduló csúcs kapja az \(\displaystyle 1\)-s számot, ezt hívjuk gyökér csúcsnak. Minden \(\displaystyle v\) nem gyökér csúcsból egyértelműen létezik út a gyökérbe \(\displaystyle F\)-ben. Ezen az úton a \(\displaystyle v\)-n kívüli csúcsokat \(\displaystyle v\) őseinek nevezzük, a közvetlenül \(\displaystyle v\) mellett lévő csúcsot (ami az a csúcs ahonnan megtaláltuk \(\displaystyle v\)-t a mélységi bejárás során) pedig \(\displaystyle v\) apa csúcsának fogjuk hívni, és \(\displaystyle f(v)\)-vel fogjuk jelölni. Megfordítva, ha \(\displaystyle u\) csúcs a \(\displaystyle v\) őse akkor \(\displaystyle v\) az \(\displaystyle u\) leszármazottja, és ha \(\displaystyle u\) csúcs a \(\displaystyle v\) apja akkor \(\displaystyle v\) az \(\displaystyle u\) gyereke. Az \(\displaystyle u\) leszármazottjai és \(\displaystyle u\) által feszített részfát \(\displaystyle F\)-ben az \(\displaystyle u\) csúcshoz tartozó részfának fogjuk nevezni.

Azt az egyszerű, ismert állítást fogjuk használni, hogy a mélységi fában nem megy keresztbe él, azaz tetszőleges külső él egy csúcsot az ősével köt össze. Minden \(\displaystyle v\) nem gyökér csúcsra legyen \(\displaystyle E_v\) a \(\displaystyle v\)-re illeszkedő külső élek halmaza, melyek \(\displaystyle v\)-t valamelyik ősével kötik össze. A kulcs észrevétel az, hogy \(\displaystyle |E_v| \leq n\) minden \(\displaystyle v\) csúcs esetén, mivel tetszőleges külső élet ha hozzáveszünk \(\displaystyle F\)-hez, akkor pontosan egy kör fog keletkezni, és \(\displaystyle E_v\) tetszőleges élét hozzávéve \(\displaystyle F\)-hez egy olyan kört kapunk, amely tartalmazza a \(\displaystyle vf(v)\) élet, sőt később még az is fontos lesz, hogy ezek a körök az \(\displaystyle f(v)f(f(v))\) élet is tartalmazzák. Így ha \(\displaystyle |E_v|>n\) lenne, akkor lenne több, mint \(\displaystyle n\) kör ami tartalmazza a \(\displaystyle vf(v)\) élet, ami a feladat feltétele szerint nem lehet.

Azt akarjuk igazolni, hogy ki tudjuk színezni \(\displaystyle G\) csúcsait \(\displaystyle n+1\) színnel, hogy ne legyen két szomszédos azonos színű csúcs. Próbáljuk meg mohón megszínezni a csúcsokat a számozás sorrendjében. Azaz mindig az éppen soron lévő csúcsnak adjunk egy tetszőleges színt, amit még egyik szomszédjához sem rendeltünk. Akkor tudunk elakadni, ha valamelyik csúcsnál már mind az \(\displaystyle n+1\) színt felhasználtuk valamelyik, már korábban megszínezett szomszédjánál. Amikor egy \(\displaystyle v\) csúcshoz érünk, akkor a számozás miatt a \(\displaystyle v\)-hez tartozó részfában még egy csúcsot sem színeztünk meg, így csak olyan \(\displaystyle v\)-vel szomszédos csúcsok vannak megszínezve, amik \(\displaystyle v\) ősei. Ebből legfeljebb \(\displaystyle |E_v|+1\) van, \(\displaystyle v\) apja és az \(\displaystyle E_v\)-beli élekkel összekötött ősei. Azaz \(\displaystyle v\)-nek korábban legfeljebb \(\displaystyle n+1\) szomszédját színeztük meg. Ez majdnem jó, ha \(\displaystyle n+2\) színnel kéne megszínezni a gráfot akkor kész is lennénk, ám az \(\displaystyle n+1\) színhez még kicsit dolgoznunk kell.

Nevezzünk egy \(\displaystyle v\) csúcsot veszélyesnek, ha \(\displaystyle |E_v|=n\). Ha egy csúcs veszélyes akkor nevezzük az apját biztonságosnak. Vegyünk egy \(\displaystyle v\) veszélyes csúcsot, ekkor \(\displaystyle f(v)\) biztonságos. Azt állítom, hogy ekkor \(\displaystyle |E_{f(v)}|=0\) és \(\displaystyle f(v)\) összes \(\displaystyle v\)-n kívüli \(\displaystyle w\) gyerekére \(\displaystyle |E_w|=0\). Ugyanis ha menne külső él \(\displaystyle f(v)\)-ből vagy valamelyik \(\displaystyle v\)-n kívüli gyerekéből az ősébe, akkor az biztosan \(\displaystyle f(v)\) ősébe menne, így az ez által az él által meghatározott egyértelmű kör tartalmazná az \(\displaystyle f(v)f(f(v))\) élet. Ám már láttuk, hogy ezt az élet tartalmazza \(\displaystyle n\) kör amit az \(\displaystyle E_v\)-beli élek határoznak meg, így nem tartalmazhatja még egy kör. Tehát speciálisan \(\displaystyle f(v)\) nem veszélyes, sőt csak egy ősébe megy él, \(\displaystyle f(f(v))\)-be, és \(\displaystyle f(v)\) egyik gyereke sem veszélyes. Így a veszélyes és biztonságos csúcsok párban vannak: Minden veszélyes csúcs apja biztonságos, és minden biztonságos csúcshoz tartozik pontosan egy gyereke, ami veszélyes.

A színezési algoritmust a következőképpen módosítjuk: Ugyanúgy a számozási sorrendben megyünk végig a csúcsokon, és minden csúcsnál adunk egy tetszőleges színt, amit még nem használtunk korábbi szomszédjánál. Kivéve, ha egy \(\displaystyle u\) biztonságos csúcshoz érkezünk. Ekkor \(\displaystyle |E_u|=0\), így \(\displaystyle u\)-nak még csak egy szomszédja lett megszínezve, az apja, tehát egy szín kivételével mindent adhatunk neki. Így \(\displaystyle n+1 \geq 3\) miatt tudunk két színt választani, hívjuk sárgának és lilának, amiket szabályosan rendelhetünk az \(\displaystyle u\) csúcshoz. Legyen \(\displaystyle v\) az \(\displaystyle u\) csúcs veszélyes gyereke. Nézzük a \(\displaystyle v\) csúcs szomszédait, melyek egy \(\displaystyle E_v\)-beli éllel csatlakoznak \(\displaystyle v\)-hez. Ezeket már megszíneztük, nézzük meg, hogy a lila és sárga szín közül mi szerepel közöttük. Ha egyik se akkor \(\displaystyle u\)-t színezzük lilára, ekkor \(\displaystyle v\)-t tudjuk majd sárgára színezni. Ha legalább az egyik szín szerepel (mondjuk a lila szerepel) akkor \(\displaystyle u\) is legyen lila. Ekkor \(\displaystyle v\)-nek van két ugyanolyan színű szomszédja, és összesen \(\displaystyle n+1\) szomszédját színeztük csak meg előtte, így biztosan marad egy szín, amivel még szabályos \(\displaystyle v\)-t megszínezni.

Tehát az algoritmus még mindig majdnem az, hogy minden csúcsot tetszőleges színnel színezzük, ami még szabályos, csak a biztonságos csúcsoknál a fent leírt módon egy kicsit jobban odafigyelünk, hogy milyen színt használunk. Korábban láttuk, hogy ez a mohó algoritmus csak a veszélyes csúcsoknál jelenthet gondot, ám ezzel a módosítással, hogy minden veszélyes csúcs apját úgy színeztük meg, hogy még a veszélyes csúcsnak is maradjon szabad szín, így az algoritmus nem tud elekadni, tehát meg tudjuk színezni \(\displaystyle n+1\) színnel a csúcsokat úgy, hogy ne legyen két szomszédos azonos színű. Ezzel az állítást igazoltuk.


Statisztika:

Az A. 807. feladat értékelése még nem fejeződött be.


A KöMaL 2021. októberi matematika feladatai