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. A pontok közti élek kétfélék lehetnek aszerint, hogy egyező, illetve különböző színű pontokat kötnek össze. Az előbbieket nevezzük , az utóbbiakat típusú éleknek.
Tekintsünk egy lépést. Tegyük föl, hogy az ennek során átszínezésre kiszemelt magányos pontból darab és darab típusú él indul ki. Ekkor ‐ a magányos pont definíciója szerint ‐ Az átszínezés után a pontból darab és darab típusú él indul ki. Tehát a típusú élek száma (az egész gráfban!) -gyel csökkent. Mivel kezdetben véges sok típusú él volt, azért csak véges számú lépést tehetünk; ez éppen azt jelenti, hogy néhány lépés után már nem lesz magányos pont.
Fazekas Borbála (Debrecen, KLTE Gyak. Ált. Isk., 8. o. t.) dolgozata alapján
Megjegyzések. 1. Nem véletlen, hogy a megoldás a különböző színű pontokat összekötő élek, nem pedig a magányos pontok számának lépésenkénti csökkenésére épült. Az 1. ábra gráfjában az egyetlen magányos pont kékre színezésének eredményeként két új magányos pont keletkezik: és .
2. Bár a típusú élek száma minden lépésben csökken, az eljárás végén nem válik feltétlenül nullává (azaz a végső gráf nem mindig ,,egyszínű''). A 2. ábrán egyetlen lépés elégséges a magányos pont megszüntetéséhez, ha színét változtatjuk meg, és a kapott színezésben ugyanannyi pont piros, mint ahány kék! |
|