Змішаний граф

Змі́шаний граф G = (V, E, A) — математичний об'єкт, що складається з набору вершин (або вузлів) V, набору (неорієнтованих) ребер E і набору спрямованих ребер (або дуг) A.

Визначення та позначення

Приклад змішаного графа

Розглянемо сусідні вершини $u,v\in V$. Орієнто́ваним ребро́м, називають дугу, ребро з орієнтацією, яке позначають ${\displaystyle {\overrightarrow {uv}}}$ або ${\displaystyle (u,v)}$ (варто зауважити, що $u$ це хвіст, а $v$ це голова дуги). Неорієнто́ваним ребро́м або просто ребро́м, називають ребро без орієнтації і позначають ${\displaystyle uv}$ або $[u,v]$.

У розглянутому прикладі застосування не буде циклів або кратних ребер змішаних графів.

Маршрут у змішаному графі — це послідовність ${\displaystyle v_{0},c_{1},v_{1},c_{2},v_{2},\dots ,c_{k},v_{k}}$ вершин і ребер/дуг, така що для всіх індексів ${\displaystyle i}$, елемент ${\displaystyle c_{i}=v_{i}v_{i+1}}$є ребром графа або елемент ${\displaystyle c_{i}={\overrightarrow {v_{i}v_{i+1}}}}$ є дугою графа. Цей маршрут є шляхом, якщо в ньому не повторюються ребра, дуги чи вершини, крім, можливо, першої й останньої вершин. Шлях є замкнутим, якщо його перша й остання вершини збігаються, і замкнутий шлях є циклом, якщо в ньому не повторюються вершини, крім першої й останньої. Змішаний граф є ациклічним, якщо він не містить циклу.

Розфарбовування

Приклад змішаного графа

Розфарбовування змішаного графа можна розглядати як маркування або присвоєння $k$ різних кольорів (де $k$ — додатне ціле число) вершинам змішаного графа. Вершинам, з'єднаним ребром, слід призначити різні кольори. Кольори можна подати числами від 1 до $k$, а для спрямованої дуги хвіст дуги має бути позначеним числом меншим, ніж голова дуги.

Приклад

Наприклад, розглянемо фігуру праворуч. Доступні нам k-кольори для фарбування нашого змішаного графа: ${\displaystyle \{1,2,3\}}$. Оскільки ${\displaystyle u}$ і ${\displaystyle v}$ пов'язані ребром, вони повинні мати різні кольори або числа (${\displaystyle u}$ і ${\displaystyle v}$ позначені 1 і 2 відповідно). У нас також є дуга від ${\displaystyle v}$ до ${\displaystyle w}$. Оскільки ми маємо справу з дугою, де орієнтація призначає порядок чисел, ми повинні позначити хвіст (${\displaystyle v}$) меншим кольором (або цілим числом з нашого набору), ніж голову (${\displaystyle w}$) дуги.

Сильне і слабке розфарбування

(Сильне) власне $k$-розфарбування змішаного графа є функцією

${\displaystyle c:V\rightarrow [k]}$, де $[k]:={1,2,\dots ,k}$ такою, що ${\displaystyle c(u)\neq c(v)}$, якщо ${\displaystyle uv\in E}$, і ${\displaystyle c(u)<c(v)}$, якщо ${\displaystyle {\overrightarrow {uv}}\in A}$.

Можна послабити умову на дуги. Тоді ми можемо вважати слабке власне k-розфарбування змішаного графа функцією

${\displaystyle c:V\rightarrow [k]}$, де $[k]:={1,2,\dots ,k}$ такою, що ${\displaystyle c(u)\neq c(v)}$, якщо ${\displaystyle uv\in E}$, і ${\displaystyle c(u)\leq c(v)}$, якщо ${\displaystyle {\overrightarrow {uv}}\in A}$.

Повертаючись до прикладу, це означає, що ми можемо позначити голову і хвіст $(v,w)$ додатним цілим числом 2.

Існування

Для змішаного графа розфарбування може існувати чи не існувати. Для того, щоб змішаний граф мав $k$-розфарбування, він не повинен містити ніяких спрямованих циклів. Якщо таке $k$-розфарбування існує, найменше $k$, необхідне для того, щоб правильно розфарбувати граф, називають його хроматичним числом, що позначається ${\displaystyle \chi (G)}$. Кількість власних $k$-розфарбувань можна порахувати як поліноміальну функцію від $k$. Її називають хроматичним поліномом графа $G$ (за аналогією з хроматичним поліномом неорієнтованих графів) і позначають як ${\displaystyle \chi _{G}(k)}$.

Обчислення слабких хроматичних поліномів

Для обчислення слабких хроматичних поліномів змішаних графів можна використати формулу видалення-стягування. Цей метод включає видалення ребра або дуги і стягування (або об'єднання) вершин, що інцидентних цьому ребру (або дузу), з утворенням однієї вершини. Після видалення ребра $e$ зі змішаного графа $G=(V,E,A)$ отримуємо змішаний граф $(V,E-e,A)$. Це видалення ребра $e$ можна позначити як $G-e$. Аналогічно, видаляючи дугу $a$ зі змішаного графа, отримуємо $(V,E,A-a)$, де ми можемо позначити видалення $a$ as $G-a$. Крім того, ми можемо позначити скорочення $e$ і $a$ як $G/e$ і $G/a$, відповідно. З наведених тверджень, отримуємо такі рівняння для обчислення хроматичного полінома змішаного графа:

1. ${\displaystyle \mathrm {X} _{G}(k)=\chi _{G-e}(k)-\chi _{G/e}(k)}$
2. ${\displaystyle \chi _{G}(k)=\chi _{G-a}(k)+\chi _{G/a}(k)-\chi _{G_{a}}(k)}$

Застосування

Задача планування

Змішані графи можна використати для моделювання задач планування робіт, у яких має виконуватися сукупність робіт з урахуванням певних часових обмежень. У задачах цього типу неспрямовані ребра можна використати для моделювання несумісності двох робіт (вони не можуть виконуватися одночасно). Спрямовані ребра можна використати для моделювання обмеження пріоритету, за яким одна робота має бути виконаною перед іншою. Граф, визначений у такий спосіб на основі задачі планування, називають диз'юнктивним графом. Задачу розфарбовування змішаного графа можна використати для знаходження розкладу найменшої довжини для виконання всіх робіт.

Баєсове висновування

Змішані графи також використовують як графічні моделі байєсового висновування. У цьому контексті ациклічний змішаний граф (без циклів спрямованих ребер) також називають ланцюговим графом. Спрямовані ребра цих графів використовують для вказання причинного зв'язку між двома подіями, в якому результат першої події впливає на ймовірність другої події. Неспрямовані ребра вказують на непричинну кореляцію між двома подіями. Зв'язну компоненту неорієнтованого підграфа ланцюгового графа називають ланцюгом. Ланцюговий граф можна перетворити на неорієнтований граф, побудувавши його моральний граф, неорієнтований граф, сформований із ланцюгового графа додаванням неорієнтованих ребер між парами вершин, які мають вихідні ребра до одного ланцюга, з відкиданням орієнтації спрямованих ребер.

Посилання

• Weisstein, Eric W. Змішаний граф(англ.) на сайті Wolfram MathWorld.