Медиальный график

Смежности ребер и граней в другом графе

Плоский граф (синий) и его срединный граф (красный).

В математической дисциплине теории графов срединный граф плоского графа 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 к числу седловых вершин ориентации (то есть числу вершин с инцидентными ребрами, циклически упорядоченными «внутрь, наружу, внутрь наружу»). ^[5] Поскольку многочлен Тутта инвариантен относительно вложений, этот результат показывает, что каждый срединный граф имеет одну и ту же сумму этих взвешенных эйлеровых ориентаций.

Направленный медиальный граф

Плоский граф (синий) и его ориентированный медиальный граф (красный).

Определение медиального графа можно расширить, включив в него ориентацию. Во-первых, грани медиального графа окрашены в черный цвет, если они содержат вершину исходного графа, и в белый цвет в противном случае. Эта окраска приводит к тому, что каждое ребро медиального графа граничит с одной черной гранью и одной белой гранью. Затем каждое ребро ориентируется так, что черная грань находится слева от него.

Плоский граф и его двойственный граф не имеют одного и того же направленного срединного графа; их направленные срединные графы являются транспонированными друг друга.

Используя направленный медиальный граф , можно эффективно обобщить результат по оценкам полинома Тутта в точке (3,3). Для плоского графа G n -кратное вычисление полинома Тутта в точке ( n +1, n +1) равно взвешенной сумме по всем раскраскам ребер с использованием n цветов в направленном медиальном графе G, так что каждый (возможно пустой) набор одноцветных ребер образует направленный эйлеров граф, где вес направленной эйлеровой ориентации равен 2 к числу одноцветных вершин. ^[6]

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

• Узлы и графы
• Ректификация (геометрия) — эквивалентная операция над многогранниками.

Ссылки

1. Стейниц, Эрнст (1922), «Polyeder und Raumeinteilungen», Encyclopädie der mathematischen Wissenschaften, Группа 3 (Геометрии) , стр. 1–139
2. Тейт, Питер Г. (1876–1877). «Об узлах I». Труды Королевского общества Эдинбурга . 28 : 145–190. doi :10.1017/S0080456800090633. S2CID  171186257. Исправлено 11 мая 1877 г.
3. Тейт, Питер Г. (1876–1877). «О связях (реферат)». Труды Королевского общества Эдинбурга . 9 (98): 321–332. doi :10.1017/S0370164600032363.
4. Гросс, Джонатан Л.; Йеллен, Джей, ред. (2003). Справочник по теории графов. CRC Press. стр. 724. ISBN 978-1584880905.
5. Лас Верньяс, Мишель (1988), «О вычислении в точке (3, 3) полинома Тутте графа», Журнал комбинаторной теории, Серия B , 35 (3): 367–372, doi :10.1016/0095-8956(88)90079-2, ISSN  0095-8956
6. Эллис-Монаган, Джоанна А. (2004). «Тождества для полиномов разбиения цепей с приложениями к полиному Тутта». Успехи в прикладной математике . 32 (1–2): 188–197. doi :10.1016/S0196-8858(03)00079-4. ISSN  0196-8858.

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

• Brylawski, Thomas ; Oxley, James (1992). "The Tutte Polynomial and Its Applications" (PDF) . В White, Neil (ред.). Matriod Applications . Cambridge University Press. стр. 123–225.