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

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

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

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

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

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

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

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

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

Примечания

  1. ↑ Virginia Vassilevska, «Coding and Graceful Labeling of trees.» SURF 2001. PostScript Архивная копия от 25 сентября 2006 на Wayback Machine
  2. ↑ 1 2 Rosa, A. Theory of Graphs (Internat. Sympos., Rome, 1966) (неопр.). — New York: Gordon and Breach, 1967. — С. 349—355.
  3. ↑ Huang, C.; Kotzig, A.; Rosa, A. Further results on tree labellings (неопр.) // Utilitas Mathematica. — 1982. — Т. 21. — С. 31—48.
  4. ↑ Morgan, David. All lobsters with perfect matchings are graceful (неопр.) // Bulletin of the Institute of Combinatorics and its Applications. — 2008. — Т. 53. — С. 82—85.
  5. ↑ 1 2 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 года.
  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.
  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

Литература

  • 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