Серединний граф — граф, що подає суміжність ребер всередині граней даного планарного графа.
Формальне визначення Якщо дано зв'язний планарний граф , його серединний граф містить:
вершину для кожного ребра , ребро між двома вершинами для кожної грані якщо на ній ребра графа йдуть послідовно.
Серединний граф незв'язного графа є незв'язним об'єднанням серединних графів компонент зв'язності.
Властивості
Оскільки серединний граф залежить від способу вкладення, серединний граф не єдиний у тому сенсі, що той самий планарний граф може мати кілька неізоморфних серединних графів. І навпаки, неізоморфні графи можуть мати той самий серединний граф. Зокрема, планарний граф та його двоїстий граф мають один серединний граф.
Серединні графи є 4-регулярними графами. При цьому будь-який 4-регулярний планарний граф є серединним графом деякого планарного графа. Для зв'язного 4-регулярного планарного графа планарний граф , для якого є серединним, можна побудувати так: грані розфарбовуються у два кольори (що можливо, оскільки є ейлеровим, і оскільки двоїстий графу є двочастковим); вершини в відповідають граням одного кольору в . Ці вершини з'єднані ребром для кожної спільної (для двох граней) вершини . Зауважимо, що проробляючи цю побудову з гранями іншого кольору, отримаємо граф, двоїстий .
Якщо два графи мають один серединний граф, вони двоїсті.
Орієнтований серединний граф
У серединний граф можна ввести орієнтацію: для цього серединний граф розмальовують у два кольори в залежності від того, чи містить грань серединного графа вершини початкового графа чи ні, а орієнтацію вводять так, щоб грані якогось з кольорів виявлялися зліва від ребер.
Планарний граф та його двоїстий мають різні орієнтовані серединні графи, які є оберненими один до одного.
Многочлен Татта Для планарного графа подвоєне значення многочлена Татта в точці (3,3) дорівнює сумі за зваженими у серединному графі , де вага орієнтації дорівнює ( — число сідлових вершин орієнтації, тобто число вершин, у яких інцидентні дуги впорядковані за циклом «вхідна — вихідна — вхідна — вихідна»). Оскільки многочлен Татта є інваріантом при вкладеннях, результат показує, що для даного графа будь-який серединний граф має ту саму зважену суму ейлерових орієнтацій.
Скориставшись орієнтованим серединним графом, можна ефективно узагальнити результат обчислення многочлена Татта в точці (3,3). Для планарного графа , помножене на значення многочлена Татта у точці дорівнює зваженій сумі всіх розфарбувань дуг в кольорів в орієнтованому серединному графі , так що кожна (можливо порожня) множина дуг одного кольору утворює орієнтований ейлерів граф, де вага ейлерової орієнтації дорівнює ( — кількість одноколірних вершин, тобто вершин, всі чотири ребра, інцидентні якій, мають один колір).
Примітки
Література