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

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

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

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

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

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

А ходить в смешанном графе - это последовательность ${ 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]

Пример

Например, рассмотрим рисунок справа. Наши доступные 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]}$ куда ${ Displaystyle [к]: = {1,2, точки, k}}$ такой, что ${ Displaystyle с (и) neq с (v)}$ если ${ displaystyle uv in E}$ и ${ Displaystyle с (и) <с (v)}$ если ${ displaystyle { overrightarrow {uv}} in A}$.^[1]

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

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

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

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

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

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

1. ${ Displaystyle чи _ {G} (к) = чи _ {G-е} (к) - чи _ {G / e} (к)}$,^[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, Дои:10.1007 / s00373-013-1381-1.
• Коуэлл, Роберт Дж .; Давид, А. Филип; Лауритцен, Штеффен Л.; Шпигельхальтер, Дэвид Дж. (1999), Вероятностные сети и экспертные системы: точные вычислительные методы для байесовских сетей, Springer-Verlag New York, стр. 27, Дои:10.1007/0-387-22630-3, ISBN  0-387-98767-3
• Хансен, Пьер; Куплинский, Хулио; де Верра, Доминик (1997), «Смешанные раскраски графов», Математические методы исследования операций, 45 (1): 145–160, Дои:10.1007 / BF01194253, МИСТЕР  1435900.
• Райс, Б. (2007), "Раскраска некоторых классов смешанных графов", Дискретная прикладная математика, 155 (1): 1–6, Дои:10.1016 / j.dam.2006.05.004, МИСТЕР  2281351.

внешняя ссылка

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