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 edytuj

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ęć edytuj

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 edytuj

↑ ^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 edytuj

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]