WikiSort.ru - Не сортированное

ПОИСК ПО САЙТУ | о проекте
Грациозная разметка. Вершинная разметка показана чёрным цветом, рёберная — красным

Грациозная разметка в теории графов — такая вершинная разметка графа с рёбрами некоторым подмножеством целых чисел между 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).

Грациозны все пути, гусеницы, все омары[en] с совершенным паросочетанием[4], все колёса, сети, рули[en], шестерёнки[en], все прямоугольные решётки[5], а также все n-мерные гиперкубы[6]. Все простые графы с 4 и менее вершинами грациозны, единственными неграциозными простыми графами на пяти вершинах являются 5-цикл (пятиугольник), полный граф K5 и граф-бабочка[en][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
  2. 1 2 Rosa, A. (1967). “Theory of Graphs (Internat. Sympos., Rome, 1966)”. New York: Gordon and Breach: 349—355. MR 0223271. Параметр |contribution= пропущен (справка на английском)
  3. ↑ Huang, C.; Kotzig, A.; Rosa, A. (1982). “Further results on tree labellings”. Utilitas Mathematica. 21: 31—48. MR 0668845.
  4. ↑ Morgan, David (2008). “All lobsters with perfect matchings are graceful”. Bulletin of the Institute of Combinatorics and its Applications. 53: 82—85.
  5. 1 2 Gallian, Joseph A. (1998; 18ое издание в 2015). “A dynamic survey of graph labeling”. Electronic Journal of Combinatorics. 5: Dynamic Survey 6 (electronic), в первом издании 43 стр., в 18ом – 389 стр. MR 1668059. Проверьте дату в |year= (справка на английском)
  6. ↑ Kotzig, Anton (1981). “Decompositions of complete graphs into isomorphic cubes”. Journal of Combinatorial Theory. Series B. 31 (3): 292—296. DOI:10.1016/0095-8956(81)90031-9. MR 0638285.
  7. ↑ Weisstein, Eric W. Graceful graph (англ.) на сайте Wolfram MathWorld.
  8. ↑ Aldred, R. E. L.; McKay, Brendan D. (1998). “Graceful and harmonious labellings of trees”. Bulletin of the Institute of Combinatorics and its Applications. 23: 69—72. MR 1621760.
  9. ↑ Fang, Wenjie (2010). “A Computational Approach to the Graceful Tree Conjecture”. arXiv:1003.3045. См. также 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

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .



Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2025
WikiSort.ru - проект по пересортировке и дополнению контента Википедии