Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem S. 6. (February 2005)

S. 6. Subscribers can reach the text of the problem after signing in. The text will be public from February 10, 2005.]

(10 pont)

Deadline expired on March 15, 2005.


Sorry, the solution is available only in Hungarian. Google translation

Az S. 6. feladat megoldása, értékelése

Mint arra mindenki rájött, a feladatot gráffal volt célszerű reprezentálni, a csúcsok az emberek és két csúcs szomszédos, ha a megfelelő emberek ellenségesek.

Ha a gráfot valahogy szisztematikusan be tudjuk járni, akkor megpróbálhatjuk a csúcsokat mohó módon bal és jobb oldalra osztani (ezentúl: 0-ra és 1-re kiszínezni), és ha olyan élhez jutunk, melynek két vége már ki van színezve, de egyforma színűre, akkor kell keresnünk egy páratlan kört. Persze az, hogy ekkor ilyen létezik, egy nem-triviális tétel. Azonban látni fogjuk, hogy az algoritmus, amit keresünk, be is fogja ezt a tételt bizonyítani.

Tehát három problémával kell meggyürkőznünk:

  • Hogyan tároljuk a gráfot?
  • Hogyan járjuk be szisztematikusan?
  • Hogyan írjuk ki a páratlan kört?

Kezdjük a gráf tárolásával. Erre több hatékony módszer is ismeretes. Itt most nagyon nagy gráfokat akarunk tárolni, viszont tudjuk a feladat szövegéből, hogy semelyik csúcsnak nincs több, mint 200 szomszédja. Ilyenkor a leghatékonyabb tárolási mód az, ha egy n (az emberek száma) sorból és 201 oszlopból álló A mátrixot tárolunk. Az i-edik sorban felsoroljuk az i számú csúcs szomszédait, ha már nincs több szomszéd, akkor 0-kkal folytatjuk (ezért célszerű a 201 oszlop, így minden esetben egy kiolvasott 0 jelzi, hogy már nincs több szomszéd).

Egy gráf bejárására is több módszer ismert, ehhez a feladathoz a "szélességi keresés" nevű eljárás a leghasznosabb. Az eljárás során minden csúcsnak 3 állapota lehet: még nem láttuk; már megláttuk, de még nem intéztük el; illetve elintéztük. A meglátott, de még el nem intézett csúcsokat egy "sor"-ban tároljuk, ez egy olyan adatszerkezet, melybe be lehet tenni és ki lehet venni elemeket, és kivételkor mindig azt az elemet kapjuk meg, akit a legrégebben raktunk be.

Ezekután a szélességi keresés alapja a következő: jelöljük meg az 1-es számú csúcsot meglátottnak és rakjuk be a sorba. Amíg a sor nem üres, vegyünk ki belőle egy csúcsot és intézzük el: vegyük sorba az összes szomszédját, és ezek közül akit még nem láttunk, azt jelöljük meglátottnak és rakjuk be a sor végére.

Az első probléma ezzel az eljárással, hogy csak akkor fogja tényleg bejárni a gráfot, ha az összefüggő, tehát az 1-es számú csúcsból minden más csúcsba el lehet jutni a gráfban. (A gráf az i csúcsot tartalmazó összefüggőségi komponensének nevezzük azon csúcsok halmazát, amelyek az i csúcsból elérhetőek.) Ezen a problémán egy kézenfekvő, ámde mégis ravasz trükkel segítünk: Sorra vesszük a csúcsokat 1-től n-ig, és ha az éppen soron lévő csúcsot még nem láttuk, akkor elindítjuk belőle a fenti eljárást.

Ezenkívül még meg kell adnunk a színezést; azt, hogy ezt hogyan ellenőrizzük le, és hogy hibás színezés esetén hogyan találunk páratlan kört. Ehhez szükségünk lesz még egy Sz szín-tömbre és egy P szülő-tömbre. Egy csúcs szülőjének azt a csúcsot nevezzük, akiből őt megláttuk. Ha az i csúcsot még nem láttuk, ezt P[i]=0 -val jelezzük. Ha valamelyik összefüggő komponensben a keresést a j csúccsal kezdtük, akkor P[j] értékét j-re állítjuk. Minden más i csúcsra P[i] az i szülőjét fogja tartalmazni.

A színezést úgy végezzük, hogy minden komponens kezdő-csúcsát 0-ra színezzük, és minden más meglátott csúcsot pedig a szülőével ellentétes színűre. Az ellenőrzést egy-egy csúcs elintézésénél végezzük el, mégpedig úgy, hogy ha valamelyik szomszédja olyan, hogy már régebben megláttuk, akkor megnézzük, hogy ez a két csúcs különböző színű-e. Ha igen megyünk tovább, különben elkezdjük megkeresni a páratlan kört.

Mielőtt ezt részleteznénk, érdemes meggondolni, hogy mi történik az eljárás során. Képzeletben minden meglátott csúcshoz rendeljünk még egy számot, melyet a csúcs szintjének nevezünk. A komponensek kezdő-csúcsának szintje legyen 0, minden más csúcs szintje legyen eggyel nagyobb, mint a szülőjének szintje. Először is vegyük észre, hogy egy komponensen belül a sorból kivett csúcsok szint-száma monoton nő, és amikor elintéztünk egy k szintű csúcsot, akkor a sorban kizárólag k és k+1 szintű csúcsok lehetnek. Ezután lássuk be, hogy ha v csúcs szintje legalább kettővel nagyobb u szintjénél, akkor ez a két csúcs biztosan nem szomszédos. Ez rögtön következik az előző észrevételből, hiszen u elintézésekor minden szomszédját megnéztük, és aki még nem volt elintézve és a sorban sem, azt beraktuk a sorba. Mivel a színezéskor a páros szintű csúcsokat 0-ra, a páratlan szintűeket 1-re színeztük, ezért csak úgy találhattunk két azonos színű szomszédos csúcsot, ha azok ugyanazon szinten vannak (és persze ugyanabban a komponensben).

Most belátjuk, hogy ilyenkor a gráfban tényleg van páratlan kör, és ezt meg is találjuk. Tegyük fel, hogy u és v volt az a két szomszédos csúcs, akiket azonosra színeztünk. Ekkor az előzőek alapján azonos (pl. a k.) szinten vannak. Tehát vagy azonos a szülőjük, vagy a nagyszülőjük, vagy a dédnagyszülőjük... Mivel a k. felmenőjük a komponens kezdő csúcsa, így tényleg találunk legközelebbi közös őst, legyen ez w. Nyilván az u, P[u], P[P[u]], ..., w és a v, P[v], P[P[v]], ..., w utak ugyanolyan hosszúak, így az uv éllel együtt egy páratlan kört alkotnak, ezt kell (jó sorrendben) kiíratni.

Egy lehetséges C kód a feladatra itt található.

Értékelés

A feladatra öten küldtek be megoldást. Vincze János programja a pici.10 teszten rossz eredményt adott, 4 pici teszten 10 másodperc alatt sem tudott eredményt generálni, és a kicsi tesztek egyikén sem tudott 1 perc alatt lefutni. Szoldatics András programja abszolút dokumentáció nélkül érkezett, a pici.9 teszten rossz eredményt adott, és sok kis hiba kijavítása után is még néhány kicsi feladatra 'Segmentation fault' hibaüzenettel elszállt. Ők ketten 0 pontot kaptak.

Engedy Balázs, Nikházy László és Stippinger Marcell jól megoldották a feladatot. A leggyorsabb és legjobban dokumentált Nikházy László programja volt, így Ő 10 pontot kapott, Stippinger Marcell 9 pontot, míg Engedy Balázs, akinek a programja pl. az orias.3 teszten 56 percig futott, 8 pontot.

(A programokat AMD 1800+ processzoron futtattuk).


Statistics:

5 students sent a solution.
10 points:Nikházy László .
9 points:Stippinger Marcell.
8 points:1 student.
0 point:2 students.

Problems in Information Technology of KöMaL, February 2005