Projektne naloge

Preusmerjanje

Dan je usmerjen (relacijski) graf G = (V,R), V je množica točk in R relacija na njej. Graf G nima zank.

Sestavi program, ki bo zamenjal smer čim manjšemu številu povezav, tako da bo 'popravljeni' graf acikličen - brez ciklov.

n = card(V) <= 100

Točke acikličnega grafa lahko uredimo tako, da ima ustrezna matrika sosednosti enice samo pod ali pa samo nad diagonalo.