A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. Megmutatjuk, hogy pontosan a következő gráfok vaktában bejárhatóak: a teljes gráfok, a körök és az ún. teljes páros gráfok közül azok, amelyeknél a csúcsok halmaza két azonos elemszámú részre osztható úgy, hogy két csúcs pontosan akkor van éllel összekötve, ha különböző részbe tartozik. Egyszerűen látható, hogy a felsorolt gráfok valóban vaktában bejárhatóak. Tegyük fel ezután, hogy vaktában bejárható gráf, amelynek csúcsa van. Jelölje a gráf tetszőleges (az csúcsból induló) Hamilton-útját. Ha a gráf bejárását az csúcsból kezdjük és az úton eljutunk -be, akkor a vaktában bejárhatóság miatt el kell jutnunk -be is, ami azt jelenti, hogy és is össze van éllel kötve, azaz létezik az (Hamilton-)kör. Megmutatjuk, hogy ha tartalmaz háromszöget, akkor teljes. Jelöljön egy háromszöget, akkor a gráf bejárható egy út mentén, és az előbbiek szerint itt és között is megy él. Ha valamelyik csúcs nincs összekötve pl. -vel, akkor induljunk el -ből a út mentén. Itt megakadunk, nem tudunk -be jutni, és ez ellentmondás. Tehát egy háromszög csúcsai a gráf minden csúcsával össze vannak kötve. Legyen egy tetszőleges csúcsa -nek; az előbbiek szerint ekkor is háromszög, ezért minden csúccsal össze van kötve, azaz teljes. A következőkben feltehetjük, hogy a gráfban nincs háromszög. Ha a ‐ továbbiakban rögzített ‐ körön kívül nincsenek további élek -ben, akkor nincs mit bizonyítanunk; tegyük fel ezért, hogy létezik e kör éleitől különböző él is. Definiáljuk (e kör szerint) az és pontok távolságát a képlettel; egy él hosszán pedig értsük a végpontjainak a távolságát. Tekintsünk egy, az körhöz nem tartozó olyan élt, amelynek a hossza minimális; feltehető, hogy ez alakú, alkalmas -re. Ekkor az pontok között nem vezet a körön kívüli él, hiszen annak hossza az hosszánál kisebb lenne. Mivel a gráf háromszögmentes, nincs összekötve -gyel. Tegyük fel, hogy nincs összekötve -gyel sem; ekkor azonban nem lehet összekötve az , , , pontok egyikével sem, hiszen egy ilyen él hossza kisebb lenne, mint -é. Induljunk el -ből az út mentén. Iménti következtetésünk szerint innen az , , , csúcsok egyikére sem tudunk továbblépni, ami ellentmondás. Tehát össze van kötve -gyel. Ezzel beláttuk, hogy minimális hosszúságú él ,,egy egységgel való elforgatottja'' is (minimális hosszúságú) él, azaz
valamennyi is él, minden -re. Hasonlóan tételezzük fel, hogy nincs összekötve sem -gyel sem pedig -gyel; szerint ekkor szükségképpen . Így az , , , közül legfeljebb csak az -vel lehet összekötve. Akkor viszont az utat vagy egyáltalán nem, vagy csupán az -ig tudjuk folytatni, ott viszont vagy felé továbbhaladva az , vagy felé továbbhaladva az pontot kényszerülünk kihagyni; tehát össze van kötve -gyel vagy -gyel. Az -gyel azonban nem lehet összekötve, hiszen akkor háromszög lenne; így az -gyel van összekötve. Ebből következik, hogy a körön kívüli élek hosszának minimuma . Megmutatjuk, hogy mindegyik csúcsa össze van kötve és valamelyikével. Ha ugyanis egy ezek egyikével sincs összekötve, akkor az utat nem tudjuk befejezni. A háromszögmentesség miatt (az és közül) csak -mal lehet összekötve, ezért az -gyel, az -mal, , az -gyel, az -mal, stb. Ugyanezt azonban szerint elmondhatjuk helyett bármelyik minimális hosszúságú élből kiindulva, és akkor és helyett általában az és csúcsokról mondható el, hogy minden csúcs ezek valamelyikével össze van kötve, éspedig az -gyel, pedig az -mal. Mivel itt és értéke tetszőleges, ez éppen azt jelenti, hogy páros, és -ben két csúcs között pontosan akkor megy él, ha indexeik különböző paritásúak.
Frenkel Péter (Fazekas M. Főv. Gyak. Gimn. III. o.t.) |
|