7. Gráfok élszínezése
7. Teljes párosítás létezése reguláris páros gráfban. Gráfok élszínezése, χe(G) fogalma és viszonya ∆(G)-hez. Vizing-tétel (biz. nélkül), Kőnig tétele a páros gráfok élkromatikus számáról.
Reguláris páros gráfok
Tétel
Ha a $G = (A,B;E)$ páros gráf $d$-reguláris, ahol $d \geq 1$ tetszőleges egész, akkor $G$-ben van teljes párosítás.
Mivel $G$ minden élének pontosan az egyik végpontja $A$-béli és minden $A$-béli csúcsra $d$ él illeszkedik, ezért $G$ élszámára $|E| = d \cdot |A|$ adódik. Hasonlóan kapjuk, hogy $|E| = d \cdot |B|$. Ezekből tehát $d \cdot |A| = d \cdot |B|$ és így $|A| = |B|$ adódik.
Legyen $X \subseteq A$ tetszőleges és jelölje $E_X$ az $X$ csúcsaira illeszkedő élek halmazát; ezeknek a $B$-béli végpontja tehát $N(X)$-béli. Hasonlóan a fentiekhez, mivel minden $X$-béli csúcsra pontosan $d$ darab $E_X$-béli él illeszkedik, ezért $|E_X| = d \cdot |X|$.
$N(X)$ csúcsaira nem csak $E_X$-béli élek illeszkedhetnek, de annyi ezekről is elmondható, hogy mindegyikre legföljebb $d$ darab $E_X$-béli él illeszkedik; így $|E_X| \leq d \cdot |N(X)|$. Ezek összevetéséből $d \cdot |X| \leq d \cdot |N(X)|$ és így $|X| \leq |N(X)|$ adódik. Ezzel beláttuk, hogy a gráf teljesíti a Frobenius-tétel feltételeit.
Élszínezések és élkromatikus szám
Definíció
Definíció. Legyen $G$ egy gráf és $k \geq 1$ egész szám. A $G$ gráf $k$ színnel él színezhető, ha $G$ minden éle kiszínezhető $k$ adott (tetszőleges) színnel úgy, hogy $G$ bármely két szomszédos (vagyis közös csúcsra illeszkedő) élének a színe különböző. A $G$ élkromatikus száma $k$ (gyakori jelölése: $\chi'(G)$), ha $G$ $k$ színnel él színezhető, de $(k-1)$-gyel már nem.
Az élszínezés lényege tehát az, hogy az azonos csúcsból induló éleknek mindenképpen különböző színt kell kapniuk. Ebből azonnal következik egy alsó becslés: az élkromatikus szám nem lehet kisebb a gráf maximális fokszámánál ($\Delta(G)$), hiszen a maximális fokszámú csúcsból induló élek mind különböző színt igényelnek.
Kidolgozott példa: Él-színezés
8.2. Feladat
Határozzuk meg az alábbi $G$ gráf élkromatikus számát, $\chi_e(G)$-t!
Megoldás levezetése
A gráf élei megszínezhetők négy színnel. Ezt bizonyítja az alábbi ábrán látható konstrukció, ahol minden csúcsra illeszkedő élek különböző színt kaptak:
Annak indoklásához, hogy ennél kevesebb szín nem elég, tekintsük például a $b$ csúcsra illeszkedő négy élt: ezek közül bármely kettő szomszédos (hiszen a $b$ csúcson találkoznak), így közülük semelyik kettő nem színezhető azonos színűre.
Megmutattuk tehát, hogy $G$ élei megszínezhetők négy színnel, de hárommal nem, így a gráf élkromatikus száma: $\chi_e(G) = 4$.
Az élkromatikus szám alsó becslése
Állítás
Állítás. Minden (hurokélmentes) $G$ gráfra $\Delta(G) \leq \chi_e(G)$ teljesül.
Legyen $v$ egy $\Delta(G)$ fokú csúcs $G$-ben. Ekkor a $v$-re illeszkedő $\Delta(G)$ darab élnek $G$ tetszőleges élszínezésében csupa különböző színt kell kapnia, hiszen bármely kettő szomszédos a $v$ csúcson keresztül. Így $G$ minden élszínezése legalább $\Delta(G)$ színt használ, amiből $\Delta(G) \leq \chi_e(G)$ valóban következik.
Vizing tétele
8.4. Tétel
Tétel. (Vizing tétele) Minden $G$ egyszerű gráfra $\chi_e(G) \leq \Delta(G) + 1$ teljesül.
Vizing tétele szerint egy egyszerű gráf élkromatikus száma csak kétféle értéket vehet fel: vagy pontosan a maximális fokszámmal egyenlő ($\Delta(G)$), vagy eggyel nagyobb annál ($\Delta(G) + 1$).
Ez az eredmény rendkívül mély, hiszen azt mondja ki, hogy az élszínezés hatékonysága szinte kizárólag a legzsúfoltabb csúcstól függ, és legfeljebb csak egyetlen "plusz" színre lehet szükség a konfliktusok feloldásához.
Példa: Teljes gráf élkromatikus száma
8.5. Feladat
Határozzuk meg a tizenegy csúcsú teljes gráf élkromatikus számát, $\chi_e(K_{11})$-et!
Megoldás levezetése
$K_{11}$ minden csúcsának a foka tíz, így $\Delta(K_{11}) = 10$. Meg fogjuk mutatni, hogy $K_{11}$ élei nem színezhetők meg tíz színnel, vagyis $\chi_e(K_{11}) > 10$. Mivel Vizing 8.4. Tételéből $\chi_e(K_{11}) \leq 11$ következik, ezért ezekből $\chi_e(K_{11}) = 11$ adódni fog.
Tegyük fel indirekt, hogy $K_{11}$ éleit megszímeztük tíz színnel, legyen ezek közül egy a piros.
Mivel minden csúcs foka tíz és a színek száma is tíz, ezért minden csúcsra kell illeszkedjen piros színű él. Mivel egynél több piros él persze egy csúcsra sem illeszkedhet, ezért ebből következik, hogy a piros élek teljes párosítást alkotnak $K_{11}$-ben.
Ez azonban nyilván lehetetlen: páratlan csúcsszámú gráfban nem létezhet teljes párosítás.
Így tehát $K_{11}$ élei nem színezhetők meg tíz színnel, ezért $\chi_e(K_{11}) = 11$.
Kőnig élszínezési tétele
Tétel
(Kőnig élszínezési tétele) Minden $G = (A,B;E)$ páros gráfra $\chi_e(G) = \Delta(G)$ teljesül.
Legyen $d = \Delta(G)$. A tételt először abban az esetben bizonyítjuk be, ha $G$ $d$-reguláris. Ha $d \geq 1$, a korábbi következmény szerint $G$-ben létezik egy $M_1$ teljes párosítás. Szímezzük ki $M_1$ éleit 1-es színnel, majd hagyjuk el őket $G$-ből. A kapott $G_1$ gráf nyilván $(d-1)$-reguláris lesz, így az eljárás $d$-szeri megismétlésével egy helyes, $d$ színnel való élszínezést kapunk.
Ha $G$ nem reguláris, akkor kiegészítjük további élekkel (és szükség esetén csúcsokkal) úgy, hogy egy $d$-reguláris $G'$ gráfot kapjunk.
- Ha $|A| \neq |B|$, adjunk a kisebbik osztályhoz annyi új csúcsot, hogy azonos méretűek legyenek.
- Húzzunk be új éleket tetszőleges olyan $a \in A, b \in B$ csúcspár közé, ahol $d(a) < d$ és $d(b) < d$.
Az eljárás végén kapott $G'$ gráf már $d$-reguláris, így az első bekezdés szerint $d$ színnel él-színezhető. Mivel azonban $G$ minden éle szerepel $G'$-ben is, ezzel $G$-nek is megadtunk egy helyes élszínezését $d = \Delta(G)$ színnel. Ebből $\chi_e(G) = \Delta(G)$ valóban következik.
Interaktív Élszínező Labor
Összefoglaló Kvíz
Kromatikus Összefüggések
Vidd az egeret a kártyák fölé a helyes válaszért!
#01 Alsó becslés
Milyen univerzális alsó korlát adható az élkromatikus számra a fokszám alapján?
#02 Vizing-tétel
Hányféle értéket vehet fel egy egyszerű gráf élkromatikus száma a maximális fokszám függvényében?
#03 Páros gráfok
Mennyi a páros gráfok élkromatikus száma?
#04 Teljes párosítás
Milyen garanciát ad a regularitás a párosításokra nézve?
Tudtad-e?
ÓRARENDKÉSZÍTÉS
Az iskolai órarendek készítése valójában egy élszínezési probléma. Ha a tanárok és osztályok közötti órákat élekként ábrázoljuk, az élkromatikus szám megadja a minimális számú idősávot, amely alatt az összes óra konfliktusmentesen megtartható.
PÁROS GRÁFOK ELŐNYE
Páros gráfoknál az élszínezés mindig optimális, hiszen $\chi_e(G) = \Delta(G)$. Ez azt jelenti, hogy sosem kell "pazarolnunk" extra színt (vagy idősávot) a maximális fokszámon felül, köszönhetően Kőnig tételének.
A VIZING-KÜLÖNBSÉG
Vizing tétele szerint az általános gráfoknál is legfeljebb csak egyetlen extra színre lehet szükség a maximális fokszám felett. Ez a "plusz egy" szín választja el a viszonylag egyszerűen színezhető gráfokat a strukturálisan bonyolultabbaktól.
KÖRMÉRKŐZÉSEK
Egy bajnokság fordulóinak beosztása egy teljes gráf élszínezése. Ha a csapatok száma páratlan (pl. $K_{11}$), akkor matematikailag bizonyítható, hogy több forduló kell, mint ahány meccse van egy csapatnak, mert minden körben valaki kénytelen pihenni.