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

В теории графов смешанный граф $G = (V, E, A)$ — это граф , состоящий из множества вершин $V$ , множества (неориентированных) ребер $E$ и множества ориентированных ребер (или дуг) $A.$ ^[1 ]

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

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

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

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

Раскрашивание

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

Пример

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

Сильная и слабая окраска

(Сильная) правильная k $-$ раскраска смешанного графа — это функция $c : V \to [k]$ , где $[k] := {1, 2, \dots, k}$ такая, что $c (u) \neq c (v),$ если $uv \in E$ , и $c (u) < c (v),$ если . ^[1] ${\overrightarrow {uv}}\in A$

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

Подсчет

Раскраска может существовать или не существовать для смешанного графа. Для того чтобы смешанный граф имел $k$ -раскраску, граф не может содержать никаких направленных циклов. ^[2] Если такая $k$ -раскраска существует, то мы ссылаемся на наименьшее $k,$ необходимое для того, чтобы правильно раскрасить наш граф, как на хроматическое число , обозначаемое как $χ (G)$ . ^[2] Количество правильных $k$ -раскрасок является полиномиальной функцией от $k,$ называемой хроматическим полиномом нашего графа $G$ (по аналогии с хроматическим полиномом неориентированных графов) и может быть обозначено как $χ G (k)$ . ^[1]

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

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

$\chi _{G}(k)=\chi _{Ge}(k)-\chi _{G/e}(k)$ ,
$\chi _{G}(k)=\chi _{Ga}(k)+\chi _{G/a}(k)-\chi _{G_{a}}(k)$ .

Приложения

Проблема планирования

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

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

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

Примечания

^ abcd Бек и др. (2013, стр. 1)
^ abcde Райс (2007, стр. 1)
^ Аб Хансен, Куплинский и де Верра (1997, стр. 1)
^ ab Бек и др. (2013, стр. 4)
^ Бек и др. (2013, стр. 5)
^ Коуэлл и др. (1999).

Ссылки

Бек, М.; Бладо, Д.; Кроуфорд, Дж.; Жан-Луи, Т.; Янг, М. (2013), «О слабых хроматических многочленах смешанных графов», Графы и комбинаторика , 31 : 91–98, arXiv : 1210.4634 , doi : 10.1007/s00373-013-1381-1.
Коуэлл, Роберт Г.; Дэвид, А. Филип ; Лауритцен, Штеффен Л .; Шпигельхальтер, Дэвид Дж. (1999), Вероятностные сети и экспертные системы: точные методы вычисления для байесовских сетей, Springer-Verlag, Нью-Йорк, стр. 27, номер домена : 10.1007/0-387-22630-3 (неактивен 25 октября 2024 г.), ISBN 0-387-98767-3{{citation}}: CS1 maint: DOI неактивен по состоянию на октябрь 2024 г. ( ссылка )
Хансен, Пьер; Куплински, Хулио; де Верра, Доминик (1997), «Смешанные раскраски графов», Математические методы исследования операций , 45 (1): 145–160, doi :10.1007/BF01194253, MR 1435900.
Райс, Б. (2007), «Раскраска некоторых классов смешанных графов», Дискретная прикладная математика , 155 (1): 1–6, doi : 10.1016/j.dam.2006.05.004 , MR 2281351.

Внешние ссылки

Вайсштейн, Эрик В. «Смешанный граф». MathWorld .