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

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

в математический дисциплина теория графов, то медиальный график из плоский график грамм это еще один график M (G) который представляет собой смежности между ребрами в гранях грамм. Медиальные графы были введены в 1922 г. Эрнст Стейниц изучить комбинаторные свойства выпуклые многогранники,[1] Хотя обратная конструкция уже использовался Питер Тейт в 1877 году в его фундаментальном исследовании узлы и звенья.[2][3]

Формальное определение

Учитывая подключенный плоский график грамм, его средний график M (G) имеет

  • вершина для каждого ребра грамм и
  • ребро между двумя вершинами для каждой грани грамм в котором соответствующие им ребра встречаются последовательно.

Медиальный граф несвязного графа - это несвязное объединение медиальных графов каждого связного компонента. Определение медиального графа также распространяется без изменений на вложения графов на поверхностях высшего рода.

Характеристики

Два красных графика являются средними графиками синего графика, но это не так. изоморфный.
  • Медиальный граф любого плоского графа представляет собой 4-обычный плоский граф.
  • Для любого плоского графа грамм, медиальный график грамм и средний график двойственный граф из грамм изоморфны. Наоборот, для любого 4-регулярного плоского графа ЧАС, единственные два плоских графа с медиальным графом ЧАС двойственны друг другу.[4]
  • Поскольку медиальный граф зависит от конкретного вложения, медиальный граф плоского графа не уникален; тот же планарный граф может иметь не-изоморфный медиальные графы. На рисунке красные графы не изоморфны, потому что две вершины с петлями имеют общее ребро в одном графе, но не в другом.
  • Каждый 4-регулярный плоский граф является средним графом некоторого плоского графа. Для связного 4-регулярного плоского графа ЧАС, планарный граф грамм с ЧАС так как его средний граф можно построить следующим образом. Раскрась лица ЧАС всего двумя цветами, что возможно, так как ЧАС эйлеров (и, следовательно, двойственный граф ЧАС двудольный). Вершины в грамм соответствуют граням одного цвета в ЧАС. Эти вершины соединены ребром для каждой вершины, общей для их соответствующих граней в ЧАС. Обратите внимание, что выполнение этого построения с использованием граней другого цвета в качестве вершин дает двойственный граф грамм.
  • Медиальный граф 3-регулярного плоского графа совпадает с его линейный график. Однако это неверно для средних графов плоских графов, у которых степень вершин больше трех.

Приложения

Для плоского графа грамм, вдвое больше оценки Полином Тутте в точке (3,3) равна сумме по взвешенным Эйлеровы ориентации в среднем графике грамм, где вес ориентации равен 2 количеству седловых вершин ориентации (то есть количеству вершин с инцидентными ребрами, циклически упорядоченными «вход, выход, выход»).[5] Поскольку полином Тутте инвариантен относительно вложений, этот результат показывает, что каждый медиальный граф имеет одинаковую сумму этих взвешенных эйлеровых ориентаций.

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

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

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

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

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

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

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

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

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