Matematické Fórum

Dobrý den, na zkoušce se často vyskytuje následující příklad:



Příklad řeším následovně: Vytvořím si tolik stejných grafů, kolik má zadaný graf stran vždy bez jedné strany. Pak je rozdělím podle stupně vrcholů a takto rozdělené grafy dále porovnávám, jestli obsahuji stejný počet n-úhelníků. Pokud ano, tak najdu specifický bod (primárně se stupněm vrcholu 1), který musí mít v případě isomorfismu oba dva grafy stejný a z tohoto bodu se pohybuji po stranách a grafy porovnávám. Až po tomto kroku dokážu určit, zda jsou isomorfní.

Zrovna u tohoto příkladu si všímám, že je osově symetrický, takže logicky symetrické strany (strany které osa neprotne) nemohou být neisomorfní.

Zadaný graf však většinou není takto pěkně symetrický a řešení mi zabere klidně i dobrých 30+ minut.

Moje otázka je, jestli se dá tento příklad vyřešit rychleji a efektivněji než to dělám teď? Děkuji.