Wykres sześcienny złożony - Folded cube graph
| Składany wykres sześcienny | |
|---|---|
 Składany wykres sześcienny wymiaru 5 (tj. wykres Clebscha ).
| |
| Wierzchołki | 2 n -1 |
| Krawędzie | 2 n -2 n |
| Średnica | piętro( n /2) |
| Liczba chromatyczna | 2 (dla parzystego n ) lub 4 (gdy nieparzyste). |
| Nieruchomości |
Graf regularny Hamiltonian Odległość-przechodnia . |
| Tabela wykresów i parametrów | |
W teorii wykres , A złożony wykres kostka jest nieukierunkowane wykres utworzony z wykresu hipersześcianu dodając do niej odpowiednim dopasowaniu łączący przeciwległe pary wierzchołków HyperCube.
Budowa
Złożony wykres sześcienny o wymiarze k (zawierający 2 k -1 wierzchołki) można utworzyć przez dodanie krawędzi między przeciwległymi parami wierzchołków w grafie hipersześcianowym o wymiarze k -1. (W hipersześcianie z 2 n wierzchołkami para wierzchołków jest przeciwnie, jeśli najkrótsza ścieżka między nimi ma długość n .) Można go równoważnie utworzyć z grafu hipersześcianowego (również) o wymiarze k , który ma dwa razy więcej wierzchołków, poprzez identyfikację (lub skrócenie) każdej przeciwnej pary wierzchołków.
Nieruchomości
Składany graf sześcienny o wymiarze k to k - regularny z 2 k − 1 wierzchołkami i 2 k − 2 k krawędziami.
Liczba chromatyczna grafu sześciennego złożonego wymiaru k wynosi dwa, gdy k jest parzyste (czyli w tym przypadku graf jest dwudzielny ) i cztery, gdy k jest nieparzyste. Dziwne obwód od złożonego sześcianu dziwnym wymiarze jest k , tak dla nieparzystych k większy niż trzy zagięte wykresy kostki zapewniają klasę trójkąta wolne wykresy z numerem cztery i chromatycznej dowolnie dużej nieparzystej obwodzie. Jako graf z regularną odległością o nieparzystym obwodzie k i średnicy ( k − 1)/2, złożone sześciany o nieparzystym wymiarze są przykładami uogólnionych grafów nieparzystych .
Gdy k jest nieparzysta, dwudzielny podwójna pokrywa się na wymiarze k złożonej kostki jest na wymiarze k sześcian z którego został utworzony. Jednak gdy k jest parzyste, sześcian wymiaru k jest podwójną okładką, ale nie dwudzielną podwójną okładką. W tym przypadku złożona kostka sama jest już dwudzielna . Grafy złożonego sześcianu dziedziczą ze swoich podgrafów hipersześcianowych właściwość posiadania cyklu Hamiltona , a z hipersześcianów, które podwójnie je pokrywają, właściwość bycia grafem przechodnim odległościowym .
Gdy k jest nieparzyste, złożony sześcian o wymiarze k zawiera jako podgraf pełne drzewo binarne z 2 k − 1 węzłami. Jednak gdy k jest parzyste, nie jest to możliwe, ponieważ w tym przypadku złożony sześcian jest grafem dwudzielnym z równą liczbą wierzchołków po każdej stronie dwudzielności, bardzo różniącej się od stosunku prawie dwa do jednego dla dwudzielności kompletne drzewo binarne.
Przykłady
- Złożony graf sześcienny trzeciego wymiaru jest grafem zupełnym K 4 .
- Złożony graf sześcienny o wymiarze czwartym jest kompletnym grafem dwudzielnym K 4,4 .
- Złożony wykres sześcienny o wymiarze piątym to wykres Clebscha .
- Złożony graf sześcienny o wymiarze szóstym to graf Kummera , tj. graf Levi o konfiguracji punkt-płaszczyzna Kummera .
Aplikacje
W obliczeniach równoległych grafy złożonego sześcianu były badane jako potencjalna topologia sieci , jako alternatywa dla hipersześcianu. W porównaniu do hipersześcianu , A składana kostka z taką samą liczbą węzłów ma prawie taki sam stopień wierzchołków, ale tylko połowę średnicy . Wydajne algorytmy rozproszone (względem tych dla hipersześcianu ) są znane z rozgłaszania informacji w złożonym sześcianie.
Zobacz też
Uwagi
Bibliografia
- van Bon, John (2007), "Finite prymitywne grafy przechodnie na odległość", European Journal of Combinatorics , 28 (2): 517-532, doi : 10.1016/j.ejc.2005.04.014.
- Choudam SA; Nandini, R. Usha (2004), "Kompletne drzewa binarne w złożonych i ulepszonych kostkach", Sieci , 43 (4): 266-272, doi : 10.1002/net.20002.
- Van Dama, Edwina; Haemers, Willem H. (2010), An Odd Characterisation of the Generalized Odd Graphs , CentER Discussion Paper Series No. 2010-47, SSRN 1596575.
- El-Amawy, A.; Latifi, S. (1991), „Właściwości i wydajność złożonych hipersześcianów”, IEEE Trans. Dystrybucja równoległa. Syst. , 2 (1): 31–42, doi : 10.1109/71.80187.
- Godsil, Chris (2004), Ciekawe wykresy i ich kolorystyka , CiteSeerX 10.1.1.91.6390.
- Varvarigos, E. (1995), „Efektywne algorytmy routingu dla sieci złożonych kostek”, Proc. 14. Międzyn. Konf. Feniksa w sprawie komputerów i komunikacji , IEEE, s. 143-151, doi : 10.1109/PCCC.1995.472498.