alt=Projekcja sześcianu z wierzchołkami opisanymi ciągami binarnymi|mały|3-kostka Kostka, k-kostka – w teorii grafów, graf, którego wierzchołki odpowiadają ciągom binarnym długości i którego krawędzie łączą ciągi różniące się dokładnie jednym wyrazem. Oznaczany symbolem .
Graf jest regularny stopnia ma wierzchołków i krawędzi.
W niektórych superkomputerach topologia połączeń między procesorami przyjmuje postać -kostki.
Własności Każda kostka jest grafem dwudzielnym, czyli takim, którego liczba chromatyczna to 2. Poprawne kolorowanie kostki dwoma kolorami można otrzymać, kolorując wierzchołki, których ciągi zawierają parzystą liczbę jedynek, jednym kolorem, a pozostałe wierzchołki drugim kolorem.
Graf jest k-spójny wierzchołkowo. Oznacza to, że aby przestał być spójny, trzeba z niego usunąć co najmniej wierzchołków. Podobnie jest -spójny krawędziowo, czyli po usunięciu dowolnego podzbioru co najwyżej krawędzi pozostanie spójny.
K-kostka jest grafem hamiltonowskim dla . Cyklowi Hamiltona w odpowiada kod Graya dla -bitowych ciągów binarnych.
K-kostka ma dokładnie
drzew rozpinających.
Planarność i liczba przecięć K-kostki są planarne jedynie dla Dla graf jest genusu
Liczba przecięć grafu rozumiana jako najmniejsza możliwa liczba par krawędzi, które muszą się przeciąć, gdy narysujemy ten graf na płaszczyźnie, jest równa 8. O liczbie przecięć wiadomo, że jest nie większa niż 56.
W 1973 roku Paul Erdős i Richard Guy postawili hipotezę, że
Hipoteza ta jest jednak fałszywa, ponieważ znaleziono płaskie rysunki o mniej niż 1760 przecięciach.
W 1991 roku Tom Madej wykazał następujące górne ograniczenie liczby przecięć grafu :
Z kolei w 1993 roku liczbę tę ograniczono z dołu:
Przypisy
Linki zewnętrzne
Kategoria:Klasy grafów