В теории графов смешанный граф G = ( V , E , A ) — это граф , состоящий из набора вершин V , набора (неориентированных) ребер E и набора направленных ребер (или дуг) A. [1]
Рассмотрим соседние вершины . Направленное ребро , называемое дугой , представляет собой ребро с ориентацией и может обозначаться как или (обратите внимание, что это хвост и голова дуги). [2] Кроме того, ненаправленное ребро или ребро — это ребро без ориентации и может обозначаться как или . [2]
В нашем примере мы не будем рассматривать петли или кратные ребра смешанных графов.
Ход в смешанном графе — это последовательность вершин и ребер/дуг такая, что для каждого индекса либо является ребром графа, либо является дугой графа. Этот обход является путем , если он не повторяет ни одного ребра, дуги или вершины, за исключением, возможно, первой и последней вершин. Маршрут называется замкнутым, если его первая и последняя вершины совпадают, а замкнутый путь является циклом . Смешанный граф называется ациклическим, если он не содержит циклов.
Раскраску смешанного графа можно рассматривать как маркировку или присвоение k различных цветов (где k — положительное целое число) вершинам смешанного графа. [3] Вершинам, соединенным ребром, необходимо назначить разные цвета. Цвета могут быть представлены числами от 1 до k , а для направленной дуги хвост дуги должен быть окрашен в меньшее число, чем начало дуги. [3]
Например, рассмотрим рисунок справа. Наши доступные k -цвета для раскраски смешанного графа: {1, 2, 3}. Поскольку u и v соединены ребром, они должны иметь разные цвета или маркировку ( u и v имеют метки 1 и 2 соответственно). У нас также есть дуга от v до w . Поскольку ориентация задает порядок, мы должны пометить хвост ( v ) меньшим цветом (или целым числом из нашего набора), чем начало ( w ) нашей дуги.
(Сильная) правильная k -раскраска смешанного графа — это функция c : V → [ k ] где [ k ] := {1, 2, …, k } такая, что c ( u ) ≠ c ( v ) , если uv ∈ E и c ( ты ) < c ( v ) если . [1]
Можно применить более слабое условие к нашим дугам, и мы можем рассматривать слабую собственную k -раскраску смешанного графа как функцию c : V → [ k ], где [ k ] := {1, 2, …, k } , такую что c ( ты ) ≠ c ( v ) если uv ∈ E и c ( ты ) ≤ c ( v ) если . [1] Возвращаясь к нашему примеру, это означает, что мы можем пометить как начало, так и хвост ( v , w ) положительным целым числом 2.
Раскраска может существовать, а может и не существовать для смешанного графа. Чтобы смешанный граф имел 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 соответственно. Из предложений, приведенных в Beck et al. В [4] мы получаем следующие уравнения для вычисления хроматического многочлена смешанного графа: [5]
Смешанные графы могут использоваться для моделирования задач планирования цеха , в которых необходимо выполнить набор задач с учетом определенных временных ограничений. В задачах такого рода ненаправленные ребра можно использовать для моделирования ограничения, заключающегося в несовместимости двух задач (их нельзя выполнять одновременно). Направленные ребра можно использовать для моделирования ограничений приоритета, при которых одна задача должна выполняться раньше другой. Граф, определенный таким образом из задачи планирования, называется дизъюнктивным графом . Задача о раскраске смешанного графа может быть использована для нахождения расписания минимальной длины для выполнения всех задач. [2]
Смешанные графы также используются в качестве графических моделей для байесовского вывода . В этом контексте ациклический смешанный граф (без циклов направленных ребер) также называется цепным графом . Направленные ребра этих графов используются для обозначения причинно-следственной связи между двумя событиями, при которой исход первого события влияет на вероятность второго события. Вместо этого ненаправленные края указывают на непричинную корреляцию между двумя событиями. Компонента связности неориентированного подграфа цепного графа называется цепью. Цепной граф можно преобразовать в неориентированный граф, построив его моральный граф , неориентированный граф, сформированный из цепного графа путем добавления неориентированных ребер между парами вершин, которые имеют исходящие ребра в одну и ту же цепь, а затем забывания ориентации направленных ребер. . [6]
![{\displaystyle [u,v]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c790b8b85a510362484e22edb7d03d54656ee4e1)
