12. FEJEZET: Vegyük a legnagyobbat, a legszélsőt! Gráfelmélet
Ebben a fejezetben folytatjuk a ,,vegyük a legszélsőt" gondolatra épülő vizsgálódásokat. Közelebbről azt vizsgáljuk, hogyan van jelen a gondolat a gráfelméletben.
Körmérkőzések
Feladat: 12.1. [
176]
Egy körmérkőzés során mindenki mindenkivel egyszer játszott, és egyetlen mérkőzésnek sem volt döntetlen az eredménye. Bizonyítandó, hogy van olyan résztvevő, aki minden versenytársát megemlíti, ha felsorolja az általa legyőzötteket, valamint azokat, akiket az általa legyőzöttek legyőztek. (Kürschák-verseny, 1954.)
Az állítást gráfelméleti formában így fogalmazhatjuk:
Definíció. Egy irányított gráfban egy pontot akkor nevezünk
,,pszeudogyőztesnek", ha belőle minden más pont egy, vagy két élű irányított úttal elérhető.
Tétel. Minden véges tournamentben van pszeudogyőztes.
Feladat: 12.2. Igaz-e a
12.1. feladat állítása végtelen tournamentben is?
Feladat: 12.3. a) Egy 10 versenyzős körmérkőzésen nem volt döntetlen. Bizonyítsuk be, hogy a versenyzők sorbaállíthatók úgy, hogy mindenki legyőzte a követlenül utána állót.
b) Bizonyítsuk be, hogy véges tournamentben van irányított Hamilton-út. Azaz a pontok sorba rakhatók úgy, hogy minden pontból az utána következőbe indul él.
Megjegyzés. Rédei László bebizonyította, hogy tournamentben a Hamilton-utak száma mindig páratlan. Ebből is következik a feladat állítása, ám ennek bizonyítása sokkal nehezebb.
Feladat: 12.4. Kutató munka:
* Hogyan jellemezhetők másképp az olyan tournamentek, amelyekben egyetlen irányított Hamilton-út van?
Utak, körök és a fokszám
Feladat: 12.5. Egy véges egyszerű gráf minden pontjának foka legalább kettő. Bizonyítandó, hogy ekkor van benne kör.
Megjegyzés: A feladathoz l. a
14.20. feladatot, valamint az alábbi
12.6-
12.15. feladatokat.
Feladat: 12.6. Bizonyítsuk be, hogy ha egy véges egyszerű gráfban minden pont foka legalább három, akkor van benne kör átlóval.
Feladat: 12.7. Bizonyítsuk be, hogy ha egy véges egyszerű gráfban minden pont foka legalább három, akkor van benne páros hosszúságú kör.
Feladat: 12.8. [
180]
Bizonyítsuk be, hogy ha egy véges egyszerű gráfban minden pont foka legalább három, akkor nincs olyan
k≥3 egész szám, amelyre a gráf minden körének hossza osztható volna
k-val.
Feladat: 12.9. Bizonyítsuk be, hogy ha egy egyszerű véges gráf minden pontja legalább harmadfokú, akkor a benne található körök hosszainak legnagyobb közös osztója kettő vagy egy. Mindkét eset elő is fordul.
Feladat: 12.10. Egy egyszerű véges gráfban minden pont foka legalább
k, ahol
k≥2. Bizonyítandó, hogy van olyan kör a gráfban, amelynek legalább
k+1 pontja van.
Garantálható-e egy pontosan
k+1 pontú kör is e feltétel mellett?
Feladat: 12.11. Egy gráfban minden pont foka legalább kettő. Bizonyítsuk be, hogy van olyan kör, amely egy pontot és annak összes szomszédját tartalmazza.
Hamilton-körök
Feladat: 12.12. Igazoljuk, hogy ha egy nyolcpontú egyszerű gráfban minden pont foka legalább négy, akkor van benne Hamilton-kör.
Feladat: 12.13. * Láttuk már, hogy egy
2n pontú gráfban minden pont foka legalább
n, akkor a gráf összefüggő, sőt kétszeresen összefüggő. (Lásd a
GR.II.1.8. feladatot.) Most bizonyítsuk be az alábbi tételt, amelyből mind a
9.11. feladat állítása, mind ezek az állítások következnek.
Dirac tétele. Ha egy
2n pontú gráfban minden pont foka legalább
n, akkor a gráfnak van Hamilton-köre.
Feladat: 12.14. Egy
2n pontú egyszerű gráfban minden pont foka legalább
n+1. Bizonyítsuk be, hogy van benne olyan Hamilton-kör, amelynek be van húzva
n darab, páronként pontdiszjunkt átlója.
Feladat: 12.15. Bizonyítsuk be, hogy ha egy
n pontú gráf bármely két össze nem kötött pontjára igaz, hogy e két pont fokszámának összege legalább
n, akkor a gráfnak van Hamilton-köre.
A ,,Turán-tétel" két egyszerű esete
Feladat: 12.16. Egy kilenc csapatból álló bajnokságban egy adott időpillanatig összesen 21 mérkőzést játszottak le (semelyik két csapat nem játszott egymással kétszer). Bizonyítsuk be, hogy van három csapat, amelyek közül mindegyik játszott a másik kettővel.
Feladat: 12.17. Bizonyítsuk be a háromszögre vonatkozó
Turán-tételt: Ha egy
n pontú egyszerű gráfnak több mint
⌊
n2
/4⌋ éle van, akkor van benne háromszög. Másrészt van olyan
n pontú és
⌊
n2
/4⌋ élű gráf, amelyben nincs háromszög.
Megjegyzés. Erre a tételre több bizonyítást is adunk, lásd még a
GR.II.2.10. feladat megoldását és a
GR.II.6.1. feladat megoldását.
Feladat: 12.18. A Turán-tétel azonban általánosabb, mint a
12.17. feladatban szereplő tétel, amely csak háromszögekről szól. Az általános Turán-tétel minden
k-ra megadja, hogy egy
n pontú gráfban hány él kell ahhoz, hogy biztosan legyen benne teljes
k-as gráf. Bizonyítsuk be az alábbi
k=4 esetet:
Turán-tétel.
Ha egy
n pontú gráfban van legalább
n2
/3 él, akkor van benne négypontú teljes gráf.
A Turán-tétel általános esetével és további analóg kérdésekkel a speciális gráfelméleti témákat tárgyaló GR.II. kötetben fogunk foglalkozni.
Néhány további feladat
Feladat: 12.19. Egy
n pontú teljes gráf éleit megszíneztük, minden él pontosan egy színt kapott. A színezéshez legalább
n színt használtunk. Mutassuk meg, hogy van olyan háromszög a gráfban, amelynek minden éle különböző színű.
Feladat: 12.20. Bizonyítsuk be, hogy egy fa összes leghosszabb útja lefogható egy ponttal (vagyis van olyan pont, amelyen a fa összes útja kereszül megy).