|
Feladat: |
B.4079 |
Korcsoport: 18- |
Nehézségi fok: könnyű |
Megoldó(k): |
Éles András , Kalina Kende , Keresztfalvi Tibor , Kiss Melinda Flóra , Kiss Réka , Lovas Lia Izabella , Nagy Donát , Perjési Gábor , Réti Dávid , Strenner Péter , Tossenberger Anna , Tóth László Márton , Tubak Dániel , Varga László , Zieger Milán |
Füzet: |
2008/november,
478 - 479. oldal |
PDF file |
Témakör(ök): |
Gráfok összefüggősége, Indirekt bizonyítási mód, Feladat |
Hivatkozás(ok): | Feladatok: 2008/március: B.4079 |
|
Legyen olyan egyszerű gráf, amelyben a leghosszabb út élből áll, és minden csúcs foka legalább . Mutassuk meg, hogy -nek minden éle benne van egy körben. (Útnak nevezzük egymáshoz csatlakozó élek egy olyan sorozatát, amely minden csúcsot legfeljebb egyszer érint.)
|
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. I. megoldás. Tekintsünk a gráfban egy tetszőleges élt (ami a és a csúcsot köti össze). Egészítsük ki ezt egy tovább már nem bővíthető úttá. (Ez biztosan megtehető, hiszen a feladat egyik feltétele szerint minden út hossza legfeljebb lehet.) Ha és a csúcsokat él köti össze, akkor ezzel az éllel a út kört határoz meg, ami tartalmazza a kiválasztott élt. ( nem állhat az egyetlen élből, mivel akkor mindkét csúcs foka 1 lenne); a továbbiakban feltehetjük, hogy nem ez a helyzet. A fokszámokra adott feltétel miatt és is legalább csúccsal van összekötve; ezek a csúcsok valamennyien -hoz tartoznak, ellenkező esetben ugyanis legalább az egyik végén bővíthető lenne egy további éllel és annak (-n kívül eső) végpontjával. Mivel feltettük, hogy és nincs egymással összekötve, a és a csúcsok valamennyi szomszédja a pontok közül kerül ki; ezek száma . Ebből következik, hogy a pontok között van olyan , amely -nel és -mel is össze van kötve. Így az minden éle benne van a vagy az körök valamelyikében, tehát a él is.
II. megoldás. , mint minden gráf összefüggő komponensekre bomlik, és ezen komponensek mindegyikére teljesül a feladat valamennyi feltétele. Az állítást ezért elegendő összefüggő gráfokra igazolnunk; ennek jegyében feltehetjük, hogy összefüggő. Indirekt bizonyítunk: tegyük föl, hogy az és csúcsokat öszekötő él nincs benne körben. Ha a gráfból ezt az élt elhagyjuk, a kapott gráf már nem összefüggő, hiszen benne az -et -vel összekötő utat az éllel (immáron -ben) kiegészítve kört kapnánk. Mivel az él visszahúzásával az összefüggő gráffá válik, két összefüggő komponensre bomlik: az csúcsot tartalmazó komponensét jelölje (). Legyen felső egész-része ; megmutatjuk, hogy az gráfban létezik az -ből induló, hosszúságú út. Ehhez csupán azt kell észrevennünk, hogy -ben minden, -től különböző pont foka legalább (ugyanitt foka legalább ). Ha pedig egy (-beli) út hossza , akkor foka legalább lévén, az pontokon kívül még legalább egy további csúccsal is össze van kötve, tehát az előbbi út 1-gyel meghosszabbítható, stb. Végül, ha egy hosszúságú út (-ben) -ből -be, hasonlóan egy hosszúságú út (-ben) -ből -ba, akkor az ezek összekapcsolásával keletkező út hossza , ami ellentmondás.
|
|