资 源 简 介
Úloha MHR: minimální hranový řez grafu
Vstupní data:
G(V,E) = jednoduchý souvislý neorientovaný neohodnocený k-regulární graf o n uzlech a m hranách
n = přirozené číslo představující počet uzlu grafu G, n >= 5
k = přirozené číslo řádu jednotek představující stupeň uzlu grafu G, n >= k >= 3; n a k nejsou současně obě liché
Doporučení pro algoritmus generování G:
Použijte generátor grafu s volbou typu grafu „-t REG“, který vygeneruje souvislý neorientovaný neohodnocený graf. Hrany grafu následně ohodnoťte náhodnými celočíselnými váhami z intervalu <1,255>.
Úkol:
Nalezněte minimální hranový řez grafu, tj. nalezněte rozdělení množiny uzlů V do dvou disjunktních neprázdných podmnožin X a Y tak, že součet ohodnocení všech hran {u,v} takových, že u je z X a v je z Y, je minimální.
Výstup algoritmu:
