Перегляд вихідного коду сторінки Змішаний граф

'''Змі́шаний граф''' G = (V, E, A)&nbsp;— математичний об'єкт, що складається з набору [[Вершина (теорія графів)|вершин]] (або вузлів) V, набору (неорієнтованих) [[Словник термінів теорії графів|ребер]] E і набору спрямованих ребер (або дуг) A<ref name=":0">{{Стаття|url=https://doi.org/10.1007/s00373-013-1381-1|author=Matthias Beck, Daniel Blado, Joseph Crawford, Taïna Jean-Louis, Michael Young|title=On Weak Chromatic Polynomials of Mixed Graphs|date=2015-01-01|language=en|видання=Graphs and Combinatorics|том=31|issue=1|pages=91–98|issn=1435-5914|doi=10.1007/s00373-013-1381-1}}</ref>.

== Визначення та позначення ==
{{Див. також|Граф (математика)}}
[[Файл:Mixed_Graph_Example.jpg|альт=Пример смешанного графа|міні|Приклад змішаного графа]]
Розглянемо сусідні вершини <math>u, v \in V</math>. '''Орієнто́ваним ребро́м''', називають '''дугу''', ребро з орієнтацією, яке позначають <math>{\displaystyle {\overrightarrow {uv}}}</math> або <math> {\displaystyle (u,v)}</math> (варто зауважити, що <math>u</math> це хвіст, а <math>v</math> це голова дуги)<ref name=":1">{{Стаття|url=http://www.sciencedirect.com/science/article/pii/S0166218X06002113|author=B. Ries|title=Coloring some classes of mixed graphs|date=2007-01-01|language=en|видання=Discrete Applied Mathematics|том=155|issue=1|pages=1–6|issn=0166-218X|doi=10.1016/j.dam.2006.05.004|accessdate=17 травня 2022|archivedate=17 травня 2022|archiveurl=https://web.archive.org/web/20220517135427/https://www.sciencedirect.com/science/article/pii/S0166218X06002113}}</ref>. '''Неорієнто́ваним ребро́м''' або просто '''ребро́м''', називають ребро без орієнтації і позначають <math> {\displaystyle uv}</math> або <math>[u, v]</math><ref name=":1" />.
{{Див. також|Кратні ребра|Петля (теорія графів)}}

У розглянутому прикладі застосування не буде циклів або кратних ребер змішаних графів.

[[Маршрут (теорія графів)|'''Маршрут''']] у змішаному графі&nbsp;— це послідовність <math>{\displaystyle v_ {0}, c_ {1}, v_ {1}, c_ {2}, v_ {2}, \dots, c_ {k}, v_ {k}}</math> вершин і ребер/дуг, така що для всіх індексів <math>{\displaystyle i}</math>, елемент <math>{\displaystyle c_ {i} = v_{i} v_{i + 1}}</math>є ребром графа або елемент <math>{\displaystyle c_{i} = {\overrightarrow {v_{i} v_{i + 1}}}} </math> є дугою графа. Цей маршрут є [[Шлях (теорія графів)|'''шляхом''']], якщо в ньому не повторюються ребра, дуги чи вершини, крім, можливо, першої й останньої вершин. Шлях є '''замкнутим''', якщо його перша й остання вершини збігаються, і замкнутий шлях є [[Цикл (теорія графів)|'''циклом''']], якщо в ньому не повторюються вершини, крім першої й останньої. Змішаний граф є '''ациклічним''', якщо він не містить циклу.

== Розфарбовування ==
{{Див. також|Розфарбовування графів}}
[[Файл:ColoredMixed.png|альт=Пример смешанного графика|міні|Приклад змішаного графа]]
Розфарбовування змішаного графа можна розглядати як маркування або присвоєння <math>k</math> різних кольорів (де <math>k</math>&nbsp;— додатне ціле число) вершинам змішаного графа<ref name=":2">{{Стаття|url=https://doi.org/10.1007/BF01194253|author=Pierre Hansen, Julio Kuplinsky, Dominique de Werra|title=Mixed graph colorings|date=1997-02-01|language=en|видання=Mathematical Methods of Operations Research|том=45|issue=1|pages=145–160|issn=1432-5217|doi=10.1007/BF01194253}}</ref>. Вершинам, з'єднаним ребром, слід призначити різні кольори. Кольори можна подати числами від 1 до <math>k</math>, а для спрямованої дуги хвіст дуги має бути позначеним числом меншим, ніж голова дуги<ref name=":2" />.

=== Приклад ===
Наприклад, розглянемо фігуру праворуч. Доступні нам k-кольори для фарбування нашого змішаного графа: <math>{\displaystyle \{1,2,3 \}}</math>. Оскільки <math>{\displaystyle u}</math> і <math>{\displaystyle v}</math> пов'язані ребром, вони повинні мати різні кольори або числа (<math>{\displaystyle u}</math> і <math>{\displaystyle v}</math> позначені 1 і 2 відповідно). У нас також є дуга від <math>{\displaystyle v}</math> до <math>{\displaystyle w}</math>. Оскільки ми маємо справу з дугою, де орієнтація призначає порядок чисел, ми повинні позначити хвіст (<math>{\displaystyle v}</math>) меншим кольором (або цілим числом з нашого набору), ніж голову (<math>{\displaystyle w}</math>) дуги.

=== Сильне і слабке розфарбування ===
('''Сильне) власне''' <math>k</math>'''-розфарбування''' змішаного графа є функцією

<math>{\displaystyle c: V \rightarrow [k]}</math>, де <math>[k]: = {1,2, \dots, k}</math> такою, що <math>{\displaystyle c (u) \neq c (v)} </math>, якщо <math>{\displaystyle uv \in E} </math>, і <math>{\displaystyle c ( u) <c (v)}</math>, якщо <math>{\displaystyle {\overrightarrow {uv}} \in A}</math>.<ref name=":0"/>

Можна послабити умову на дуги. Тоді ми можемо вважати '''слабке власне k-розфарбування''' змішаного графа функцією

<math>{\displaystyle c: V \rightarrow [k]}</math>, де <math>[k]: = {1,2, \dots, k}</math> такою, що <math>{\displaystyle c (u) \neq c (v)} </math>, якщо <math>{\displaystyle uv \in E} </math>, і <math>{\displaystyle c ( u)\leq c (v)}</math>, якщо <math>{\displaystyle {\overrightarrow {uv}} \in A}</math>.<ref name=":0"/>

Повертаючись до прикладу, це означає, що ми можемо позначити голову і хвіст <math>(v, w)</math> додатним цілим числом 2.

=== Існування ===
Для змішаного графа розфарбування може існувати чи не існувати. Для того, щоб змішаний граф мав <math>k</math>-розфарбування, він не повинен містити ніяких спрямованих циклів<ref name=":1"/>. Якщо таке <math>k</math>-розфарбування існує, найменше <math>k</math>, необхідне для того, щоб правильно розфарбувати граф, називають його '''[[Хроматичне число|хроматичним числом]]''', що позначається <math>{\displaystyle \chi (G)}</math><ref name=":1" />. Кількість власних <math>k</math>-розфарбувань можна порахувати як поліноміальну функцію від <math>k</math>. Її називають '''хроматичним поліномом''' графа <math>G
</math> (за аналогією з хроматичним поліномом неорієнтованих графів) і позначають як <math>{\displaystyle \chi _ {G} (k)}</math><ref name=":0"/>.

=== Обчислення слабких хроматичних поліномів ===
Для обчислення слабких хроматичних поліномів змішаних графів можна використати [[Многочлен Татта|формулу видалення-стягування]]. Цей метод включає видалення ребра або дуги і стягування (або об'єднання) вершин, що [[Інцидентність (геометрія)|інцидентних]] цьому ребру (або дузу), з утворенням однієї вершини<ref name=":0"/>. Після видалення ребра <math>e</math> зі змішаного графа <math>G = (V, E, A)</math> отримуємо змішаний граф <math>(V, E-e, A)</math><ref name=":0" />. Це видалення ребра <math>e</math> можна позначити як <math>G-e</math>. Аналогічно, видаляючи дугу <math>a</math> зі змішаного графа, отримуємо <math>(V, E, A-a)</math>, де ми можемо позначити видалення <math>a</math> as <math>G-a</math><ref name=":0" />. Крім того, ми можемо позначити скорочення <math>e</math> і <math>a</math> як <math>G / e</math> і <math>G / a</math>, відповідно<ref name=":0" />. З наведених тверджень,<ref name=":0" /> отримуємо такі рівняння для обчислення хроматичного полінома змішаного графа:

# <math>{\displaystyle \Chi _ {G} (k) = \chi _ {G-e} (k) - \chi _ {G / e} (k)}</math><ref name=":0"/>
# <math>{\displaystyle \chi _ {G} (k) = \chi _ {G-a} (k) + \chi _ {G / a} (k) - \chi _ {G_ {a}} (k)} </math><ref name=":0" />

== Застосування ==

=== Задача планування ===
Змішані графи можна використати для моделювання [[Теорія розкладів|задач планування робіт]], у яких має виконуватися сукупність робіт з урахуванням певних часових обмежень. У задачах цього типу неспрямовані ребра можна використати для моделювання несумісності двох робіт (вони не можуть виконуватися одночасно). Спрямовані ребра можна використати для моделювання обмеження пріоритету, за яким одна робота має бути виконаною перед іншою. Граф, визначений у такий спосіб на основі задачі планування, називають '''{{Нп|Диз'юнктивний граф|диз'юнктивним графом|en|Disjunctive graph}}'''. Задачу розфарбовування змішаного графа можна використати для знаходження розкладу найменшої довжини для виконання всіх робіт<ref name=":1"/>.

=== Баєсове висновування ===
{{Див. також|Баєсове висновування}}
Змішані графи також використовують як [[Графова модель|графічні моделі]] [[Баєсове висновування|байєсового висновування]]. У цьому контексті ациклічний змішаний граф (без циклів спрямованих ребер) також називають '''ланцюговим графом'''. Спрямовані ребра цих графів використовують для вказання причинного зв'язку між двома подіями, в якому результат першої події впливає на ймовірність другої події. Неспрямовані ребра вказують на непричинну кореляцію між двома подіями. Зв'язну компоненту неорієнтованого підграфа ланцюгового графа називають '''ланцюгом'''. Ланцюговий граф можна перетворити на неорієнтований граф, побудувавши його [[моральний граф]], неорієнтований граф, сформований із ланцюгового графа додаванням неорієнтованих ребер між парами вершин, які мають вихідні ребра до одного ланцюга, з відкиданням орієнтації спрямованих ребер<ref>{{Книга
|посилання = https://books.google.com/books?id=G_4E_w_wJzcC&pg=PA27
|автор = Robert G. Cowell, Philip Dawid, Steffen L. Lauritzen, David J. Spiegelhalter
|заголовок = Probabilistic Networks and Expert Systems: Exact Computational Methods for Bayesian Networks
|рік = 2007-07-16
|видавництво = Springer Science & Business Media
|сторінок = 340
|ISBN = 978-0-387-71823-1
|назва = 
|archivedate = 12 червня 2020
|archiveurl = https://web.archive.org/web/20200612040111/https://books.google.com/books?id=G_4E_w_wJzcC&pg=PA27
}}</ref>.

== Примітки ==
{{примітки|2}}

== Посилання ==
* {{mathworld|id=MixedGraph|title=Змішаний граф}}
{{Бібліоінформація}}
[[Категорія:Об'єкти теорії графів]]