Русская Википедия:Грациозная разметка
Грациозная разметка в теории графов — такая вершинная разметка графа с <math>m</math> рёбрами некоторым подмножеством целых чисел между 0 и <math>m</math> включительно, что разные вершины помечены разными числами, и такая, что, если каждое ребро пометить абсолютной разностью меток вершин, которое оно соединяет, то все полученные разности будут различными[1]. Граф, который допускает грациозную разметку, называется грациозным графом.
Автором термина «грациозная разметка» является Соломон Голомб; Шаблон:Нп2 был первым, кто выделил этот класс разметок и ввёл его под названием <math>\beta</math>-разметки в статье 1967 года про разметки графов.[2].
Одной из главных недоказанных гипотез в теории графов является гипотеза грациозности деревьев (Шаблон:Lang-en), также известная как гипотеза Рингеля — Коцига по именам сформулировавших её Герхарда Рингеля и Шаблон:Нп2, которая утверждает, что все деревья грациозны. По состоянию Шаблон:На гипотеза всё ещё не доказана, но из-за простоты формулировки привлекла широкое внимание любителей математики (вследствие чего появилось много неправильных доказательств), Коциг в своё время даже охарактеризовал массовые попытки доказать её как «заболевание»[3].
Основные результаты
В оригинальной статье Роса доказал, что эйлеров граф с числом рёбер m ≡ 1 (mod 4) или m ≡ 2 (mod 4) не может быть грациозным.[2], в ней же показано, что цикл Cn грациозен тогда и только тогда, когда n ≡ 0 (mod 4) или n ≡ 3 (mod 4).
Грациозны все пути, гусеницы, все Шаблон:Iw с совершенным паросочетанием[4], все колёса, сети, Шаблон:Iw, Шаблон:Iw, все прямоугольные решётки[5], а также все n-мерные гиперкубы[6]. Все простые графы с 4 и менее вершинами грациозны, единственными неграциозными простыми графами на пяти вершинах являются 5-цикл (пятиугольник), полный граф K5 и бабочка[7].
Грациозны все деревья с числом вершин не более чем 27; этот результат был получен Альдредом и Шаблон:Нп2 в 1998 году с помощью компьютерной программы[5][8]; совершенствование их подхода (с применением другого вычислительного метода) позволило показать в 2010 году, что все деревья до 35 вершин включительно грациозны — это результат проекта распределённых вычислений Graceful Tree Verification Project под руководством Вэньцзе Фана[9].
Примечания
Литература
- 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
- ↑ Virginia Vassilevska, «Coding and Graceful Labeling of trees.» SURF 2001. PostScript Шаблон:Wayback
- ↑ 2,0 2,1 Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ 5,0 5,1 Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Mathworld
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья См. также Graceful Tree Verification Project
