Медиальный график
В математической дисциплине теории графов плоского медиальный граф графа G — это другой граф M(G) который представляет смежности между ребрами на гранях G. , Медиальные графы были введены в 1922 году Эрнстом Стейницем для изучения комбинаторных свойств выпуклых многогранников . [1] хотя обратная конструкция уже использовалась Питером Тейтом в 1877 году в его фундаментальном исследовании узлов и связей . [2] [3]
Формальное определение
[ редактировать ]Для связного плоского графа G его медиальный граф M(G) имеет
- вершина для каждого ребра G и
- ребро между двумя вершинами для каждой грани графа G , в котором соответствующие ребра встречаются последовательно.
Медиальный граф несвязного графа — это непересекающееся объединение медиальных графов каждой компоненты связности. Определение медиального графа без изменений распространяется также на вложения графов на поверхностях более высокого рода.
Характеристики
[ редактировать ]
- Медиальный граф любого плоского графа является 4- правильным плоским графом.
- Для любого плоского графа G медиальный граф G и медиальный граф двойственного G изоморфны графа . И наоборот, для любого 4-регулярного плоского графа H только два плоских графа с медиальным графом H двойственны друг другу. [4]
- Поскольку медиальный граф зависит от конкретного вложения, медиальный граф планарного графа не уникален; один и тот же планарный граф может иметь неизоморфные медиальные графы. На рисунке красные графы не изоморфны, поскольку две вершины с петлями имеют общее ребро в одном графе, но не в другом.
- Каждый 4-регулярный плоский граф является медиальным графом некоторого плоского графа. Для связного 4-регулярного плоского графа H планарный граф G с H в качестве медиального графа можно построить следующим образом. Раскрасьте грани H всего в два цвета, что возможно, поскольку H эйлеров (и, следовательно, двойственный граф H двудольный). Вершины в G соответствуют граням одного цвета H. в Эти вершины соединены ребром для каждой вершины, общей для соответствующих им граней в H . Обратите внимание, что выполнение этой конструкции с использованием граней другого цвета в качестве вершин дает двойственный граф G .
- Медиальный график 3-регулярного плоского графа совпадает с его линейным графом . Однако это неверно для медиальных графов плоских графов, имеющих вершины степени больше трех.
Приложения
[ редактировать ]Для плоского графа G двойная оценка полинома Тутте в точке (3,3) равна сумме по взвешенным эйлеровым ориентациям в медиальном графе G , где вес ориентации равен 2 числу седловых вершин графа G . ориентация (то есть количество вершин с инцидентными ребрами, циклически упорядоченными «внутри, наружу, внутрь»). [5] Поскольку полином Тутте инвариантен относительно вложений, этот результат показывает, что каждый медиальный граф имеет одинаковую сумму этих взвешенных эйлеровых ориентаций.
Направленный медиальный граф
[ редактировать ]
Определение медиального графа можно расширить, включив в него ориентацию. Во-первых, грани медиального графа окрашиваются в черный цвет, если они содержат вершину исходного графа, и в белый в противном случае. Эта раскраска приводит к тому, что каждое ребро медиального графа ограничивается одной черной гранью и одной белой гранью. Затем каждое ребро ориентируется так, чтобы черная грань находилась слева от него.
Плоский граф и его двойственный граф не имеют одного и того же ориентированного медиального графа; их направленные медиальные графы транспонированы друг друга.
Используя направленный медиальный граф, можно эффективно обобщить результат на оценки полинома Тутте в (3,3). Для плоского графа n G - кратное вычисление полинома Тутте в точке ( n +1, n +1) равняется взвешенной сумме по всем раскраскам ребер с использованием n цветов в направленном медиальном графе G, так что каждый (возможно, пустой ) множество одноцветных ребер образует ориентированный эйлеров граф, где вес направленной эйлеровой ориентации равен 2 числу одноцветных вершин. [6]
См. также
[ редактировать ]- Узлы и графики
- Ректификация (геометрия) — эквивалентная операция над многогранниками.
Ссылки
[ редактировать ]- ^ Стейниц, Эрнст (1922), «Многогранники и пространственные деления», Энциклопедия математических наук, том 3 (Геометрия) , стр. 1–139.
- ^ Тейт, Питер Г. (1876–1877). «На узлах я» . Труды Королевского общества Эдинбурга . 28 : 145–190. дои : 10.1017/S0080456800090633 . S2CID 171186257 .
Пересмотрено 11 мая 1877 г.
- ^ Тейт, Питер Г. (1876–1877). «О ссылках (Аннотация)» . Труды Королевского общества Эдинбурга . 9 (98): 321–332. дои : 10.1017/S0370164600032363 .
- ^ Гросс, Джонатан Л.; Йеллен, Джей, ред. (2003). Справочник по теории графов . ЦРК Пресс. п. 724. ИСБН 978-1584880905 .
- ^ Лас Верньяс, Мишель (1988), «Об оценке в точке (3, 3) полинома Тутте графа», Журнал комбинаторной теории, серия B , 35 (3): 367–372, doi : 10.1016/0095- 8956(88)90079-2 , ISSN 0095-8956
- ^ Эллис-Монаган, Джоанна А. (2004). «Тождества для полиномов разбиения цепей с применением к полиному Тутте». Достижения прикладной математики . 32 (1–2): 188–197. дои : 10.1016/S0196-8858(03)00079-4 . ISSN 0196-8858 .
Дальнейшее чтение
[ редактировать ]- Брылавски, Томас ; Оксли, Джеймс (1992). «Полином Тутте и его приложения» (PDF) . В белом, Нил (ред.). Приложения Матриода . Издательство Кембриджского университета. стр. 123–225.