| dbo:abstract
|
- A Chvátal-tétel egy 1972-es gráfelméleti tétel, amely nagyjából azt állítja, hogy ha egy gráfnak elegendően sok éle van, akkor van benne Hamilton-kör. A tétel így szól: Legyenek csúcsú egyszerű gráf fokszámai nagyság szerint .
* Ha teljesül a következő feltétel: (+) -ra, amelyre teljesül, hogy akkor tartalmaz Hamilton-kört.
* Ha olyan pozitív egész számok, amikre (+) nem teljesül, akkor létezik olyan Hamilton-kört nem tartalmazó gráf, melynek fokszámaira -re . Bizonyítás:
* A bizonyítás az Ore-tétel bizonyításával azonosan indul:Tegyük fel indirekt, hogy a gráf kielégíti a feltételt, de nincsen benne Hamilton-kör. Ez az ellenpélda gráfunk legyen . Húzzunk be -be további éleket úgy, hogy az új gráf is ellenpélda legyen (továbbra sincs benne Hamilton-kör). Így kapunk egy gráfot, ami továbbra is ellenpélda, hisz új élek behúzásával "rossz pontpárt" nem lehet létrehozni, de ha még egy élet akárhogyan behúzunk, akkor már tartalmaz a gráf Hamilton-kört. Biztosan van két olyan pont, hogy , hiszen egy csúcsú teljes gráfban ( esetén) van Hamilton-kör. Ekkor viszont a gráfban van Hamilton-kör, tehát -ben van Hamilton-út. Azaz bármely két összekötetlen csúcsa között van Hamilton-út, hisz a két csúcs összekötésével Hamilton-kör keletkezne. ( esetén is van Hamilton-út, esetén pedig a gráfunk egy izolált pont, nincs éle, nincs benne Hamilton-kör). Legyenek a P Hamilton-út csúcsai: , és és . Ha szomszédos a P út valamely pontjával, akkor nem lehet összekötve -gyel, mert ez esetben egy Hamilton-kör lenne. Így tehát nem lehet összekötve legalább darab ponttal, ezért Azaz -ben bármely két összekötetlen -re .Most jön az, ami már különbözik az Ore-tétel bizonyításához képest. Válasszuk meg -t úgy, hogy és maximális legyen az összes összekötetlen csúcspár közül. Az általánosság megszorítása nélkül feltehető, hogy . Így az előbbiekből következik, hogy . Bevezetünk egy új jelölést: . Megmutatjuk, hogy -ra . Az előbb már láttuk, hogy , elég tehát az első egyenlőtlenséget belátnunk. Az első egyenlőtlenség jelentése pedig az, hogy -nek van legalább olyan csúcsa, amelyeknek a fokszámai külön-külön legfeljebb . Tehát a -adik legkisebb fokú csúcs fokszáma nem lehet -nál nagyobb. Ezt akarjuk most belátni, hogy ez teljesül -ben. Ehhez tekintsük minden szomszédjához az és közötti Hamilton-út mentén őt megelőzőt. Láttuk, hogy ezek egyike sem lehet összekötve -nal, mert különben lenne -ben Hamilton-kör. Ezek szerint viszont ezen összesen darab ilyen csúcs bármelyikét választhattuk volna párjául a tekintett Hamilton-út kezdőpontjának, és ha bármelyiknek a fokszáma nagyobb volna az fokszámánál, akkor a maximalizálásánál őt választottuk volna. De -et választottuk, ezért biztos, hogy ezen darab csúcs egyikének sem nagyobb a fokszáma fokszámánál, vagyis -nál. Azaz megkaptuk, hogy tényleg létezik -ben legalább csúcs, melyeknek fokszáma nem nagyobb -nál.A feltételben szereplő helyébe -t írva a fentiekből azt kapjuk, hogy . Ez viszont pontosan azt jelenti, hogy legalább csúcs fokszáma legalább . Mivel azonban -nek darab szomszédja van, így az előbb említett csúcs között biztos van olyan, ami -szel nincs összekötve. Így találtunk két összekötetlen csúcsot, és ezek fokszámösszege legalább , ami viszont ellentmond az Ore-tétel bizonyításában látottaknak (hisz ott azt kaptuk, hogy bármely két összekötetlen csúcsra (hu)
- A Chvátal-tétel egy 1972-es gráfelméleti tétel, amely nagyjából azt állítja, hogy ha egy gráfnak elegendően sok éle van, akkor van benne Hamilton-kör. A tétel így szól: Legyenek csúcsú egyszerű gráf fokszámai nagyság szerint .
* Ha teljesül a következő feltétel: (+) -ra, amelyre teljesül, hogy akkor tartalmaz Hamilton-kört.
* Ha olyan pozitív egész számok, amikre (+) nem teljesül, akkor létezik olyan Hamilton-kört nem tartalmazó gráf, melynek fokszámaira -re . Bizonyítás:
* A bizonyítás az Ore-tétel bizonyításával azonosan indul:Tegyük fel indirekt, hogy a gráf kielégíti a feltételt, de nincsen benne Hamilton-kör. Ez az ellenpélda gráfunk legyen . Húzzunk be -be további éleket úgy, hogy az új gráf is ellenpélda legyen (továbbra sincs benne Hamilton-kör). Így kapunk egy gráfot, ami továbbra is ellenpélda, hisz új élek behúzásával "rossz pontpárt" nem lehet létrehozni, de ha még egy élet akárhogyan behúzunk, akkor már tartalmaz a gráf Hamilton-kört. Biztosan van két olyan pont, hogy , hiszen egy csúcsú teljes gráfban ( esetén) van Hamilton-kör. Ekkor viszont a gráfban van Hamilton-kör, tehát -ben van Hamilton-út. Azaz bármely két összekötetlen csúcsa között van Hamilton-út, hisz a két csúcs összekötésével Hamilton-kör keletkezne. ( esetén is van Hamilton-út, esetén pedig a gráfunk egy izolált pont, nincs éle, nincs benne Hamilton-kör). Legyenek a P Hamilton-út csúcsai: , és és . Ha szomszédos a P út valamely pontjával, akkor nem lehet összekötve -gyel, mert ez esetben egy Hamilton-kör lenne. Így tehát nem lehet összekötve legalább darab ponttal, ezért Azaz -ben bármely két összekötetlen -re .Most jön az, ami már különbözik az Ore-tétel bizonyításához képest. Válasszuk meg -t úgy, hogy és maximális legyen az összes összekötetlen csúcspár közül. Az általánosság megszorítása nélkül feltehető, hogy . Így az előbbiekből következik, hogy . Bevezetünk egy új jelölést: . Megmutatjuk, hogy -ra . Az előbb már láttuk, hogy , elég tehát az első egyenlőtlenséget belátnunk. Az első egyenlőtlenség jelentése pedig az, hogy -nek van legalább olyan csúcsa, amelyeknek a fokszámai külön-külön legfeljebb . Tehát a -adik legkisebb fokú csúcs fokszáma nem lehet -nál nagyobb. Ezt akarjuk most belátni, hogy ez teljesül -ben. Ehhez tekintsük minden szomszédjához az és közötti Hamilton-út mentén őt megelőzőt. Láttuk, hogy ezek egyike sem lehet összekötve -nal, mert különben lenne -ben Hamilton-kör. Ezek szerint viszont ezen összesen darab ilyen csúcs bármelyikét választhattuk volna párjául a tekintett Hamilton-út kezdőpontjának, és ha bármelyiknek a fokszáma nagyobb volna az fokszámánál, akkor a maximalizálásánál őt választottuk volna. De -et választottuk, ezért biztos, hogy ezen darab csúcs egyikének sem nagyobb a fokszáma fokszámánál, vagyis -nál. Azaz megkaptuk, hogy tényleg létezik -ben legalább csúcs, melyeknek fokszáma nem nagyobb -nál.A feltételben szereplő helyébe -t írva a fentiekből azt kapjuk, hogy . Ez viszont pontosan azt jelenti, hogy legalább csúcs fokszáma legalább . Mivel azonban -nek darab szomszédja van, így az előbb említett csúcs között biztos van olyan, ami -szel nincs összekötve. Így találtunk két összekötetlen csúcsot, és ezek fokszámösszege legalább , ami viszont ellentmond az Ore-tétel bizonyításában látottaknak (hisz ott azt kaptuk, hogy bármely két összekötetlen csúcsra (hu)
|
