Popis algoritmu

Víme počet uzlů a skóre grafu, tj. jakého stupně je každý uzel (kolik má sousedů). Máme najít všechny grafy s tímto skóre, které nejsou izomorfní.

Musíme tedy vygenerovat všechny grafy, které mají toto skóre a pak je mezi sebou porovnat. Já to dělám tak, že vytvářím kombinace ze všech možných hran, které může tento graf obsahovat. Je jich tedy jako v úplném grafu, n * (n - 1) / 2.

V případě ukázkového zadání:

6 3 3 2 2 2 2

budu vybírat z těchto hran (celkem 15):

0-1 0-2 0-3 0-4 0-5 1-2 1-3 1-4 1-5 2-3 2-4 2-5 3-4 3-5 4-5

Víme i, kolik hran tento graf obsahuje - součet stupňů / 2, v tomto případě 7. Celkový počet kombinací je tedy kombinační číslo (15 / 7). Ale ne všechny kombinace budou mít zadané skóre, při generování lze tedy velmi snadno prořezávat, jakmile u nějakého uzlu přesáhneme zadané skóre nebo víme, že ho v dané kombinaci už nebudeme moci splnit. V ukázkovém příkladu jich zbyde 54.

Dále si vytvoříme seznam, do kterého budeme ukládat navzájem izomorfní grafy. Pokud je seznam prázdný, první validní kombinaci do něj ihned uložíme. Každou další pak musíme se všemi položkami tohoto seznamu porovnávat. Pokud bude nová kombinace s nějakou z tohoto seznamu izomorfní, tak ji zahazujeme, pokud ne, přidáváme ji do seznamu.

Kontrola izomorfnosti je z celého úkolu to nejtěžší. Je potřeba vygenerovat si všechna možná mapování uzlů, doporučuji pole o velikosti počtu uzlů, kde klíč bude index uzlu v prvním grafu a hodnota index uzlu v druhém grafu.

Počet těchto mapování závisí na skupinách uzlů se stejným stupněm, logicky v izomorfismu lze na sebe mapovat jen uzly se stejným stupněm. V ukázkovém příkladu bude počet těchto mapování (2!) * (4!) = 48.

Jakmile máte tato mapování, můžete porovnávat grafy. U každého mapování vyzkouším všechny dvojice uzlů - pokud spolu sousedí v původním grafu, musí spolu sousedit i jejich obrazy. Pokud nesousedí, nesmí ani obrazy. Těchhle porovnávání bude hodně, měly by být v konstantním čase.

Na konci vypíšete počet položek v seznamu těch navzájem neizomorfních grafů.