WikiSort.ru - Не сортированное

Срединный граф — граф, представляющий рёбра смежности внутри граней заданного планарного графа.

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

Если задан связный планарный граф ${\displaystyle G}$ , его срединный граф ${\displaystyle M(G)}$ содержит:

• вершину для каждого ребра ${\displaystyle G}$ ,
• ребро между двумя вершинами для каждой грани ${\displaystyle G}$ , если на ней рёбра графа ${\displaystyle G}$ идут подряд.

Срединный граф несвязного графа является несвязным объединением срединных графов компонент связности.

Свойства

Поскольку срединный граф зависит от способа вложения, срединный граф не единственнен в том смысле, что один и тот же планарный граф может иметь несколько неизоморфных срединных графов. И обратно, неизоморфные графы могут иметь тот же самый срединный граф. В частности, планарный граф и его двойственный граф имеют один срединный граф.

Срединные графы являются 4-регулярными графами. При этом любой 4-регулярный планарный граф является срединным графом некоторого планарного графа. Для связного 4-регулярного планарного графа ${\displaystyle H}$ планарный граф ${\displaystyle G}$ , для которого ${\displaystyle H}$ является срединным, можно построить следующим образом: раскрашиваются грани ${\displaystyle G}$ в два цвета (что возможно, поскольку ${\displaystyle H}$ является эйлеровым, и поскольку двойственный графу ${\displaystyle H}$ является двудольным); вершины в ${\displaystyle G}$ соответствуют граням одного цвета в ${\displaystyle H}$ . Эти вершины соединены ребром для каждой общей (для двух граней) вершины в ${\displaystyle H}$ . Заметим, что проделывая данное построение с гранями другого цвета, получим двойственный ${\displaystyle G}$ граф.

Если два графа имеют один срединный граф, они двойственны^[1].

Ориентированный срединный граф

В серединный граф может быть введена ориентация: для этого осуществляется раскраска срединного графа в два цвета в зависимости от то того, содержит ли грань срединного графа вершины исходного графа или нет, а ориентация вводится таким образом, чтобы грани какого-либо из цветов оказывались слева от рёбер.

Планарный граф и его двойственный имеют разные ориентированные срединные графы, которые являются обратными^[en] друг другу.

Многочлен Татта

Для планарного графа ${\displaystyle G}$ удвоенное значение многочлена Татта^[en] в точке (3,3) равно сумме по взвешенным эйлеровым ориентациям^[en] в срединном графе ${\displaystyle G}$ , где вес ориентации равен ${\displaystyle 2^{s}}$ (${\displaystyle s}$  — число седловых вершин ориентации, то есть число вершин, у которых инцидентные дуги упорядочены по циклу «входящая — исходящая — входящая — исходящая»)^[2]. Поскольку многочлен Татта является инвариантом при вложениях, результат показывает, что для заданного графа любой срединный граф имеет одну и ту же взвешенную сумму эйлеровых ориентаций.

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

Примечания

Литература

• Thomas Brylawski, James Oxley. Matriod Applications / Neil White. — Cambridge University Press, 1992. — С. 123–225.

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.