Серединний граф
Серединний граф — граф, що подає суміжність ребер всередині граней даного планарного графа.
Якщо дано зв'язний планарний граф , його серединний граф містить:
- вершину для кожного ребра ,
- ребро між двома вершинами для кожної грані якщо на ній ребра графа йдуть послідовно.
Серединний граф незв'язного графа є незв'язним об'єднанням серединних графів компонент зв'язності.
Оскільки серединний граф залежить від способу вкладення, серединний граф не єдиний у тому сенсі, що той самий планарний граф може мати кілька неізоморфних серединних графів. І навпаки, неізоморфні графи можуть мати той самий серединний граф. Зокрема, планарний граф та його двоїстий граф мають один серединний граф.
Серединні графи є 4-регулярними графами. При цьому будь-який 4-регулярний планарний граф є серединним графом деякого планарного графа. Для зв'язного 4-регулярного планарного графа планарний граф , для якого є серединним, можна побудувати так: грані розфарбовуються у два кольори (що можливо, оскільки є ейлеровим, і оскільки двоїстий графу є двочастковим); вершини в відповідають граням одного кольору в . Ці вершини з'єднані ребром для кожної спільної (для двох граней) вершини . Зауважимо, що проробляючи цю побудову з гранями іншого кольору, отримаємо граф, двоїстий .
Якщо два графи мають один серединний граф, вони двоїсті[1].
У серединний граф можна ввести орієнтацію: для цього серединний граф розмальовують у два кольори в залежності від того, чи містить грань серединного графа вершини початкового графа чи ні, а орієнтацію вводять так, щоб грані якогось з кольорів виявлялися зліва від ребер.
Планарний граф та його двоїстий мають різні орієнтовані серединні графи, які є оберненими один до одного.
Для планарного графа подвоєне значення многочлена Татта в точці (3,3) дорівнює сумі за зваженими ейлеровими орієнтаціями[en] у серединному графі , де вага орієнтації дорівнює ( — число сідлових вершин орієнтації, тобто число вершин, у яких інцидентні дуги впорядковані за циклом «вхідна — вихідна — вхідна — вихідна»)[2]. Оскільки многочлен Татта є інваріантом при вкладеннях, результат показує, що для даного графа будь-який серединний граф має ту саму зважену суму ейлерових орієнтацій.
Скориставшись орієнтованим серединним графом, можна ефективно узагальнити результат обчислення многочлена Татта в точці (3,3). Для планарного графа , помножене на значення многочлена Татта у точці дорівнює зваженій сумі всіх розфарбувань дуг в кольорів в орієнтованому серединному графі , так що кожна (можливо порожня) множина дуг одного кольору утворює орієнтований ейлерів граф, де вага ейлерової орієнтації дорівнює ( — кількість одноколірних вершин, тобто вершин, всі чотири ребра, інцидентні якій, мають один колір)[3][4].
- ↑ Handbook of Graph Theory / Jonathan L. Gross, Jay Yellen. — CRC Press, 2003. — С. 724. — ISBN 978-1584880905.
- ↑ 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:.
- ↑ 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:.
- ↑ 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.