Kostka (teoria grafów)

Kostka, k-kostka^[1] – 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}$ ^[1].

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

W niektórych superkomputerach topologia połączeń między procesorami przyjmuje postać $k$ -kostki^[2].

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^[3].

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^[3].

K-kostka jest grafem hamiltonowskim dla $k\geq 2$ ^[3]. Cyklowi Hamiltona w $Q_{k}$ odpowiada kod Graya dla $k$ -bitowych ciągów binarnych^[4].

K-kostka ma dokładnie

T(Q_{k})=2^{-k}\prod _{i=1}^{k}(2i)^{\binom {k}{i}}=2^{2^{k}-k-1}\prod _{i=2}^{k}i^{\binom {k}{i}}

drzew rozpinających^[3].

Planarność i liczba przecięć

K-kostki są planarne jedynie dla $k\leq 3.$ Dla $k>3$ graf $Q_{k}$ jest genusu

\gamma (Q_{k})=(k-4)2^{k-3}+1

.

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ęć $\operatorname {cr} (Q_{5})$ wiadomo, że jest nie większa niż 56^[3].

W 1973 roku Paul Erdős i Richard Guy postawili hipotezę, że^[5]^[6]

\operatorname {cr} (Q_{k})={\frac {5\cdot 4^{k}}{32}}-\left\lfloor {\frac {k^{2}+1}{2}}\right\rfloor 2^{k-2}.

Hipoteza ta jest jednak fałszywa, ponieważ znaleziono płaskie rysunki $Q_{7}$ o mniej niż 1760 przecięciach^[6].

W 1991 roku Tom Madej wykazał następujące górne ograniczenie liczby przecięć grafu $Q_{k}$ ^[6]^[7]:

\operatorname {cr} (Q_{k})\leq {\frac {4^{k}}{6}}-k^{2}\cdot 2^{k-3}-3\cdot 2^{k-4}+{\frac {(-2)^{k}}{48}}

.

Z kolei w 1993 roku liczbę tę ograniczono z dołu^[6]^[8]:

\operatorname {cr} (Q_{k})>{\frac {4^{k}}{20}}-(k+1)2^{k-2}

.

Przypisy

↑ ^a ^b ^c RobinR. Wilson RobinR., Wprowadzenie do teorii grafów, Wydawnictwo Naukowe PWN, 2012, s. 33, ISBN 978-83-01-15066-2 (pol.).
↑ John P.J.P. Hayes John P.J.P., Trevor N.T.N. Mudge Trevor N.T.N., Quentin F.Q.F. Stout Quentin F.Q.F., Architecture of a Hypercube Supercomputer, „International Conference on Parallel Processing”, IEEE Computer Society Press, 1986, s. 653-660 [dostęp 2024-04-28] (ang.).
↑ ^a ^b ^c ^d ^e FrankF. Harary FrankF., John P.J.P. Hayes John P.J.P., Horng-JyhH.J. Wu Horng-JyhH.J., A survey of the theory of hypercube graphs, „Computers & Mathematics with Applications”, 15 (4), 1988, s. 277–289, DOI: 10.1016/0898-1221(88)90213-1, ISSN 0898-1221 [dostęp 2024-04-28] (ang.).
↑ E.N.E.N. Gilbert E.N.E.N., Gray Codes and Paths on the n-Cube, „Bell System Technical Journal”, 37 (3), 1958, s. 815–826, DOI: 10.1002/j.1538-7305.1958.tb03887.x [dostęp 2024-04-28] (ang.).
↑ PaulP. Erdös PaulP., RichardR. Guy RichardR., Crossing Number Problems, „The American Mathematical Monthly”, 80 (1), 1973, s. 55, DOI: 10.1080/00029890.1973.11993230, ISSN 0002-9890 [dostęp 2024-04-28] (ang.).
↑ ^a ^b ^c ^d KieranK. Clancy KieranK., MichaelM. Haythorpe MichaelM., AlexA. Newcombe AlexA., A survey of graphs with known or bounded crossing numbers, 2021, s. 52-53, DOI: 10.48550/arXiv.1901.05155 [dostęp 2024-04-28] (ang.).
↑ TomT. Madej TomT., Bounds for the crossing number of the N‐cube, „Journal of Graph Theory”, 15 (1), 1991, s. 81–97, DOI: 10.1002/jgt.3190150109, ISSN 0364-9024 [dostęp 2024-04-28] (ang.).
↑ OndrejO. Sýkora OndrejO., ImrichI. Vrťo ImrichI., On crossing numbers of hypercubes and cube connected cycles, „BIT Numerical Mathematics”, 33 (2), 1993, s. 232–237, DOI: 10.1007/BF01989746, ISSN 1572-9125 [dostęp 2024-04-28] (ang.).

Linki zewnętrzne

Eric W.E.W. Weisstein Eric W.E.W., Hypercube Graph, [w:] MathWorld, Wolfram Research [dostęp 2024-04-28] (ang.).

[:0-1] RobinR. Wilson RobinR., Wprowadzenie do teorii grafów, Wydawnictwo Naukowe PWN, 2012, s. 33, ISBN 978-83-01-15066-2 (pol.).

[2] John P.J.P. Hayes John P.J.P., Trevor N.T.N. Mudge Trevor N.T.N., Quentin F.Q.F. Stout Quentin F.Q.F., Architecture of a Hypercube Supercomputer, „International Conference on Parallel Processing”, IEEE Computer Society Press, 1986, s. 653-660 [dostęp 2024-04-28] (ang.).

[:1-3] FrankF. Harary FrankF., John P.J.P. Hayes John P.J.P., Horng-JyhH.J. Wu Horng-JyhH.J., A survey of the theory of hypercube graphs, „Computers & Mathematics with Applications”, 15 (4), 1988, s. 277–289, DOI: 10.1016/0898-1221(88)90213-1, ISSN 0898-1221 [dostęp 2024-04-28] (ang.).

[4] E.N.E.N. Gilbert E.N.E.N., Gray Codes and Paths on the n-Cube, „Bell System Technical Journal”, 37 (3), 1958, s. 815–826, DOI: 10.1002/j.1538-7305.1958.tb03887.x [dostęp 2024-04-28] (ang.).

[5] PaulP. Erdös PaulP., RichardR. Guy RichardR., Crossing Number Problems, „The American Mathematical Monthly”, 80 (1), 1973, s. 55, DOI: 10.1080/00029890.1973.11993230, ISSN 0002-9890 [dostęp 2024-04-28] (ang.).

[:2-6] KieranK. Clancy KieranK., MichaelM. Haythorpe MichaelM., AlexA. Newcombe AlexA., A survey of graphs with known or bounded crossing numbers, 2021, s. 52-53, DOI: 10.48550/arXiv.1901.05155 [dostęp 2024-04-28] (ang.).

[7] TomT. Madej TomT., Bounds for the crossing number of the N‐cube, „Journal of Graph Theory”, 15 (1), 1991, s. 81–97, DOI: 10.1002/jgt.3190150109, ISSN 0364-9024 [dostęp 2024-04-28] (ang.).

[8] OndrejO. Sýkora OndrejO., ImrichI. Vrťo ImrichI., On crossing numbers of hypercubes and cube connected cycles, „BIT Numerical Mathematics”, 33 (2), 1993, s. 232–237, DOI: 10.1007/BF01989746, ISSN 1572-9125 [dostęp 2024-04-28] (ang.).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]