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