Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Изящная маркировка. Метки вершин - черные, края - красные.

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

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

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

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

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

Выбранные результаты [ править ]

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

См. Также [ править ]

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

Внешние ссылки [ править ]

  • Numberphile видео про изящную гипотезу о дереве

Ссылки [ править ]

  1. ^ Вирджиния Василевска , «Кодирование и изящная маркировка деревьев». SURF 2001. PostScript
  2. ^ a b Роза, А. (1967), "О некоторых оценках вершин графа", Теория графов (Internat. Sympos., Рим, 1966) , Нью-Йорк: Гордон и Бреч, стр. 349–355, Руководство по ремонту  0223271.
  3. ^ Ван, Дао-Мин; Ян, Чэн-Чанг; Сюй, Лих-Син; Ченг, Эдди (2015), "Бесконечно много эквивалентных версий изящным дерева гипотезы", применимого анализ и дискретная математика , 9 (1): 1-12, DOI : 10,2298 / AADM141009017W , МР 3362693 
  4. ^ Монтгомери, Ричард; Покровский, Алексей; Судаков, Бенни (2020). «Доказательство гипотезы Рингеля». arXiv : 2001.02665 [ math.CO ].
  5. ^ Хуанг, C .; Коциг, А .; Роза, А. (1982), "Дальнейшие результаты по разметке деревьев", Utilitas Mathematica , 21 : 31–48, MR 0668845 .
  6. ^ Хартнетт, Кевин. «Доказательство радуги показывает, что у графиков есть однородные части» . Журнал Quanta . Проверено 29 февраля 2020 .
  7. ^ Хуанг, C .; Коциг, А .; Роза, А. (1982), "Дальнейшие результаты по разметке деревьев", Utilitas Mathematica , 21 : 31–48, MR 0668845 .
  8. ^ Роза, A. (1988), "Циклические тройные системы Штейнера и маркировка треугольных кактусов", Scientia , 1 : 87–95.
  9. ^ Морган, Дэвид (2008), «Все омары с идеальным подбором изящны», Бюллетень Института комбинаторики и ее приложений , 53 : 82–85, hdl : 10402 / era.26923.
  10. ^ a b Галлиан, Джозеф А. (1998), "Динамический обзор разметки графов" , Электронный журнал комбинаторики , 5 : Dynamic Survey 6, 43 стр. (389 стр. в 18-м изд.) (электронный), MR 1668059 .
  11. ^ Олдред, REL; Маккей, Брендан Д. (1998), "Изящные и гармоничные обозначения деревьев", Бюллетень Института комбинаторики и его приложений , 23 : 69–72, MR 1621760 .
  12. ^ Хортон, Майкл П. (2003), Изящные деревья: статистика и алгоритмы.
  13. ^ Фанг, Вэньцзе (2010), Вычислительный подход к гипотезе изящного дерева , arXiv : 1003.3045 , Bibcode : 2010arXiv1003.3045F. См. Также проект Graceful Tree Verification Project.
  14. ^ Коциг, Антон (1981), "Разложение полных графов в изоморфные кубы", Журнал комбинаторной теории, Series B , 31 (3): 292-296, DOI : 10,1016 / 0095-8956 (81) 90031-9 , М.Р. 0638285 .
  15. ^ Вайсштейн, Эрик В. "Изящный граф" . MathWorld .

Дальнейшее чтение [ править ]

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