 |
A B. 5397. feladat (2024. május) |
B. 5397. Egy gráfra (amely többszörös éleket is tartalmazhat) teljesül, hogy akárhogyan osztjuk szét a csúcsait \(\displaystyle t\) darab diszjunkt halmazba, legalább \(\displaystyle 2t-2\) él különböző halmazok között vezet. Bizonyítsuk be, hogy a gráf éleit ki lehet színezni pirosra vagy kékre úgy, hogy a kék és a piros élek is összefüggő (és minden csúcsot elérő) gráfot alkossanak.
Javasolta: Williams Kada (Cambridge, UK)
(6 pont)
A beküldési határidő 2024. június 10-én LEJÁRT.
Megoldás. A megoldás során élünk a következő elnevezésekkel:
- Egy gráf egy \(\displaystyle t\)-részes partíciójának nevezzük a csúcsainak \(\displaystyle t\) db diszjunkt halmazba való szétosztását.
- Szingulárisnak nevezzük azt a partíciót, amelyben minden csúcs külön halmazba kerül.
- Ha egy \(\displaystyle t\)-részes partíció esetén (ahol \(\displaystyle t \geq 2\)) a gráf legalább \(\displaystyle 2t-2\) éle különböző halmazok között vezet , akkor jó partícióról, egyébként rossz partícióról beszélünk.
- Azt mondjuk, hogy egy gráf teljesíti a partíciós feltételt, ha minden partíciója jó.
- A jó partíciók között fontos szerepet játszanak a feszes partíciók, ezeknél pontosan \(\displaystyle 2t-2\) él megy különböző halmazok között. (Megjegyzés: az egyetlen halmazba való osztásnál persze \(\displaystyle 2 \cdot 1 - 2 = 0\) él vezet különöző halmazok között, de ezt nem tekintjük feszes partíciónak.)
- Egy gráf jól színezhető, ha a gráf éleit ki lehet színezni pirosra vagy kékre úgy, hogy a kék és a piros élek is összefüggő és minden csúcsot elérő gráfot alkossanak (az ilyen színezést jó színezésnek nevezzük).
Indirekt bizonyítunk. Tegyük fel, hogy nem igaz a feladat állítása – azaz van olyan gráf, amely teljesíti a partíciós feltételt, de mégsem színezhető jól. Legyen \(\displaystyle G\) a ,,legkisebb ellenpélda'', pontosabban az összes ellenpélda közül egy minimális csúcsszámú és az ilyen csúcsszámúak között egy minimális élszámú ellenpélda-gráf. Jelölje \(\displaystyle G\) csúcsszámát \(\displaystyle n\), élszámát \(\displaystyle e\). Feltevésünk szerint tehát minden olyan \(\displaystyle G'\) gráf esetén, amelynek \(\displaystyle n' < n\) csúcsa van, vagy \(\displaystyle n'=n\) csúcsa és \(\displaystyle e' < e\) éle van, teljesül, hogy ha teljesíti a partíciós feltételt, akkor jól is színezhető.
(Feltehetjük, hogy \(\displaystyle n \geq 3\), hiszen egy és két csúcsú gráfokra triviálisan teljesül a feladat állítása.)
Biztosak lehetünk benne, hogy \(\displaystyle G\)-ban van feszes partíció, hiszen különben \(\displaystyle G\) bármelyik élét törölve egy ugyanannyi csúcsú, de eggyel kevesebb élű ellenpéldát kapnánk.
I. eset: \(\displaystyle G\)-nek van nem szinguláris feszes partíciója.
Legyen egy nem szinguláris feszes partíció \(\displaystyle V = V_1 \cup V_2 \cup \ldots \cup V_t\) (itt értelemszerűen \(\displaystyle V\) a \(\displaystyle G\) csúcshalmaza, és \(\displaystyle 2 \leq t \leq n-1\)). Az általánosság korlátozása nélkül feltehetjük, hogy \(\displaystyle |V_1| \geq 2\), jelölje \(\displaystyle G_1\) a gráfnak a \(\displaystyle V_1\) által feszített részgráfját.
Ekkor \(\displaystyle G_1\) is teljesíti a partíciós feltételt. Ennek belátásához tekintsük \(\displaystyle V_1\)-nek egy tetszőleges \(\displaystyle V_1 = W_1 \cup W_2 \cup \ldots \cup W_s\) partícióját. Mivel
\(\displaystyle V = \underbrace{W_1 \cup W_2 \cup \ldots \cup W_s}_{V_1} \cup V_2 \cup V_3 \cup \ldots \cup V_t \)
a \(\displaystyle G\) gráf egy \(\displaystyle (s+t-1)\)-részes partíciója, tehát legalább \(\displaystyle 2s+2t-4\) él vezet különböző halmazok között. Ezen élek közül pontosan \(\displaystyle 2t-2\) darab vezet különböző \(\displaystyle V_i\)-k között (a feszes \(\displaystyle V_1 \cup V_2 \cup \ldots \cup V_t\) partícióban különböző halmazok közt futó élek), tehát még legalább \(\displaystyle 2s-2\) olyan élnek kell lennie, amelyek különböző \(\displaystyle W_i\)-k közt vezetnek. Ezzel beláttuk, hogy \(\displaystyle G_1\) teljesíti a partíciós feltételt. Mivel \(\displaystyle |V_1| < n\), ezért ebből következik, hogy \(\displaystyle G_1\) jól színezhető is.
Másrészt tekintsük azt a \(\displaystyle G^*_1\) gráfot is, amelyet úgy kapunk \(\displaystyle G\)-ből, hogy az összes \(\displaystyle V_1\)-beli csúcsot egyetlen \(\displaystyle v^*_1\) csúccsá húzzuk össze (a \(\displaystyle G^*_1\) csúcshalmaza tehát \(\displaystyle V \setminus V_1 \cup \{ v^*_1 \}\); a két \(\displaystyle V_1\)-beli csúcsot összekötő élek törlődnek; a \(\displaystyle v^*_1\) csúcs pedig annyi éllel van összekötve minden \(\displaystyle w \in V \setminus V_1\) csúccsal, mint ahány él vezet \(\displaystyle G\)-ben a \(\displaystyle w\)-ből a \(\displaystyle V_1\) halmazba; a \(\displaystyle V_1\)-et elkerülő élek pedig változatlanul megmaradnak \(\displaystyle G^*_1\)-ben is). Könnyen látható, hogy a \(\displaystyle G^*_1\) gráf is teljesíti a partíciós feltételt (hiszen minden partíciója megfelel a \(\displaystyle G\) egy partíciójának). Mivel \(\displaystyle G^*_1\)-nek \(\displaystyle n\)-nél kevesebb csúcsa van, ezért \(\displaystyle G^*_1\) is jól színezhető.
Mivel \(\displaystyle G\) minden éle vagy \(\displaystyle G_1\)-ben, vagy \(\displaystyle G_1^*\)-ban szerepel, ezért a \(\displaystyle G_1\) és \(\displaystyle G_1^*\) egy-egy jó színezése egyesíthető a \(\displaystyle G\) egy színezésévé, amelyről könnyen látszik, hogy jó színezés (mindegyik szín összefüggő és minden csúcsot elér \(\displaystyle G\)-ben). Ez ellentmond \(\displaystyle G\) ellenpélda voltának, tehát az alábbi, 2. esetnek kell fennálnia.
II. eset: \(\displaystyle G\) egyetlen feszes partíciója a szinguláris partíció.
Mivel a szinguláris partícióban minden él különböző halmazok között vezet, ezért a \(\displaystyle G\) gráfnak \(\displaystyle 2n-2\) éle kell legyen. Tehát az átlagos fokszám \(\displaystyle 4\) alatt van, így van legfeljebb 3-fokú csúcs, egy ilyen csúcsot nevezzünk \(\displaystyle v_0\)-nak. Ha \(\displaystyle v_0\) foka legfeljebb 2 lenne, akkor a \(\displaystyle V = \{v_0 \} \cup ( V \setminus \{ v_0 \})\) 2-részes partíció feszes (vagy rossz) lenne, ellentmondva a II. eset feltételeinek. Tehát \(\displaystyle v^*\) foka pontosan 3.
Tekintsük most azt az \(\displaystyle n-1\) csúcsú \(\displaystyle G_0\) gráfot, amelyet úgy kapunk, hogy \(\displaystyle G\)-ből töröljük a \(\displaystyle v_0\) csúcsot (az éleivel együtt), majd a maradék gráfban \(\displaystyle v_0\) három egykori szomszédja (jelölje őket: \(\displaystyle v_1\), \(\displaystyle v_2\), \(\displaystyle v_3\)) közül kettőt (\(\displaystyle v_1\)-et és \(\displaystyle v_2\)-t) összekötünk egy fantom-éllel.
Belátjuk, hogy \(\displaystyle G^*_0\) teljesíti a partíciós feltételt. A szinguláris partíció esetén minden él különböző csúcsok között megy, márpedig \(\displaystyle G_0\)-nak éppen \(\displaystyle 2n-2 - 3 + 1 = 2(n-1)-2\) éle van.
Tekintsük most \(\displaystyle G_0\) egy tetszőleges nem szinguláris \(\displaystyle V \setminus \{ v_0 \} = V^*_1 \cup V^*_2 \cup \ldots \cup V^*_t\) partícióját. Ekkor persze
\(\displaystyle \{ v_0 \} \cup V^*_1 \cup V^*_2 \cup \ldots \cup V^*_t \)
a \(\displaystyle G\) gráfnak egy nem szinguláris, tehát nem is feszes \(\displaystyle (t+1)\)-részes partíciója, azaz legalább \(\displaystyle 2(t+1)-2+1 = 2t+1\) db él megy különböző halmazok között. Ezek közül csak a \(\displaystyle v_0\)-ból induló 3 él veszik el a \(\displaystyle G_0^*\)-ra való visszatérésnél, tehát legalább \(\displaystyle 2t-2\) él megy különböző halmazok között a \(\displaystyle G_0\) tetszőlegesen választott nem szinguláris \(\displaystyle t\)-részes partíciójánál.
Azt kaptuk, hogy \(\displaystyle G^*_0\) is teljesíti a partíciós feltételt. Mivel \(\displaystyle n-1\) csúcsú, ezért ebből következik, hogy jól színezhető is.
A \(\displaystyle G^*_0\) egy tetszőleges jó színezését ki tudjuk egészíteni a \(\displaystyle G\) egy jó színezésévé a következő módon: \(\displaystyle v_0v_1\) és \(\displaystyle v_0v_2\) élek színe egyezzen meg a \(\displaystyle v_1v_2\) fantom-él színével, míg \(\displaystyle v_0v_3\) él színe legyen ezzel ellentétes. Így mindkét szín eléri a \(\displaystyle v_0\) csúcsot, és a színek összefüggősége is megmarad. Ezzel a II. eset is ellentmondással zárult, azaz a teljes indirekt bizonyításnak is a végére értünk.
Statisztika:
7 dolgozat érkezett. 3 pontot kapott: 1 versenyző. 2 pontot kapott: 1 versenyző. 1 pontot kapott: 3 versenyző. 0 pontot kapott: 1 versenyző. Nem versenyszerű: 1 dolgozat.
A KöMaL 2024. májusi matematika feladatai