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

Серединний граф — граф, що подає суміжність ребер всередині граней даного планарного графа.

Планарний граф (синій) та його серединний граф (червоний).

Формальне визначення

Якщо дано зв'язний планарний граф $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.