Přesný počet automorfismů

Úloha číslo: 3575

Pro každé přirozené \(n\) sestrojte graf \(G_n\), který má přesně \(n\) automorfismů, neboli izomorfismů \(G_n\to G_n\).

  • Řešení

    \(K_1\) má jeden automorfismus, \(K_2\) dva.

    Cyklus \(C_k\) má \(2k\) automorfismů \(f\)– pro \(f(v_1)\) lze zvolit \(k\) způsoby a pro \(f(v_2)\) pak jeden ze dvou sousedů \(f(v_1)\), zbytek je pak určen jednoznačně. Tímto jsme pokryli případy pro všechna sudá \(n=2k\).

    Konstrukce pro lichá \(n\) může vyjít z podobného principu, jen je třeba hrany \(C_n\) nahradit složitějšími grafy, aby volba \(f(v_2)\) byla jednoznačně určena volbou \(f(v_1)\). Toho lze docílit např. pokud hranu nahradíme cestou délky tři, kde k prvnímu vnitřnímu vrcholu cesty přidáme 1 list a ke druhému dva, viz obrázek.

    Má-li původní cyklus vrcholy \(v_1,…,v_k\) v pořadí po směru hodinových ručiček, potom v upraveném grafu posílá každý automorfismus vrchol \(v_1\) na nějaký vrchol stupně dva. Obraz \(v_2\) je už jednoznačně dán, je to první vrchol stupně dva, který následuje po \(f(v_1)\) ve směru hodinových ručiček.

    Podobných konstrukcí existuje více.

Obtížnost: Obtížná úloha
Úloha vyžadující neobvyklý trik nebo nápad
En translation
	Zaslat komentář k úloze