Toleranciarelációhoz legközelebbi ekvivalenciareláció

Adott egy T parciális toleranciareláció (reflexív és szimmetrikus). A feladat megkeresni az ehhez legközelebbi ekvivalenciarelációt. Miután ez NP-nehéz feladat, így csak közelítő eredmény várható.

A megírandó program maximum két parancssori argumentumot kaphat. Az első (amit mindenképpen megkap) egy fájl neve. Ebben a fájlban soronként egy-egy gráfot leíró fájl neve található. Minden gráfleíró fájl első sora a gráf csúcsainak számát (n) adja meg. Ezt n sor követi, melyek mindegyikében n karakter szerepel. A 0 karakter jelzi, hogy ez a pozíció nem érdekes, mivel a reláció itt nem értelmezett. Az 1 karakter jelzi, hogy a reláció ebben az esetben értelmezett és teljesül. Míg a 2 karakter azt jelzi, hogy a reláció értelmezett, de nem teljesül. Például álljon itt a bal oldalon egy lehetséges ilyen fájl tartalma:

6 122021 111122 211022 111122 211012 111122 000120 111122 221211 222211 122011 222211

Ebben a fordulóban Erdős–Rényi véletlen gráfokat használunk. A keresett ekvivalenciareláció is leírható lenne hasonló módon (fent jobb oldalt), viszont az minden elempárra értelmezett, így 0 karakter nem szerepelhet a leírásában. Érdemes az ekvivalenciarelációt egy függvényként elképzelni (f : V → N), mely minden csúcshoz egy egész számot rendel. Két csúcs ekvivalens, ha a hozzájuk rendelt két szám egyenlő, és nem ekvivalens, ha ez a két szám különböző.

A tolerancia- és az ekvivalenciareláció távolságát úgy értelmezzük, hogy azon i és j csúcspárok száma, ahol vagy a toleranciareláció teljesül, de az ekvivalenciareláció nem, vagy a toleranciareláció nem teljesül, míg az ekvivalenciareláció igen. Fent az eltéréseket piros színnel jeleztük, így a távolság 4. Mivel mind a tolerancia-, mind az ekvivalenciareláció szimmetrikus, így elegendő az előbb szereplő mátrixok felső (háromszögmátrix) felével dolgozni, mert az alsó háromszögmátrixban is ugyanezek a csúcspárok szerepelnek.

A programnak az egyes gráfok esetén számolt távolságok összegét kell a kimenetre írnia, azaz minden futás esetén csak egyetlen számot!

Annak érdekében, hogy ez a megoldás utólag ellenőrizhető legyen, ha egy második parancssori argumentum is megadásra kerül (a tartalma lényegtelen), akkor a távolságok összege helyett a kimenetre minden egyes gráfleíró fájl esetén meg kell adni a gráfhoz tartozó távolságot, majd az ekvivalenciához tartozó valamely f függvényt is, azaz előbbi példánk esetén az output lehet

4 1 1 1 1 2 2

vagy akár

4 3 3 3 3 1 1

is. Az a lényeg, hogy egy ekvivalenciaosztály tagjaihoz ugyanazon szám legyen megadva. Az egyes gráfokhoz tartozó kimeneteket külön sorba kell kiírni, az adatokat egy soron belül egy-egy szóközzel elválasztva.

Megjegyzés

Ebben a feladatban a feltöltött programokat csak kis gráfok esetén teszteljük (ahol n ≤ 10), hogy egy 3 másodpercig futó program is biztonsággal meg tudja találni az optimális megoldást. A levelező verseny feladatában azonban a tesztelést nagy gráfokkal fogjuk végezni, és a legoptimálisabb megoldást keressük. Az első parancssori argumentumban megadott állományban legfeljebb 20 állománynév fog szerepelni, amelyek hossza nem haladja meg az 50 karaktert.