Isomorfismus s doplňkem
Úloha číslo: 4540
Nalezněte graf, který je izomorfní svému doplňku. Dokážete najít další? Je možné jich sestrojit nekonečně mnoho?
Idea řešení
Rozborem případů lze nalézt \(P_4\) nebo \(C_5\).
Nekonečně takových je možné získat rekurzivní konstrukcí. V grafu \(G\), který je izomorfní svému doplňku nahradíme každý vrchol \(v\) kopií nějakého grafu \(H_v\), který je také izomorfní svému doplňku. (Dokonce pro nahrazení různých vrcholů lze použít různé grafy, nebo některé vrcholy nijak nenahrazovat - stačí nahradit jen jeden.)
Hrany původního grafu pak nahradíme úplnými bipartitními grafy.
Isomorfismus \(G\) a \(\overline G\) zkombinovaný s isomorfismy mezi \(H_v\) a \(\overline{H_v}\) je hledaný isomorfismus výsledného grafu a jeho doplňku.
