Kostka (teoria grafów)

3-kostka $Q_3$

Kostka, k-kostka – w teorii grafów, graf, którego wierzchołki odpowiadają ciągom binarnym długości $k$ i którego krawędzie łączą ciągi różniące się dokładnie jednym wyrazem. Oznaczany symbolem $Q_k$.

Graf $Q_k$ jest regularny stopnia $k,$ ma $2^k$ wierzchołków i $k\cdot 2^{k-1}$ krawędzi.

W niektórych superkomputerach topologia połączeń między procesorami przyjmuje postać $k$-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 $Q_k$ jest k-spójny wierzchołkowo. Oznacza to, że aby przestał być spójny, trzeba z niego usunąć co najmniej $k$ wierzchołków. Podobnie $Q_k$ jest $k$-spójny krawędziowo, czyli po usunięciu dowolnego podzbioru co najwyżej $k-1$ krawędzi pozostanie spójny.

K-kostka jest grafem hamiltonowskim dla $k\ge 2$. Cyklowi Hamiltona w $Q_k$ odpowiada kod Graya dla $k$-bitowych ciągów binarnych.

K-kostka ma dokładnie Szablon:Wzór drzew rozpinających.

Planarność i liczba przecięć

K-kostki są planarne jedynie dla $k⩽3.$ Dla $k>3$ graf $Q_k$ jest genusu Szablon:Wzór Liczba przecięć grafu $Q_4,$ 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ęć $\mathrm{cr}(Q_5)$ wiadomo, że jest nie większa niż 56.

W 1973 roku Paul Erdős i Richard Guy postawili hipotezę, że Szablon:Wzór

Hipoteza ta jest jednak fałszywa, ponieważ znaleziono płaskie rysunki $Q_7$ o mniej niż 1760 przecięciach.

W 1991 roku Tom Madej wykazał następujące górne ograniczenie liczby przecięć grafu $Q_k$: Szablon:Wzór Z kolei w 1993 roku liczbę tę ograniczono z dołu: Szablon:Wzór