Wykres asymetryczny - Asymmetric graph
W teorii grafów , gałęzi matematyki, graf nieskierowany nazywa się grafem asymetrycznym, jeśli nie ma nietrywialnych symetrii.
Formalnie automorfizm grafu jest permutacją p jego wierzchołków z własnością, że dowolne dwa wierzchołki u i v sąsiadują ze sobą wtedy i tylko wtedy, gdy p ( u ) i p ( v ) sąsiadują ze sobą. Mapowanie tożsamości z wykresu na siebie zawsze automorfizmem i nazywany jest trywialne automorfizm wykresu. Graf asymetryczny to graf, dla którego nie ma innych automorfizmów.
Przykłady
Najmniejsze asymetryczne nietrywialne grafy mają 6 wierzchołków. Najmniejsze asymetryczne grafy regularne mają dziesięć wierzchołków; istnieją grafy asymetryczne o dziesięciu wierzchołkach, które są 4-regularne i 5-regularne. Jednym z pięciu najmniejszych asymetrycznych grafów sześciennych jest dwunastowierzchołkowy graf Fruchta odkryty w 1939 roku. Według wzmocnionej wersji twierdzenia Fruchta istnieje nieskończenie wiele asymetrycznych grafów sześciennych.
Nieruchomości
Klasa grafów asymetrycznych jest zamknięta pod dopełnieniami : graf G jest asymetryczny wtedy i tylko wtedy, gdy jest jego dopełnieniem. Dowolny asymetryczny graf n -wierzchołkowy można uczynić symetrycznym, dodając i usuwając w sumie co najwyżej n /2 + o( n ) krawędzi.
Wykresy losowe
Proporcja grafów na n wierzchołkach z nietrywialnym automorfizmem dąży do zera wraz ze wzrostem n , co jest nieformalnie wyrażone jako „ prawie wszystkie skończone grafy są asymetryczne”. W przeciwieństwie do tego, ponownie nieformalnie, „prawie wszystkie nieskończone grafy są symetryczne”. Dokładniej, przeliczalne 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 we wspólnym punkcie końcowym. W przeciwieństwie do grafów prawie wszystkie drzewa są symetryczne. W szczególności, jeśli drzewo jest wybierane jednolicie losowo spośród wszystkich drzew na n oznaczonych węzłach, to z prawdopodobieństwem dążącym do 1 przy wzroście 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 zamieniające te dwa liście.