Wykres asymetryczny
W teorii grafów , gałęzi matematyki, graf nieskierowany nazywany jest grafem asymetrycznym, jeśli nie ma nietrywialnych symetrii .
Formalnie automorfizmem grafu jest permutacja p jego wierzchołków z tą właściwością, że dowolne dwa wierzchołki u i v są przyległe wtedy i tylko wtedy, gdy p ( u ) i p ( v ) są przyległe. Odwzorowanie tożsamościowe grafu na siebie samego jest zawsze automorfizmem i jest nazywane trywialnym automorfizmem grafu. Graf asymetryczny to graf, dla którego nie ma innych automorfizmów.
Przykłady
Najmniejsze asymetryczne grafy nietrywialne mają 6 wierzchołków. Najmniejsze asymetryczne grafy regularne mają dziesięć wierzchołków; istnieją grafy asymetryczne z dziesięcioma wierzchołkami, które są 4-regularne i 5-regularne. Jednym z pięciu najmniejszych asymetrycznych grafów sześciennych jest graf Fruchta z dwunastoma wierzchołkami odkryty w 1939 roku. Zgodnie ze wzmocnioną wersją twierdzenia Fruchta istnieje nieskończenie wiele asymetrycznych grafów sześciennych.
Nieruchomości
Klasa grafów asymetrycznych jest zamknięta na dopełnienia : graf G jest asymetryczny wtedy i tylko wtedy, gdy jego dopełnienie jest. Dowolny o n wierzchołkach można uczynić symetrycznym, dodając i usuwając w sumie co najwyżej n /2 + o( n ) krawędzi.
Losowe wykresy
Odsetek grafów na n wierzchołkach z nietrywialnym automorfizmem dąży do zera wraz ze wzrostem n , co nieformalnie wyraża się jako „ prawie wszystkie skończone grafy są asymetryczne”. W przeciwieństwie do tego, ponownie nieformalnie, „prawie wszystkie nieskończone wykresy są symetryczne”. Mówiąc dokładniej, policzalne nieskończone grafy losowe w modelu Erdősa – Rényiego są z prawdopodobieństwem 1 izomorficzne z wysoce symetrycznym grafem Rado .
Drzewa
Najmniejsze drzewo asymetryczne ma siedem wierzchołków: składa się z trzech ścieżek o długości 1, 2 i 3, połączonych wspólnym punktem końcowym. W przeciwieństwie do sytuacji dla grafów, prawie wszystkie drzewa są symetryczne. W szczególności, jeśli drzewo zostanie wybrane równomiernie losowo spośród wszystkich drzew na n oznakowanych węzłach, to z prawdopodobieństwem dążącym do 1 wraz ze wzrostem n drzewo będzie zawierało jakieś dwa liście sąsiadujące z tym samym węzłem i będzie miało symetrie wymieniające te dwa liście.