Изящная маркировка - Graceful labeling

Изящная маркировка. Вершина этикетки черные, края - красные

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

Название «изящная разметка» связано с Соломон В. Голомб; этот вид маркировки изначально получил название β-мечение Александра Розы в статье 1967 года о разметке графиков.^[2]

Основная гипотеза теории графов - это Гипотеза изящного дерева или же Гипотеза Рингеля – Котцига, названный в честь Герхард Рингель и Антон Коциг, который предполагает, что все деревья изящны. Это все еще открытая гипотеза, хотя родственная, но немного более слабая гипотеза, известная как гипотеза Рингеля, была доказана в 2020 году.^[3][4][5] Гипотеза Рингеля – Котцига также известна как «гипотеза изящной разметки». Коциг однажды назвал попытку доказать гипотезу «болезнью».^[6]

Еще одна более слабая версия изящной маркировки - это возле изящная разметка, в которой вершины могут быть помечены с использованием некоторого подмножества целые числа между 0 и м + 1 включительно, так что никакие две вершины не имеют общей метки, и каждое ребро однозначно идентифицируется абсолютная разница между его конечными точками, так что эта величина находится между 1 и м + 1 включительно.

Еще одна гипотеза теории графов - это Гипотеза Розы, названный в честь Александр Роза, который говорит, что все треугольные кактусы изящны или почти изящны.^[7]

Избранные результаты

• В своей оригинальной статье Роза доказал, что Граф Эйлера с количеством ребер м ≡ 1 (мод 4) или м ≡ 2 (мод. 4) не может быть изящным.^[2]
• Также в своей оригинальной статье Роза доказал, что цикл C_п изящно тогда и только тогда, когда п ≡ 0 (мод 4) или п ≡ 3 (мод.4).
• Все графы путей и гусеничные графики изящны.
• Все графики лобстеров с идеальное соответствие изящны.^[8]
• Все деревья с не более чем 27 вершинами изящны; этот результат показали Олдред и Маккей в 1998 году с помощью компьютерной программы.^[9][10] Это было распространено на деревья с не более чем 29 вершинами в диссертации Майкла Хортона с отличием.^[11] Другое расширение этого результата до деревьев с 35 вершинами было заявлено в 2010 году проектом Graceful Tree Verification Project. распределенных вычислений проект под руководством Вэньцзе Фана.^[12]
• Все колесные графики, веб-графики, графики руля, графики передач, и прямоугольные сетки изящны.^[9]
• Все п-размерный гиперкубы изящны.^[13]
• Все простые графики с четырьмя или менее вершинами изящны. Единственные не изящные простые графы с пятью вершинами - это 5-цикл (пятиугольник ); то полный график K₅; и график бабочки.^[14]

Смотрите также

• Изящная маркировка
• Список домыслов

внешняя ссылка

• Numberphile видео о изящном дереве

Рекомендации

1. Вирджиния Василевская, «Кодирование и изящная маркировка деревьев». СЕРФ 2001. PostScript
2. Роза, А. (1967), "О некоторых оценках вершин графа", Теория графов (Международные симпозиумы, Рим, 1966 г.), Нью-Йорк: Гордон и Брич, стр. 349–355, МИСТЕР  0223271.
3. Монтгомери, Ричард; Покровский, Алексей; Судаков, Бенни (2020). «Доказательство гипотезы Рингеля». arXiv:2001.02665 [math.CO ].
4. Хуанг, С .; Коциг, А.; Роза, А. (1982), "Дальнейшие результаты по разметке деревьев", Utilitas Mathematica, 21: 31–48, МИСТЕР  0668845.
5. Хартнетт, Кевин. «Доказательство радуги показывает, что у графиков есть однородные части». Журнал Quanta. Получено 2020-02-29.
6. Хуанг, С .; Коциг, А.; Роза, А. (1982), "Дальнейшие результаты по разметке деревьев", Utilitas Mathematica, 21: 31–48, МИСТЕР  0668845.
7. Роза, А. (1988), "Циклические тройные системы Штейнера и маркировка треугольных кактусов", Scientia, 1: 87–95.
8. Морган, Дэвид (2008), «Все омары с идеальным сочетанием изящны», Вестник Института комбинаторики и ее приложений, 53: 82–85, HDL:10402 / эпоха 26923.
9. Галлиан, Джозеф А. (1998), «Динамический обзор разметки графиков», Электронный журнал комбинаторики, 5: Dynamic Survey 6, 43 стр. (389 стр. В 18 изд.) (Электронная), МИСТЕР  1668059.
10. Aldred, R. E. L .; Маккей, Брендан Д. (1998), "Изящные и гармоничные обозначения деревьев", Вестник Института комбинаторики и ее приложений, 23: 69–72, МИСТЕР  1621760.
11. Хортон, Майкл П. (2003), Изящные деревья: статистика и алгоритмы.
12. Клык, Вэньцзе (2010), Вычислительный подход к гипотезе изящного дерева, arXiv:1003.3045, Bibcode:2010arXiv1003.3045F. Смотрите также Проект проверки изящного дерева
13. Коциг, Антон (1981), «Разложение полных графов на изоморфные кубы», Журнал комбинаторной теории, серия B, 31 (3): 292–296, Дои:10.1016/0095-8956(81)90031-9, МИСТЕР  0638285.
14. Вайсштейн, Эрик В. «Изящный график». MathWorld.

дальнейшее чтение

• (К. Эшги) Введение в Graceful Graphs, Технологический университет Шарифа, 2002 г.
• (У. Н. Дешмук и Васанти Н. Бхат-Наяк), Новые семейства изящных банановых деревьев - Труды математических наук, 1996 - Спрингер
• (М. Хавиар, М. Иваска), Разметка вершин простых графов, Исследования и изложение по математике, Том 34, 2015.
• (Пинг Чжан ), Калейдоскопический взгляд на раскраски графиков, SpringerBriefs in Mathematics, 2016 - Springer