Feladat: Gy.2793 Korcsoport: 14-15 Nehézségi fok: nehéz
Megoldó(k):  Csörnyei Marianna ,  Dőtsch András ,  Fazekas Borbála ,  Kóczy László ,  Németh Ákos ,  Pete Gábor 
Füzet: 1993/március, 119. oldal  PDF  |  MathML 
Témakör(ök): Logikai feladatok, Gráfelmélet, Gyakorlat
Hivatkozás(ok):Feladatok: 1992/október: Gy.2793

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 A, az utóbbiakat B 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 a darab A és b darab B típusú él indul ki. Ekkor ‐ a magányos pont definíciója szerint ‐ b>a. Az átszínezés után a pontból b darab A és a darab B típusú él indul ki. Tehát a B típusú élek száma (az egész gráfban!) b-a⩾1-gyel csökkent. Mivel kezdetben véges sok B 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 -P1- kékre színezésének eredményeként két új magányos pont keletkezik: P2 és P3.
 

2. Bár a B 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 P2 színét változtatjuk meg, és a kapott színezésben ugyanannyi pont piros, mint ahány kék!