Смешанный граф

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

(Сильная) собственная ${\displaystyle k}$-раскраска смешанного графа является функцией

${\displaystyle {\displaystyle c:V\rightarrow [k]}}$, где ${\displaystyle [k]:={1,2,\dots ,k}}$ такой, что ${\displaystyle {\displaystyle c(u)\neq c(v)}}$, если ${\displaystyle {\displaystyle uv\in E}}$, и ${\displaystyle {\displaystyle c(u)<c(v)}}$, если ${\displaystyle {\displaystyle {\overrightarrow {uv}}\in A}}$.[1]

Мы можем ослабить условие на наши дуги. Тогда мы можем считать слабую собственную k-раскраску смешанного графа функцией

${\displaystyle {\displaystyle c:V\rightarrow [k]}}$, где ${\displaystyle [k]:={1,2,\dots ,k}}$ такой, что ${\displaystyle {\displaystyle c(u)\neq c(v)}}$, если ${\displaystyle {\displaystyle uv\in E}}$, и ${\displaystyle {\displaystyle c(u)\leq c(v)}}$, если ${\displaystyle {\displaystyle {\overrightarrow {uv}}\in A}}$.[1] Возвращаясь к нашему примеру, это означает, что мы можем пометить голову и хвост ${\displaystyle (v,w)}$ положительным целым числом 2.

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

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

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

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

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