navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m33pal:uloha6-2013 [2013/11/10 01:01] ondrejmirtes referenční řešení |
courses:a4m33pal:uloha6-2013 [2025/01/03 18:28] (aktuální) |
||
|---|---|---|---|
| Řádek 31: | Řádek 31: | ||
| 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. | 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. | + | Dále si vytvoříme seznam, do kterého budeme ukládat navzájem neizomorfní 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. | 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. | ||
| Řádek 40: | Řádek 40: | ||
| Na konci vypíšete počet položek v seznamu těch navzájem neizomorfních grafů. | Na konci vypíšete počet položek v seznamu těch navzájem neizomorfních grafů. | ||
| + | |||
| + | ------------------------------------------------------------------------------------------------------------------------- | ||
| + | By Rosion: chci se zeptat, jak generujete kombinace hran? Mate nejaky typ, nejake doporuceni? Diky | ||
