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

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

Определения и обозначения [ править ]

Пример смешанного графа

Рассмотрим смежные вершины . Направленное ребро , называется дуга , ребро с ориентацией и может быть обозначен как или (заметим , что это хвост , а это голова дуги). ^[2] Кроме того, неориентированная кромка или кромка - это кромка без ориентации, которую можно обозначить как или . ^[2]${\ displaystyle u, v \ in V}$${\ displaystyle {\ overrightarrow {uv}}}$${\ Displaystyle (и, v)}$${\ displaystyle u}$${\ displaystyle v}$${\ displaystyle uv}$${\ Displaystyle [и, 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 - целое положительное число) вершинам смешанного графа. ^[3] Разные цвета должны быть присвоены вершинам, соединенным ребром. Цвета могут быть представлены числами от 1 до k , и для направленной дуги хвост дуги должен быть окрашен меньшим числом, чем голова дуги. ^[3]

Пример [ править ]

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

Сильная и слабая окраска [ править ]

(Сильный) собственно к -раскраске смешанного графа является функция

${\displaystyle c:V\rightarrow [k]}$где такое, что если и если . ^[1]${\displaystyle [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]}$где такое, что если и если . ^[1] Возвращаясь к нашему примеру, это означает, что мы можем пометить как начало, так и конец элемента положительным целым числом 2.${\displaystyle [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}$${\displaystyle (v,w)}$

Существование [ править ]

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

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

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

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

Приложения [ править ]

Проблема с расписанием [ править ]

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

Байесовский вывод [ править ]

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

Заметки [ править ]

Ссылки [ править ]

• Бек, М .; Blado, D .; Crawford, J .; Жан-Луи, Т .; Янг, М. (2013), «О слабых хроматических многочленах смешанных графов», Графы и комбинаторика , arXiv : 1210.4634 , doi : 10.1007 / s00373-013-1381-1.
• Коуэлл, Роберт Дж .; Давид, А. Филип ; Лауритцен, Штеффен Л .; Шпигельхальтер, Дэвид Дж. (1999), Вероятностные сети и экспертные системы: точные вычислительные методы для байесовских сетей , Springer-Verlag New York, стр. 27, DOI : 10.1007 / 0-387-22630-3 , ISBN 0-387-98767-3
• Хансен, Пьер; Куплинский, Хулио; де Werra, Доминик (1997), "Смешанные раскраска графов", Математические методы исследования операций , 45 (1): 145-160, DOI : 10.1007 / BF01194253 , МР  1435900.
• Раис, Б. (2007), "Раскраска некоторых классов смешанных графов", дискретная Прикладная математика , 155 (1): 1-6, DOI : 10.1016 / j.dam.2006.05.004 , MR  2281351.

Внешние ссылки [ править ]

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