Wykres Hamminga

Wykres Hamminga
Nazwany po	Richarda Hamminga
Wierzchołki	q d
Krawędzie	${\ Displaystyle {\ Frac {d (q-1) q ^ {d}} {2}}}$
Średnica	D
Widmo	${\ Displaystyle \ {(d (q-1) -qi) ^ {{\ binom {d} {i}} (q-1) ^ {i}};} ja = ,$$ja =0,\ldkropki ,d\}}$
Nieruchomości	d ( q – 1) - regularna Wierzchołek-przechodnia Odległość-regularna
Notacja	H. ( re , q )
Tabela wykresów i parametrów

H (3,3) narysowany jako wykres odległości jednostkowej

Wykresy Hamminga to specjalna klasa grafów nazwana na cześć Richarda Hamminga i używana w kilku gałęziach matematyki ( teoria grafów ) i informatyce . Niech S będzie zbiorem q elementów , a d dodatnią liczbą całkowitą . Graf Hamminga H ( d , q ) ma zbiór wierzchołków S ^d , zbiór uporządkowanych d - krotki elementów S , czyli ciągi o długości d z S . Dwa wierzchołki sąsiadują ze sobą , jeśli różnią się dokładnie jedną współrzędną; to znaczy, jeśli ich odległość Hamminga wynosi jeden. Graf Hamminga H ( d , q ) jest równoważnie iloczynem kartezjańskim d pełnych grafów K _q .

W niektórych przypadkach grafy Hamminga można traktować bardziej ogólnie jako iloczyny kartezjańskie kompletnych grafów, które mogą mieć różne rozmiary. W przeciwieństwie do grafów Hamminga H ( d , q ) , grafy w tej bardziej ogólnej klasie niekoniecznie są grafami regularnymi odległości , ale nadal są regularne i przechodnie względem wierzchołków .

Przypadki specjalne

• H (2,3) , czyli uogólniony czworokąt G Q (2,1)
• H (1, q ) , czyli pełny wykres K _q
• H (2, q ) , czyli wykres kratowy L _q,q , a także wykres wieży
• H ( d ,1) , który jest grafem singletonowym K ₁
• H ( d ,2) , który jest wykresem hipersześcianu Q _d . Ścieżki Hamiltona na tych grafach tworzą kody Graya .
• Ponieważ iloczyny kartezjańskie grafów zachowują właściwość bycia wykresem jednostkowej odległości , wszystkie grafy Hamminga H ( d , 2) i H ( d , 3) ​​są wykresami jednostkowej odległości.

Aplikacje

Wykresy Hamminga są interesujące w połączeniu z kodami korekcji błędów i schematami asocjacji , by wymienić dwa obszary. Zostały one również uznane za topologię sieci komunikacyjnej w przetwarzaniu rozproszonym .

Złożoność obliczeniowa

czasie liniowym można sprawdzić, czy graf jest grafem Hamminga, a jeśli tak, znaleźć jego oznaczenie krotkami, które realizują go jako graf Hamminga.

Linki zewnętrzne

• Weisstein, Eric W. „Wykres Hamminga” . MathWorld .
• Brouwer, Andries E. „Wykresy Hamminga” .