Mycielski-konstrukció

A Wikipédiából, a szabad enciklopédiából
Jump to navigation Jump to search

A matematika, azon belül a gráfelmélet területén a Mycielski-konstrukció, avagy egy irányítatlan gráfhoz tartozó Mycielski-gráf az eredeti gráfból megadott módon képezett nagyobb gráf[1]. A konstrukció megtartja az eredeti gráf háromszögmentességét, de növeli a kromatikus számot; a konstrukciót ismételten alkalmazva Mycielski igazolta a tetszőlegesen nagy kromatikus számú háromszögmentes gráfok létezését.

Ismert, hogy a klikkszám egy alsó korlátja a kromatikus számnak. Ezért felvetődik az a kérdés, hogy adható-e a klikkszám segítségével felső korlát a kromatikus számra. Ennek a kérdésnek a megválaszolásához Mycielski egy olyan konstrukciót használt, amely egy gráfot úgy egészít ki, hogy klikkszáma nem változik, míg a kromatikus száma 1-gyel nő.

Definíció[szerkesztés]

Az 5-körgráfból Mycielski-konstrukcióval képezett M4 Grötzsch-gráf.

A Mycielski-konstrukció a csúcshalmazú gráfhoz egy olyan -vel jelölt gráfot rendel, melyben feszített részgráfként szerepel a gráf, továbbá még n+1 csúcs. Ezek a következő elrendezésben: Minden -beli csúcsnak van egy párja, melynek szomszédsága megegyezik a szomszédságával, vagyis azokkal és csak azokkal a csúcsokkal van összekötve, amelyekkel . Az (n+1)-edik új csúcs () mindegyik csúccsal össze van kötve, de egyetlen -vel sincs. Mycielski-gráfoknak azokat a gráfokat nevezzük, amelyek a két csúcsú teljes gráfból, vagyis a két pontból és egyetlen élből álló gráfból előállíthatóak a fenti eljárás egymás után következő véges számú alkalmazásával.

Az ábrán a felső öt csúcs által feszített részgráf az -mal izomorf, az ábrán jelölt többi csúccsal alkotja az -et.

Tétel[szerkesztés]

(Mycielski): Minden egész számra létezik olyan gráf, melyre és . Ez azt jelenti, hogy a kromatikus szám felső korlátja nem függ a klikkszámtól.

Bizonyítás[szerkesztés]

Teljes indukcióval belátjuk, hogy egyetlen -ra sem tartalmaz háromszöget, azaz a klikkszáma 2. -re igaz az állítás, hiszen a 2 pontú teljes gráf. Tegyük fel, hogy -ban nincs háromszög. Indirekt bizonyítással belátjuk, hogy -ben sincs. Tegyük fel, hogy mégis van -ben háromszög. Ennek a háromszögnek legalább az egyik csúcsa nincs -ban, mert az indukciós feltevés szerint nem tartalmaz háromszöget. Ha a háromszög tartalmazza a -vel jelölt csúcsot, akkor a másik két csúcs csak -val jelölt lehet, azok azonban nincsenek összekötve. Már csak az az eset maradt, hogy a háromszög tartalmaz egy -val jelölt csúcsot (). Ekkor a másik két csúcs csak és lehet. pontosan azokkal a csúcsokkal van összekötve, amelyekkel , vagyis , és is háromszöget alkot -ban, ez pedig ellentmond az indukciós feltevésnek.

Teljes indukcióval látjuk be, hogy . -re az állítás egyértelmű. Tegyük fel, hogy az állítás igaz -ra. Indirekt belátjuk, hogy ekkor . színezhető jól színnel a következő módon: Kiszínezzük a -beli csúcsokat színnel jól (az indukciós feltevés miatt ez lehetséges), majd minden -t színére és -t pedig a -edik színnel. Azt kell tehát belátni, hogy erre a színre szükség is van. Mivel részgráfként tartalmazza a -kromatikus gráfot, nem lehet kisebb -nál. Tegyük fel indirekt, hogy . A színeket 1,2,…,-val, csúcs színét -szel jelöljük. Feltehetjük, hogy . Mivel minden szomszédos -vel, minden csúcs színe az 1,2,…, színek valamelyike lehet. Tekintsük a csúcsok által feszített részgráfot, ez -val izomorf. Most megadjuk a csúcsok egy új, színezését, mely csak az 1,2,…, színeket tartalmazza. esetén legyen , minden más esetben . Azoknál az éleknél, melyek végpontjainak színét nem változtattuk meg, nem lehet probléma. Azon csúcsoknak, melyekre teljesül, nincs olyan szomszédja, melyre , mert egy jó színezés volt. Ekkor minden szomszédjára teljesül. Gond csak akkor lehet, ha . azonban nem teljesül, mert ha és szomszédosak, akkor és is, pedig jó színezés. Tehát a csúcsok színezhetőek jól úgy, hogy csak az 1,2,…, színeket használjuk. Ez viszont ellentmond annak, hogy a csúcsok -val izomorf feszített részgráfja k-kromatikus. Emiatt . Ebből és -ből az következik, hogy . A fenti tételnek a következménye, hogy a kromatikus számra nem adható felső becslés a klikkszám segítségével.

A konstrukció iterációja[szerkesztés]

Az M2, M3 és M4 Mycielski-gráfok

Ha a két csúcsból és egyetlen élből álló gráfból kiindulva ismételten alkalmazzuk a Mycielski-konstrukciót, gráfok Mi = M(Mi−1) sorozatát kapjuk, ezeket Mycielski-gráfoknak is nevezzük. A sorozat első néhány eleme az M2 = K2, ami két csúcsból és egy élből áll, az M3 = C5 körgráf és a 11 csúcsból és 20 élből álló Grötzsch-gráf.

Általában véve a sorozat Mi gráfjairól elmondható, hogy háromszögmentesek, (i−1)-szeresen összefüggőek és i-kromatikusak. Az Mi csúcsainak száma 3 · 2i−2 − 1(A083329 sorozat az OEIS-ben). Az Mi éleinek számát (kis i-kre) a következő sorozat adja:

0, 0, 1, 5, 20, 71, 236, 755, 2360, 7271, 22196, 67355, ... (A122695 sorozat az OEIS-ben).

Tulajdonságai[szerkesztés]

Az M4 (Grötzsch-gráf) Hamilton-köre

Általánosítása: gráf feletti kúp[szerkesztés]

A Mycielski-konstrukció egy általánosítása a gráf feletti kúp képzése, amit (Stiebitz 1985) vezetett be, majd (Tardif 2001) és (Lin et al. 2006) tanulmányozták tovább. Ebben a konstrukcióban adott G gráfból úgy képezzük a Δi(G) gráfot, hogy vesszük a G × H tenzorszorzatot, ahol H egy i hosszú út a végén egy hurokéllel, majd a hurokél H csúcsával kapcsolódó összes csúcsot egyetlen szupercsúccsá húzzuk össze. Maga a Mycielski-konstrukció ebben az általánosításban a Δ2(G)-nek felel meg.

Euler-kör a Mycielski-gráfban[szerkesztés]

A -kromatikus Mycielski-konstrukcióval kapott gráf csak -ra tartalmaz Euler-kört. egy pontból, két pontból és egy élből áll, tehát nem tartalmaznak Euler-kört. egy 5 pontból álló kör, amiben van Euler-kör. A konstrukcióból adódik, hogy ugyanannyi típusú csúcs van, mint amennyi típusú, tehát esetén -vel együtt páratlan sok csúcs van. -ben a csúcsnak szomszédja van, ami esetén páratlan, így páratlan fokú. Tehát -ra a Mycielski-gráf nem tartalmaz Euler-kört.

Euler-út a Mycielski-gráfban[szerkesztés]

Az Mycielski-gráf csak és esetén tartalmaz Euler-utat. Könnyen ellenőrizhető, hogy és tartalmaz Euler-utat. A következőkben azt látjuk be, hogy a Mycielski-gráfnak esetén 2-nél több páratlan fokú csúcsa van, ezért nem tartalmaz Euler-utat. Ha -ban fokszáma , akkor -ben fokszáma , hiszen össze van kötve -beli szomszédaival és -vel, de más csúccsal nem. -ben össze van kötve az -beli szomszédaival, illetve azok jelű párjaival, vagyis szomszédja van -ben. Ebből következik, hogy esetén, a Mycielski-gráf -vel jelölt csúcsai páros fokúak, míg az -val jelölt csúcsai páratlan fokúak, hiszen esetén minden csúcs foka 1-gyel nagyobb, mint a párjáé. Ekkor az -k száma mindig nagyobb kettőnél.

Megjegyzés: A probléma úgy is megközelíthető, hogy a konstrukcióból adódóan minden és párnál a fokszám 1-gyel tér el, tehát és különböző paritású, esetén pedig 2-nél több ilyen pár van a gráfban.

Hamilton-kör a Mycielski-gráfban[szerkesztés]

A Mycielski-gráf esetén mindig tartalmaz Hamilton-kört. és nem tartalmaz Hamilton-kört, a 5 hosszú körrel izomorf, tehát tartalmaz. Most belátjuk, hogy ha tartalmaz Hamilton-kört, akkor is. Legyen Hamilton-köre a kör. Ekkor -ben létezik a következő kör, mert a felsorolásban szomszédos csúcsok között a konstrukcióból adódóan mindenhol van él. Ennek a felsorolásnak az első és utolsó csúcsa megegyezik, továbbá minden csúcsot pontosan egyszer tartalmaz, tehát Hamilton-kör. A felsorolás helyességéhez az is kell, hogy páratlan számú csúcsot tartalmazzon, ez a konstrukcióból adódóan teljesül is.

Kapcsolódó témák[szerkesztés]

Irodalom[szerkesztés]

További információk[szerkesztés]

  • Jan Mycielski (1955)