 |
Az A. 866. feladat (2023. december) |
A. 866. Egy gráfot kétszeresen összefüggőnek nevezünk, ha bármelyik csúcsát (és a hozzá tartozó éleket) elvéve a gráf összefüggő marad.
Igaz-e, hogy minden kétszeresen összefüggő, megszámlálhatóan végtelen sok pontból álló gráfban lehet találni olyan, az egyik irányban végtelen sétát (azaz nem feltétlenül különböző csúcsok olyan \(\displaystyle v_1, v_2,\ldots\) sorozatát, melyekre \(\displaystyle v_i\) és \(\displaystyle v_{i+1}\) között mindig van él), amely minden élen legfeljebb egyszer megy át?
Javasolta: Bursics Balázs és Kocsis Anett (Budapest)
(7 pont)
A beküldési határidő 2024. január 10-én LEJÁRT.
Az állítás igaz. Legyen az eredeti gráf \(\displaystyle G\) és vegyünk egy tetszőleges \(\displaystyle F\) feszítőfáját \(\displaystyle G\)-nek. Ha minden csúcs foka véges \(\displaystyle F\)-ben, akkor a Kőnig-lemma állítása szerint találunk egy végetelen hosszú utat a gráfban, ekkor készen vagyunk.
Tehát tegyük fel, hogy van egy végtelen fokú csúcs \(\displaystyle F\)-ben, jelöljön egy ilyet \(\displaystyle v\). Világos, hogy elegendő lenne találni végtelen sok éldiszjunkt kört, melyek mind átmennek a \(\displaystyle v\) csúcson. Sőt, ha adott egy \(\displaystyle p=(v, v_1, \ldots , v_k)\) út, akkor elég végtelen sok olyan kört találni, hogy mindegyik tartalmazza a \(\displaystyle p\) utat, és bármely kettőre igaz, hogy nincs közös éle a \(\displaystyle p\)-beli éleken kívül. Mivel ez azt jelenti, hogy van végtelen sok éldiszjunkt séta \(\displaystyle v\) és \(\displaystyle v_k\) között, amik segítségével világos, hogy tudunk megfelelő végtelen sétát építeni.
Ha elhagyjuk a \(\displaystyle v\) csúcsot az \(\displaystyle F\) gráfból, akkor végtelen sok komponensre esik, nevezzük ezeket a komponenseket \(\displaystyle v\)-komponenseknek. Két \(\displaystyle v\)-komponenst nevezzük szomszédosnak, ha van egy-egy olyan csúcsuk, amik \(\displaystyle G\)-ben éllel össze vannak kötve. Vegyük észre, hogy a kétszeresen összefüggőség miatt minden \(\displaystyle v\)-komponensnek van szomszédja.
Először tegyük fel, hogy minden \(\displaystyle v\)-komponensnek csak véges sok szomszédja van. Ekkor a következőképpen lehet találni végtelen sok \(\displaystyle v\)-t tartalmazó éldiszjunk kört: Tegyük fel, hogy a \(\displaystyle v\)-n áthaladó \(\displaystyle C_1, C_2, \ldots , C_k\) köröket már megtaláltuk. Megmutatjuk, hogy tudunk mutatni még egy, az összestől éldiszjunkt kört. A \(\displaystyle C_1, C_2, \ldots , C_k\) körök összesen véges sok csúcsot tartalmaznak, így összesen véges sok \(\displaystyle v\)-komponensbe metszenek bele, és ezeknek a \(\displaystyle v\)-komponenseknek, mivel mindnek véges sok szomszédja van, így összesen is csak véges sok szomszédja van. Legyen \(\displaystyle A\) egy olyan \(\displaystyle v\)-komponenst, amibe nem metsz bele \(\displaystyle C_i\) kör és nem szomszédos egyik olyan \(\displaystyle v\)-komponenssel sem, amelyikbe valamelyik \(\displaystyle C_i\) belemetsz, és legyen \(\displaystyle B\) az \(\displaystyle A\) egyik szomszédja. Ekkor \(\displaystyle B\)-be se metsz bele egyik \(\displaystyle C_i\) kör se, és van \(\displaystyle a \in A\), \(\displaystyle b \in B\) csúcs, amik \(\displaystyle G\)-ben szomszédosak, így egy kört kapunk, ha \(\displaystyle v\)-ből elsétálunk \(\displaystyle a\)-ba \(\displaystyle F\)-beli élek mentén (ez végig az \(\displaystyle A\) komponensben halad), majd átlépünk \(\displaystyle B\)-be, és \(\displaystyle B\)-ben \(\displaystyle F\)-beli élek mentén visszasétálunk \(\displaystyle v\)-be. Így tényleg tudunk végtelen sok \(\displaystyle v\)-n áthaladó éldiszjunkt kört találni, tehát kész vagyunk.
Már csak az az eset maradt, amikor van egy olyan \(\displaystyle A_1\) \(\displaystyle v\)-komponens, aminek végtelen sok szomszédja van. Legyen \(\displaystyle v_1\) az a csúcs, amivel a \(\displaystyle v\)-komponens a \(\displaystyle v\)-hez csatlakozik. Ha elhagyjuk \(\displaystyle v_1\)-t \(\displaystyle F\)-ből, akkor komponensekre esik, a \(\displaystyle v\)-t nem tartalmazó komponenseket nevezzük \(\displaystyle v_1\)-komponenseknek. Egy \(\displaystyle v_1\)-komponenst és egy \(\displaystyle A_1\)-től különböző \(\displaystyle v\)-komponenst szomszédosnak nevezünk, ha van egy-egy csúcsuk, mely \(\displaystyle G\)-ben össze van kötve.
Ha van végtelen sok olyan \(\displaystyle v\)-komponens, amibe megy közvetlen él \(\displaystyle v_1\)-ből, akkor világos, hogy tudunk végtelen sok, a \(\displaystyle (v,v_1)\) élet tartalmazó kört találni, amik ezen kívül éldiszjunktak, így ekkor készen vagyunk. Mostantól feltesszük, hogy ez nem teljesül, ekkor a \(\displaystyle v_1\)-komponenseknek összesen végtelen sok \(\displaystyle v\)-komponens szomszédja van,
Ha minden \(\displaystyle v_1\)-komponensnek véges sok \(\displaystyle v\)-komponens szomszédja van, akkor végtelens sok \(\displaystyle v_1\)-komponens van. Ekkor a korábbi esethez hasonlóan találhatunk végtelen sok, a \(\displaystyle (v,v_1)\) élet tartalmazó kört, amik ezen az élen kívül éldiszjunktak. Egyedül annyi a változás, hogy ekkor már nem biztos, hogy minden \(\displaystyle v_1\)-komponensnek van \(\displaystyle v\)-komponens szomszédja, de ez nem baj, mert elég, hogy összesen végtelen szomszédjuk van. Tehát ha \(\displaystyle C_1, C_2, \ldots , C_k\) ilyen körök, akkor azon \(\displaystyle v_1\)-komponensek, melyekbe valamelyik \(\displaystyle C_i\) belemetsz, csak véges sokan vannak, és összesen csak véges sok szomszédjuk van, így van egy olyan \(\displaystyle v_1\)-komponens, aminek van olyan \(\displaystyle v\)-komponens szomszédja, hogy egyikükbe sem metsz bele semelyik \(\displaystyle C_i\)-kör, így ezek segítségével találhatunk egy megfelelő \(\displaystyle C_{k+1}\) kört. Tehát ebben az esetben is készen vagyunk.
Ha pedig van olyan \(\displaystyle v_1\)-komponens, ami végtelen sok \(\displaystyle v\)-komponenssel szomszédos, akkor válasszunk egy ilyen \(\displaystyle A_2\) komponenst, és legyen a \(\displaystyle v_1\)-hez csatlakozó csúcsa \(\displaystyle v_2\).
Innen indukcióval ugyanígy folytatjuk. Ha már definiáltuk a \(\displaystyle v, v_1, \ldots , v_k\) csúcsokat, ahol \(\displaystyle v_k\) egy olyan \(\displaystyle v_{k-1}\)-komponens \(\displaystyle v_{k-1}\)-gyel szomszédos csúcsa, mely végtelen sok \(\displaystyle v\)-komponenssel szomszédos, akkor definiálhatjuk a \(\displaystyle v_k\)-komponenseket, melyek az \(\displaystyle F\)-ből \(\displaystyle v_k\) elhagyásával keletkező, \(\displaystyle v_{k-1}\)-et nem tartalmazó komponensek. Értelemszerűen definiáljuk, hogy egy \(\displaystyle v_k\)-komponens mikor szomszédos egy \(\displaystyle A_1\)-től különböző \(\displaystyle v\)-komponenssel. Legyen \(\displaystyle p\) a \(\displaystyle (v, v_1, \ldots , v_k)\) út. Ha \(\displaystyle v_k\) közvetlenül össze van kötve végtelen sok \(\displaystyle v\)-komponenssel, akkor találunk végtelen sok \(\displaystyle p\)-t tartalmzó, \(\displaystyle p\)-n kívül éldiszjunkt kört. Különben a \(\displaystyle v_k\)-komponenseknek összesen végtelen szomszédja van. Ha minden \(\displaystyle v_k\)-komponensnek csak véges sok \(\displaystyle v\)-komponens szomszédja van, akkor az előzőekhez hasonlóan találunk végtelen sok \(\displaystyle p\)-t tartalmzó, \(\displaystyle p\)-n kívül éldiszjunkt kört. Ha pedig van \(\displaystyle A_{k+1}\) \(\displaystyle v_k\)-komponens, aminek végtelen sok \(\displaystyle v\)-komponens szomszédja van, akkor legyen ebben \(\displaystyle v_{k+1}\) a \(\displaystyle v_k\)-val összekötött csúcs, és folytassuk az indukciót.
Ha nem akadunk el, akkor találtunk egy végtelen hosszú utat: \(\displaystyle v, v_1, v_2\ldots\), amivel kész vagyunk. Ellenkező esetben pedig már a folyamat közben találunk valamikor egy megfelelő végtelen sétát.
Statisztika:
18 dolgozat érkezett. 7 pontot kapott: Czanik Pál, Duchon Márton, Holló Martin, Szakács Ábel, Tarján Bernát, Varga Boldizsár, Wiener Anna. 2 pontot kapott: 4 versenyző. 1 pontot kapott: 1 versenyző. 0 pontot kapott: 6 versenyző.
A KöMaL 2023. decemberi matematika feladatai