Грациозная разметка

Грациозная разметка в теории графов — такая вершинная разметка графа с $\text{[math]}$ $\text{[math]}$ $m$ $m$ рёбрами некоторым подмножеством целых чисел между 0 и $\text{[math]}$ $\text{[math]}$ $m$ $m$ включительно, что разные вершины помечены разными числами, и такая, что, если каждое ребро пометить абсолютной разностью меток вершин, которое оно соединяет, то все полученные разности будут различными^[1]. Граф, который допускает грациозную разметку, называется грациозным графом.

Грациозная разметка. Вершинная разметка показана чёрным цветом, рёберная — красным

Автором термина «грациозная разметка» является Соломон Голомб; Александер Роса (англ. Alexander Rosa — версия статьи «Роса, Александер» на английском языке Alexander Rosa) был первым, кто выделил этот класс разметок и ввёл его под названием $\text{[math]}$ $\text{[math]}$ $\beta$ $\beta$ -разметки в статье 1967 года про разметки графов.^[2].

Одной из главных недоказанных гипотез в теории графов является гипотеза грациозности деревьев (англ. Graceful Tree Conjecture), также известная как гипотеза Рингеля — Коцига по именам сформулировавших её Герхарда Рингеля и Антона Коцига (англ. Anton Kotzig — версия статьи «Коциг, Антон» на английском языке Anton Kotzig), которая утверждает, что все деревья грациозны. По состоянию на 2017 год гипотеза всё ещё не доказана, но из-за простоты формулировки привлекла широкое внимание любителей математики (вследствие чего появилось много неправильных доказательств), Коциг в своё время даже охарактеризовал массовые попытки доказать её как «заболевание»^[3].

Основные результатыПравить

В оригинальной статье Роса доказал, что эйлеров граф с числом рёбер m ≡ 1 (mod 4) или m ≡ 2 (mod 4) не может быть грациозным.^[2], в ней же показано, что цикл C_n грациозен тогда и только тогда, когда n ≡ 0 (mod 4) или n ≡ 3 (mod 4).

Грациозны все пути, гусеницы, все омары^[en] с совершенным паросочетанием^[4], все колёса, сети, рули^[en], шестерёнки^[en], все прямоугольные решётки^[5], а также все n-мерные гиперкубы^[6]. Все простые графы с 4 и менее вершинами грациозны, единственными неграциозными простыми графами на пяти вершинах являются 5-цикл (пятиугольник), полный граф K₅ и бабочка^[7].

Грациозны все деревья с числом вершин не более чем 27; этот результат был получен Альдредом и Маккеем (англ. Brendan McKay — версия статьи «Маккей, Брендан» на английском языке Brendan McKay) в 1998 году с помощью компьютерной программы^[5]^[8]; совершенствование их подхода (с применением другого вычислительного метода) позволило показать в 2010 году, что все деревья до 35 вершин включительно грациозны — это результат проекта распределённых вычислений Graceful Tree Verification Project под руководством Вэньцзе Фана^[9].

ПримечанияПравить

↑ Virginia Vassilevska, «Coding and Graceful Labeling of trees.» SURF 2001. PostScript Архивная копия от 25 сентября 2006 на Wayback Machine
↑ ¹ ² Rosa, A. Theory of Graphs (Internat. Sympos., Rome, 1966) (неопр.). — New York: Gordon and Breach, 1967. — С. 349—355.
↑ Huang, C.; Kotzig, A.; Rosa, A. Further results on tree labellings (неопр.) // Utilitas Mathematica. — 1982. — Т. 21. — С. 31—48.
↑ Morgan, David. All lobsters with perfect matchings are graceful (неопр.) // Bulletin of the Institute of Combinatorics and its Applications. — 2008. — Т. 53. — С. 82—85.
↑ ¹ ² Gallian, Joseph A. A dynamic survey of graph labeling (англ.) // Electronic Journal of Combinatorics (англ.) (рус. : journal. — 1998; 18-е издание в 2015. — Vol. 5. — P. Dynamic Survey 6 (electronic), в 1-м издании 43 стр., в 18-м — 389 стр. Архивировано 15 декабря 2018 года.
↑ Kotzig, Anton. Decompositions of complete graphs into isomorphic cubes (англ.) // Journal of Combinatorial Theory. Series B : journal. — 1981. — Vol. 31, no. 3. — P. 292—296. — doi:10.1016/0095-8956(81)90031-9.
↑ Weisstein, Eric W. Graceful graph (англ.) на сайте Wolfram MathWorld.
↑ Aldred, R. E. L.; McKay, Brendan D. Graceful and harmonious labellings of trees (неопр.) // Bulletin of the Institute of Combinatorics and its Applications. — 1998. — Т. 23. — С. 69—72.
↑ Fang, Wenjie. A Computational Approach to the Graceful Tree Conjecture (англ.) : journal. — 2010. — arXiv:1003.3045. Архивировано 15 августа 2016 года. См. также Graceful Tree Verification Project

ЛитератураПравить

K. Eshghi Introduction to Graceful Graphs, Sharif University of Technology, 2002.
U. N. Deshmukh and Vasanti N. Bhat-Nayak, New families of graceful banana trees — Proceedings Mathematical Sciences, 1996 — Springer
M. Haviar, M. Ivaska, Vertex Labellings of Simple Graphs, Research and Exposition in Mathematics, Volume 34, 2015.
Ping Zhang, A Kaleidoscopic View of Graph Colorings, SpringerBriefs in Mathematics, 2016 — Springer

[Vas2001-1] Virginia Vassilevska, «Coding and Graceful Labeling of trees.» SURF 2001. PostScript Архивная копия от 25 сентября 2006 на Wayback Machine

[Ros1967-2] ¹ ² Rosa, A. Theory of Graphs (Internat. Sympos., Rome, 1966) (неопр.). — New York: Gordon and Breach, 1967. — С. 349—355.

[Hua1982-3] Huang, C.; Kotzig, A.; Rosa, A. Further results on tree labellings (неопр.) // Utilitas Mathematica. — 1982. — Т. 21. — С. 31—48.

[Morgan-4] Morgan, David. All lobsters with perfect matchings are graceful (неопр.) // Bulletin of the Institute of Combinatorics and its Applications. — 2008. — Т. 53. — С. 82—85.

[Gal2015-5] ¹ ² Gallian, Joseph A. A dynamic survey of graph labeling (англ.) // Electronic Journal of Combinatorics (англ.) (рус. : journal. — 1998; 18-е издание в 2015. — Vol. 5. — P. Dynamic Survey 6 (electronic), в 1-м издании 43 стр., в 18-м — 389 стр. Архивировано 15 декабря 2018 года.

[Kot1981-6] Kotzig, Anton. Decompositions of complete graphs into isomorphic cubes (англ.) // Journal of Combinatorial Theory. Series B : journal. — 1981. — Vol. 31, no. 3. — P. 292—296. — doi:10.1016/0095-8956(81)90031-9.

[Mat2007-7] Weisstein, Eric W. Graceful graph (англ.) на сайте Wolfram MathWorld.

[8] Aldred, R. E. L.; McKay, Brendan D. Graceful and harmonious labellings of trees (неопр.) // Bulletin of the Institute of Combinatorics and its Applications. — 1998. — Т. 23. — С. 69—72.

[9] Fang, Wenjie. A Computational Approach to the Graceful Tree Conjecture (англ.) : journal. — 2010. — arXiv:1003.3045. Архивировано 15 августа 2016 года. См. также Graceful Tree Verification Project

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]