Wykres symetryczny - Symmetric graph
W matematycznej dziedzinie teorii wykres , A wykres G jest symetryczna (lub łuku przechodni ) w przypadku, biorąc pod uwagę dowolne dwie pary sąsiednich wierzchołków kształcie U 1 - V 1 i u 2 - v 2 o G , jest automorfizmem
takie, że
Innymi słowy, graf jest symetryczny, jeśli jego grupa automorfizmu działa przechodnie na uporządkowane pary sąsiednich wierzchołków (to znaczy na krawędzie uważane za mające kierunek). Taki graf jest czasami nazywany również 1-arc-transitive lub flag-transitive .
Z definicji (pomijając u 1 i u 2 ) graf symetryczny bez izolowanych wierzchołków musi być również wierzchołkiem przechodnim . Ponieważ powyższa definicja odwzorowuje jedną krawędź na drugą, symetryczny wykres również musi być krawędziowo przechodni . Jednak graf przechodni krawędziowy nie musi być symetryczny, ponieważ a — b może być odwzorowane na c — d , ale nie na d — c . Wykresy gwiaździste są prostym przykładem tego, że są przechodnie krawędziowe, nie będąc przechodnimi wierzchołkami ani symetrycznymi. Jako dalszy przykład, grafy półsymetryczne są przechodnie krawędziowe i regularne , ale nie są przechodnie wierzchołkowe.
Każdy połączony graf symetryczny musi zatem być zarówno wierzchołkowo przechodni, jak i krawędziowo przechodni, a odwrotność jest prawdziwa dla grafów nieparzystego stopnia. Jednakże, w równym stopniu, istnieją połączone grafy, które są wierzchołkowo przechodnie i krawędziowo przechodnie, ale nie są symetryczne. Takie wykresy nazywane są półprzechodnimi . Najmniejszym połączonym grafem półprzechodnim jest graf Holta , z wierzchołkami stopnia 4 i 27. Mylące, niektórzy autorzy używają terminu „wykres symetryczny” w znaczeniu wykresu, który jest przechodni wierzchołkowy i przechodni krawędziowej, a nie wykresu przechodniego łuku. Taka definicja obejmowałaby grafy półprzechodnie, które są wyłączone w ramach powyższej definicji.
Dystansu przechodni wykresu jest taki, w którym zamiast uwzględnieniem parami sąsiednimi wierzchołkami (tj wierzchołkami odległości 1 od siebie), przy czym definicja obejmuje dwie pary wierzchołków, każdy w tej samej odległości od siebie. Takie wykresy są z definicji automatycznie symetryczne.
T -arc jest definiowany jako sekwencja o t + 1 wierzchołków, tak że każde dwa kolejne wierzchołki sekwencji sąsiadują ze sobą, i do powtórzenia wierzchołki wynosi ponad 2 etapy siebie. T -transitive wykres przedstawia wykres tak, aby grupa automorfizmem działa przechodni w t -arcs, ale nie w ( t + 1) -arcs. Ponieważ 1-arcs są po prostu krawędziami, każdy symetryczny graf stopnia 3 lub wyższego musi być t -przechodni dla pewnego t , a wartość t może być użyta do dalszej klasyfikacji grafów symetrycznych. Na przykład kostka jest 2-przechodnia.
Przykłady
Połączenie warunku symetrii z ograniczeniem, że wykresy są sześcienne (tj. wszystkie wierzchołki mają stopień 3), daje dość mocny warunek, a takie wykresy są na tyle rzadkie, że można je wymienić. Spis ludności Foster i jego rozszerzenia zawierają takie listy. Spis Foster rozpoczął się w latach 30. XX wieku przez Ronalda M. Fostera, gdy był zatrudniony w Bell Labs , a w 1988 r. (kiedy Foster miał 92 lata) ówczesny spis Fostera (wymieniający wszystkie sześcienne grafy symetryczne do 512 wierzchołków) został opublikowany w książce Formularz. Pierwsze trzynaście pozycji na liście to sześcienne grafy symetryczne z maksymalnie 30 wierzchołkami (dziesięć z nich jest również przechodnich na odległość ; wyjątki są wskazane):
Wierzchołki | Średnica | Obwód | Wykres | Uwagi |
---|---|---|---|---|
4 | 1 | 3 | Zakończeniu wykres K 4 | odległość przechodnia, 2-łuku przechodnia |
6 | 2 | 4 | Zakończeniu dwustronnego wykres K 3,3 | odległość przechodnia, 3-łukowa przechodnia |
8 | 3 | 4 | Wierzchołki i krawędzie sześcianu | odległość przechodnia, 2-łuku przechodnia |
10 | 2 | 5 | Wykres Petersen | odległość przechodnia, 3-łukowa przechodnia |
14 | 3 | 6 | Wykres Heawood | odległość przechodnia, 4-łukowa przechodnia |
16 | 4 | 6 | Wykres Möbiusa-Kantor | 2-łukowe-przechodnie |
18 | 4 | 6 | Wykres Pappus | odległość przechodnia, 3-łukowa przechodnia |
20 | 5 | 5 | Wierzchołki i krawędzie dwunastościanu | odległość przechodnia, 2-łuku przechodnia |
20 | 5 | 6 | Wykres Desargues | odległość przechodnia, 3-łukowa przechodnia |
24 | 4 | 6 | Wykres Nauru (The uogólnione Petersen wykres G (12,5)) | 2-łukowe-przechodnie |
26 | 5 | 6 | Wykres F26A | 1-łukowo-przechodnie |
28 | 4 | 7 | Wykres Coxeter | odległość przechodnia, 3-łukowa przechodnia |
30 | 4 | 8 | Wykres Tutte-Coxeter | odległość przechodnia, 5-łukowa przechodnia |
Inne znane sześciennych wykresy symetryczne to wykres Dyck The wykres Foster i wykres Biggs-Smith . Dziesięć wykresów przechodnich odległości wymienionych powyżej, wraz z wykresem Fostera i wykresem Biggsa-Smitha , to jedyne sześcienne wykresy przechodnie odległości.
Niesześcienne wykresy symetryczne obejmują wykresy cykli (stopień 2), wykresy kompletne (stopień 4 lub więcej, gdy istnieje 5 lub więcej wierzchołków), wykresy hipersześcianowe (stopień 4 lub więcej, gdy istnieje 16 lub więcej wierzchołków) oraz wykresy utworzone przez wierzchołki oraz krawędzie oktaedrycznej , dwudziestościanu , sześcio-ośmiościan i icosidodecahedron . Wykres Rado stanowi przykład symetryczny wykres z nieskończenie wiele wierzchołków i nieskończony stopniu.
Nieruchomości
Wierzchołek-łączność symetrycznego wykresu jest zawsze równy stopień d . W przeciwieństwie do tego, dla grafów wierzchołkowo-przechodnich w ogólności, łączliwość wierzchołków jest ograniczona poniżej przez 2( d + 1)/3.
T -transitive wykres stopnia 3 lub więcej posiada obwód co najmniej 2 ( T - 1). Jednak nie ma skończonych grafów t -przechodnich stopnia 3 lub więcej dla t ≥ 8. W przypadku stopnia równego dokładnie 3 (grafy sześcienno-symetryczne), nie ma żadnego dla t ≥ 6.
Zobacz też
Bibliografia
Zewnętrzne linki
- Wykresy sześcienne symetryczne (The Foster Census) . Pliki danych dla wszystkich sześciennych wykresów symetrycznych do 768 wierzchołków i niektórych sześciennych wykresów do 1000 wierzchołków. Gordon Royle, aktualizacja luty 2001, pobrana 18.04.2009.
- Trójwartościowe (sześcienne) wykresy symetryczne do 10000 wierzchołków . Marston Conder , 2011.