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

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

Если задан связный планарный граф ${\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].

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

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

Для планарного графа ${\displaystyle G}$ удвоенное значение многочлена Татта в точке (3,3) равно сумме по взвешенным эйлеровым ориентациям^[англ.] в срединном графе ${\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.