Az eredeti feladat itt.

Megoldás

Egy tetszőleges gráfban a maximális független csúcshalmaz megtalálása nehéz feladat (lényegében NP-teljes), úgyhogy extra feltételek kihasználása nélkül reménytelen lenne hozzálátni a megoldáshoz. Koncentráljunk tehát arra, hogy mit tudunk a gráfról: legfeljebb öt kivétellel minden csúcs foka legfeljebb kettő (minden ember legfeljebb két másikat ismer). Először vizsgáljuk azt az esetet, amikor nincs kivétel, azaz minden csúcs foka legfeljebb kettő. Egy ilyen gráf könnyen látható módon diszjunkt utakból és körökből áll, ezekre elég külön-külön meghatározni a maximális független csúcshalmazokat. A feladat viszont így már könnyű, hiszen egy k csúcsú útra a válasz k/2 felső egészrésze, míg egy k pontot tartalmazó körre k/2 alsó egészrésze (minden második csúcsot kell kiválasztani). Azaz csak ki kell számolni a komponensek méretét (és típusát), a keresett maximum pedig ezen értékek összege lesz.

Na de mi van akkor, ha vannak 2-nél nagyobb fokú csúcsok is? Szerencsére csak kevés van belőlük (legfeljebb 5), úgyhogy mindössze annyi a teendőnk, hogy előre lerögzítsük, hogy közülük melyeket vesszük be a független csúcshalmazba, és melyeket nem. Erre 2⁵ lehetőségünk van. Persze arra azért figyelni kell, hogy ha ketten szomszédosak, akkor ne vegyük be mindkettőt. Azonban miután ezt rögzítettük (valamint kitöröltük azokat a csúcsokat, amelyeket biztosan nem veszünk be a független halmazba), a maradék gráfban minden csúcs foka legfeljebb kettő, vagyis alkalmazhatjuk a fenti (lineáris futásidejű) algoritmusunkat a maximum keresésére. Összesen tehát 2^l * N-nel arányos a lépésszám, ahol l a több mint 2-fokú csúcsok száma.

Ez egy igencsak technikai feladat, ahol a fent vázolt gondolatmenet egyes részleteinek a lekódolása is ötleteket igényel (azaz nemcsak matematikai, hanem programozói kihívás is a feladat). Erre egy lehetséges módszer a példaprogramomban látható.

Megoldásom (nem a hivatalos megoldás!)

A bejegyzés trackback címe:

Kommentek:

A hozzászólások a vonatkozó jogszabályok  értelmében felhasználói tartalomnak minősülnek, értük a szolgáltatás technikai  üzemeltetője semmilyen felelősséget nem vállal, azokat nem ellenőrzi. Kifogás esetén forduljon a blog szerkesztőjéhez. Részletek a  Felhasználási feltételekben és az adatvédelmi tájékoztatóban.