Grafy na čtyřech vrcholech
Úloha číslo: 3570
Nalezněte všechny neizomorfní grafy na čtyřech vrcholech.
U každého z nich určete, kolik by měl izomorfních protějšků, pokud by množina vrcholů byla předepsána (např. \(\{u,v,w,x\}\)).
Nápověda
Postupujte systematicky, např. podle počtu hran.
Řešení
Grafy jsou na následujícím obrázku, grafy nad sebou jsou vzájemně komplementární, jen poslední \(P_4\) je doplňkem sebe sama.
Komplementární grafy mají stejně velké třídy izomorfismů, jejich velikost je uvedena.
Konkrétně:- Prázdný graf je jen jeden (každá permutace vrcholů dává stejný graf).
- Grafů s jednou hranou je šest – dvojici (hranu) lze ze čtyřprvkové množiny vybrat \(\binom{4}{2}=6\) způsoby.
- Grafů izomorfních \(P_3\cup K_1\) je dvanáct – pro izolovaný vrchol jsou čtyři možnosti, pro střed \(P_3\) pak tři ze zbylých vrcholů.
- Párování jsou jen tři, jsou určené třemi volbami, jak zvolit souseda k \(u\).
- \(K_{1{,}3}\) jsou čtyři – tolik voleb je pro centrální vrchol.
- Cest je \(\frac{4!}{2}\) – každá permutace dá uspořádání vrcholů do posloupnosti, dvě posloupnosti dají stejný graf pokud jsou vzájemně symetrické.
Odpověď
Na čtyřech vrcholech lze nalézt celkem 64 různých grafů, ale z nich je jen 11 neizomorfních.