Смешанный граф (Vbyoguudw ijgs)

Смешанный граф G = (V, E, A) представляет собой математический объект, состоящий из набора вершин (или узлов) V, набора (неориентированных) ребер E и набора направленных ребер (или дуг) A.^[1]

Определения и обозначения

Дополнительная информация: Граф (математика)

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

Дополнительная информация: Кратные рёбра

Дополнительная информация: Петля (теория графов)

В качестве нашего примера применения мы не будем рассматривать циклы или кратные ребра смешанных графов.

Маршрут в смешанном графе — это последовательность ${\displaystyle v_{0},c_{1},v_{1},c_{2},v_{2},\dots ,c_{k},v_{k}}$ вершин и ребер/дуг, такая что для всеx индексов ${\displaystyle i}$ , элемент ${\displaystyle c_{i}=v_{i}v_{i+1}}$ является ребром графа или элемент ${\displaystyle c_{i}={\overrightarrow {v_{i}v_{i+1}}}}$ является дугой графа. Этот маршрут является путем, если в нем не повторяются ребра, дуги или вершины, кроме, возможно, первой и последней вершин. Путь является замкнутым, если его первая и последняя вершины совпадают, и замкнутый путь является циклом, если в нем не повторяются вершины, кроме первой и последней. Смешанный граф является ациклическим, если он не содержит цикла.

Раскраска

Дополнительная информация: Раскраска графов

Раскраску смешанного графа можно рассматривать как маркировку или присвоение $k$ разных цветов (где $k$ — положительное целое число) вершинам смешанного графа.^[3] Вершинам, соединенным ребром должны быть назначены разные цвета. Цвета могут быть представлены числами от 1 до $k$ , а для направленной дуги хвост дуги должен быть обозначен числом меньшим, чем голова дуги.^[3]

Пример

Например, рассмотрим фигуру справа. Доступные нам 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}$ .^[1]

Мы можем ослабить условие на наши дуги. Тогда мы можем считать слабую собственную 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}$ .^[1] Возвращаясь к нашему примеру, это означает, что мы можем пометить голову и хвост $(v,w)$ положительным целым числом 2.

Существование

Для смешанного графа раскраска может существовать или не существовать. Для того чтобы смешанный граф имел $k$ -раскраску, он не должен содержать никаких направленных циклов.^[2] Если такая $k$ -раскраска существует, то мы обозначаем наименьшее $k$ , необходимое для того, чтобы правильно раскрасить наш граф, как хроматическое число, обозначаемое ${\displaystyle \chi (G)}$ .^[2] Мы можем посчитать количество собственных $k$ -раскрасок как полиномиальную функцию от $k$ . Это называется хроматическим полиномом нашего графа $G$ (по аналогии с хроматическим полиномом неориентированных графов) и может быть обозначено как ${\displaystyle \chi _{G}(k)}$ .^[1]

Вычисление слабых хроматических полиномов

Формула удаления-стягивания может быть использована для вычисления слабых хроматических полиномов смешанных графов. Этот метод включает удаление ребра или дуги и сжатие (или соединение) оставшихся вершин, находящихся на этом ребре (или дуге), для формирования одной вершины.^[1] После удаления ребра $e$ из смешанного графа $G=(V,E,A)$ мы получаем смешанный граф $(V,E-e,A)$ .^[1] Мы можем обозначить это удаление ребра $e$ как $G-e$ . Аналогично, удаляя дугу $a$ из смешанного графа, мы получаем $(V,E,A-a)$ , где мы можем обозначить удаление $a$ as $G-a$ .^[1] Кроме того, мы можем обозначить сокращение $e$ и $a$ как $G/e$ и $G/a$ , соответственно.^[1] Из приведенных утверждений,^[1] мы получаем следующие уравнения для вычисления хроматического полинома смешанного графа:

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

Приложения

Задача планирования

Смешанные графы могут использоваться для моделирования задач планирования работ, в которых должен выполняться сбор задач, с учетом определенных временных ограничений. В этом типе задачи ненаправленные ребра могут использоваться для моделирования ограничения того, что две задачи несовместимы (они не могут быть выполнены одновременно). Направленные ребра могут использоваться для моделирования ограничений приоритета, в которых одна задача должна быть выполнена перед другой. Граф, определенный таким образом из задачи планирования, называется дизъюнктивным графом. Смешанную задачу раскраски графов можно использовать для нахождения расписания минимальной длины для выполнения всех задач.^[2]

Байесовский вывод

Смешанные графы также используются в качестве графических моделей для байесовского вывода. В этом контексте ациклический смешанный граф (без циклов направленных ребер) также называется цепным графом. Направленные ребра этих графов используются для указания причинной связи между двумя событиями, в которой исход первого события влияет на вероятность второго события. Ненаправленные ребра указывают на не причинную корреляцию между двумя событиями. Связная компонента неориентированного подграфа цепного графа называется цепочкой. Граф цепочки может быть преобразован в неориентированный граф путем построения его морального графа, неориентированного графа, сформированного из графа цепи путем добавления неориентированных ребер между парами вершин, имеющих исходящие ребра, в одну и ту же цепочку, не учитывая ориентацию направленных ребер.^[4]

Примечания

↑ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ ¹⁰ ¹¹ Matthias Beck, Daniel Blado, Joseph Crawford, Taïna Jean-Louis, Michael Young. On Weak Chromatic Polynomials of Mixed Graphs (англ.) // Graphs and Combinatorics. — 2015-01-01. — Vol. 31, iss. 1. — P. 91–98. — ISSN 1435-5914. — doi:10.1007/s00373-013-1381-1.
↑ ¹ ² ³ ⁴ ⁵ B. Ries. Coloring some classes of mixed graphs (англ.) // Discrete Applied Mathematics. — 2007-01-01. — Vol. 155, iss. 1. — P. 1–6. — ISSN 0166-218X. — doi:10.1016/j.dam.2006.05.004. Архивировано 17 мая 2022 года.
↑ ¹ ² Pierre Hansen, Julio Kuplinsky, Dominique de Werra. Mixed graph colorings (англ.) // Mathematical Methods of Operations Research. — 1997-02-01. — Vol. 45, iss. 1. — P. 145–160. — ISSN 1432-5217. — doi:10.1007/BF01194253.
↑ Robert G. Cowell, Philip Dawid, Steffen L. Lauritzen, David J. Spiegelhalter. Probabilistic Networks and Expert Systems: Exact Computational Methods for Bayesian Networks. — Springer Science & Business Media, 2007-07-16. — 340 с. — ISBN 978-0-387-71823-1.

Ссылки

Weisstein, Eric W. «Mixed Graph» MathWorld

[:0-1] ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ ¹⁰ ¹¹ Matthias Beck, Daniel Blado, Joseph Crawford, Taïna Jean-Louis, Michael Young. On Weak Chromatic Polynomials of Mixed Graphs (англ.) // Graphs and Combinatorics. — 2015-01-01. — Vol. 31, iss. 1. — P. 91–98. — ISSN 1435-5914. — doi:10.1007/s00373-013-1381-1.

[:1-2] ¹ ² ³ ⁴ ⁵ B. Ries. Coloring some classes of mixed graphs (англ.) // Discrete Applied Mathematics. — 2007-01-01. — Vol. 155, iss. 1. — P. 1–6. — ISSN 0166-218X. — doi:10.1016/j.dam.2006.05.004. Архивировано 17 мая 2022 года.

[:2-3] ¹ ² Pierre Hansen, Julio Kuplinsky, Dominique de Werra. Mixed graph colorings (англ.) // Mathematical Methods of Operations Research. — 1997-02-01. — Vol. 45, iss. 1. — P. 145–160. — ISSN 1432-5217. — doi:10.1007/BF01194253.

[4] Robert G. Cowell, Philip Dawid, Steffen L. Lauritzen, David J. Spiegelhalter. Probabilistic Networks and Expert Systems: Exact Computational Methods for Bayesian Networks. — Springer Science & Business Media, 2007-07-16. — 340 с. — ISBN 978-0-387-71823-1.

[1]

[2]

[3]

[4]