Feladat: 926. matematika gyakorlat Korcsoport: 14-15 Nehézségi fok: átlagos
Megoldó(k):  Rátky György 
Füzet: 1965/április, 158 - 159. oldal  PDF  |  MathML 
Témakör(ök): Gráfok összefüggősége, Irányított gráfok, Kombinatorikai leszámolási problémák, Gyakorlat
Hivatkozás(ok):Feladatok: 1964/szeptember: 926. matematika gyakorlat

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.

Legyen az 1. ábra köreinek érintkezési pontja C, a két kört összekötő körív két végpontja A és B. Az ábrának a feltételek szerinti megrajzolása ‐ más szóval bejárása ‐ azonos feladat a 2. ábra megrajzolásával, hiszen nem lényeges a vonaldarabok alakja, csak az, hogy az A, B, C csomópontok egyes párjai hány közvetlen útvonallal vannak összekötve.

 
1. ábra
 
2. ábra

A 2. ábráról jobban látjuk, hogy pl. az A és C közti két útvonal a feltételek szerint egymással felcserélhető. Így elegendő lesz felsorolni a bejárás egymás utáni csomópontjait. Minden ilyen betűsorrendben az A és C közti első átmenet 2-féleképpen választható, ugyanígy a B és C közti első átmenet is (a második átmenetekben persze már nincs választás). Ezért a bejárások száma a csomópontok különböző felsorolásai számának 2⋅2-szerese lesz.
A bejárás kezdőpontja és végpontja csak az A vagy a B csomópont lehet, mert ezekbe páratlan számú út fut be, C-be viszont páros számú. Ugyanis egy ponton áthaladva 2 oda befutó utat rajzolunk meg, az érkezését és a továbbhaladásét, ezért A-n és B-n csak egyszer-egyszer haladhatunk át, a harmadik útszakaszt rajzunknak vagy a kezdő, vagy a befejező szakaszában kell bejárnunk. Másrészt így a C-ből kiinduló 4 útszakasz bejárása is lehetséges lesz 2 rajta való áthaladással.
Ábráink tükrösek AB felező merőlegesére, mint tengelyre, ezért elég azokat a felsorolásokat megadnunk, amelyeknek kezdőpontja mondjuk A (tehát végpontjuk B). Ezek tükörképei adják a B-ben kezdődő (és A-ban végződő) bejárásokat, és a megadandó felsorolások számát ezért ismét 2-vel szoroznunk kell.
A felsorolás első két pontja vagy AB, vagy AC. Az előbbi után csak C következhetik, az utóbbi után viszont vagy visszamegyünk A-ba, vagy tovább megyünk C-be, így a felsorolás első három pontja ABC, ACA vagy ACB. Az első két esetben már ennyiből kiadódik a befejezés: ABCACB (I.), ill. ACABCB (II.) ‐ ugyanis ABCB rajzunk idő előtti befejezését jelentené. A harmadik eset 2-féleképpen fejezhető be: ACBCAB (III.) és ACBACB (IV.)
Ezek szerint A-ból kiindulva a csomópontok egymásutánja 4-féle lehet, így pedig a megrajzolási lehetőségek száma az AC, BC útpárok, valamint a B-ből való elindulás figyelembevételével 4⋅2⋅2⋅2=32.
 Rátky György (Budapest, Berzsenyi D. g. II. o. t.)
 

II. megoldás. Az I. megoldásban látott egyszerűsítéseket ismét felhasználjuk. Tekintsük az 1. ábrát egy vasúti hálózat vázlatának, a csomópontokban váltókkal. A C csomópont váltói az itteni két áthaladás céljára kétféleképpen állíthatók be, vagy az ugyanazon csomópontok felé vivő vonalakat összekötve, az érkező vonatot ugyanoda továbbítva, ahonnét érkezett, vagy mindkétszer keresztülfutva C-n (3. ábra a és b).
 
3. ábra
 
4. ábra)

Így a hálózat képe a 4a, ill. 4b ábrára egyszerűsödik. Az a) esetben az A-beli hurkot nyilvánvalóan az AB átmenet előtt kell bejárnunk, a B-beli hurkot pedig utána (a fenti II. felsorolás). A b) esetben a bejárás ABAB, és 3 különböző felsorolást kapunk aszerint, hogy a C-n át nem futó AB ágat az 1., a 2. vagy a 3. átmenetben rajzoljuk (a fenti I., IV., ill. III. felsorolás).