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