S. 6.

(10 points)

Deadline expired.

Sorry, the solution is published in Hungarian only.

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.