Срединный граф

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

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

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

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

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

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

Свойства

Оба красных графа являются срединными графами синего графа, но они не изоморфны.

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

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

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

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

Планарный граф (синий) и его ориентированный срединный граф (красный). Ориентация введена таким образом, чтобы серые грани (содержащие вершины исходного графа) оказывались слева.

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

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

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

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

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

Литература

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