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

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

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

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

Якщо дано зв'язний планарний граф ${\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) дорівнює сумі за зваженими ейлеровими орієнтаціями^[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].

Примітки

1. Handbook of Graph Theory / Jonathan L. Gross, Jay Yellen. — CRC Press, 2003. — С. 724. — ISBN 978-1584880905.
2. Michel Las Vergnas. On the evaluation at (3, 3) of the Tutte polynomial of a graph // Journal of Combinatorial Theory, Series B. — 1988. — Т. 35, вип. 3. — С. 367–372. — ISSN 0095-8956. — DOI:10.1016/0095-8956(88)90079-2.
3. Joanna A. Ellis-Monaghan. Identities for circuit partition polynomials, with applications to the Tutte polynomial // Advances in Applied Mathematics. — 2004. — Т. 32, вип. 1-2. — С. 188-197. — ISSN 0196-8858. — DOI:10.1016/S0196-8858(03)00079-4.
4. Michael Korn, Igor Pak. Combinatorial evaluations of the Tutte polyno. — 2003, препринт. — С. 4, Coloring edges of the medial graph.

Література

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