72
72
Kategória: |
Bizonyítás
- Tétel
|
Évfolyam: |
9. |
Kulcsszó: |
Euler-gráfok |
Lektorálás: |
Nem lektorált |
A gráf Euler-útjának megkeresése
Bizonyítás
Kiválasztunk egy pontot, majd elindulunk a rajta átmenő körön. Ha egy olyan csúcsra értünk, amely része egy másik körnek is amit még nem jártunk be, akkor elindulunk rajta (így ha ezt a kört bejártuk, akkor visszatérünk ahhoz a csúcshoz, ahonnan elhagytuk az eredeti kört, és ezt folytatjuk). Mivel összefüggő a gráf, így az összes kört bejártuk, tehát megtaláltuk az Euler-kört a gráfban.
A fönti algoritmus bárhonnan kezdhető. Most kitörlöm a bizonyítás elején behúzott élt az eredetileg páratlan fokszámú csúcsok között, így megszakítottuk az Euler-kört egy helyen. Így ha az egyik páratlan fokszámú csúcsból kezdjük el a fönt megtalált "kört" bejárni, akkor a másik páratlan fokszámú csúcsba érkezünk meg. Így megrajzoltuk a gráf Euler-útját.
Kössük össze a két páratlan fokszámú csúcsot! Most minden fokszám páros, így elvégezhetjük "A gráf felosztása diszjunkt körökre" című bizonyítást.