Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Плоский график (синий) и его средний график (красный).

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

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

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

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

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

  • Брылавский, Томас ; Оксли, Джеймс (1992). «Многочлен Тутте и его приложения» (PDF) . В белом, Нил (ред.). Приложения Matriod . Издательство Кембриджского университета. С. 123–225.