查看“︁混合图”︁的源代码

{{NoteTA
|G1 = Math
|1=zh-cn:數學對象;zh-tw:數學物件;
}}
'''混合图（mixed graph）'''''G'' = (''V'', ''E'', ''A'')是由[[顶点_(图论)|顶点 （节点）]]的集合V、无向边的集合E和有向边的集合A所组成的[[数学对象]]。<ref name="BeckBladoCrawfordJeanLouisYoung">{{Harvard citation text|Beck|Blado|Crawford|Jean-Louis|2013|p=1}}</ref>

== 定义和标识 ==
[[File:Mixed_Graph_Example.jpg|缩略图|混合图的实例]]
考虑一对相邻的顶点 <math>u,v \in V</math>。'''有向边'''，是一个有[[有向邊|方向的边]]，其可以表示为 <math>\overrightarrow{uv}</math> 或 <math>(u,v)</math> (即该有向边为由<math>u</math>指向<math>v</math>)。<ref name="Ries">{{Harvard citation text|Ries|2007|p=1}}</ref> 同样地，'''无向边'''，是一个没有方向的边，其可以表示为 <math>uv</math> 或 <math>[u,v]</math>。<ref name="Ries" />

在以下给出的应用实例中，我们不考虑混合图中包含[[自环]]或[[多重边]]的情况。

混合图或[[混合循环]]中的循环，是由有向边在混合图中构成的循环。<ref name="BeckBladoCrawfordJeanLouisYoung">{{Harvard citation text|Beck|Blado|Crawford|Jean-Louis|2013|p=1}}</ref>如果不能从有向边形成循环，则认为混合图的方向是无环的。<ref name="BeckBladoCrawfordJeanLouisYoung" />如果一个混合图的所有方向都是无环的，我们称它为[[有向无环图]]。<ref name="BeckBladoCrawfordJeanLouisYoung" />

== 着色 ==
[[File:ColoredMixed.png|缩略图|混合图实例]]
混合图着色可以看作是使用k种不同颜色(其中k是正整数)对混合图[[顶点 (图论)|顶点]]进行标记或[[赋值]]。<ref name="HansenKuplinskydeWerra">{{Harvard citation text|Hansen|Kuplinsky|de Werra|1997|p=1}}</ref>通过[[邊_(圖論)|边]]连接的两端顶点必须颜色不同。颜色可以由1到k的数字表示，对于有向边，箭头后端的颜色对应数字必须小于箭头前端的颜色对应数字。<ref name="HansenKuplinskydeWerra" />

=== 实例 ===
例如右图，我们可用于混合图的k着色方式为 <math>\{1,2,3\}</math>。由于 <math>u</math> 和 <math>v</math> 之间有边连接，他们必须用不同颜色进行标记(如将<math>u</math> 和 <math>v</math> 分别标记为1和2)。 <math>v</math> 和<math>w</math>之间为有向边连接，因此箭头后端<math>v</math>的颜色标记必须小于箭头前段<math>w</math>的颜色标记。

=== 强着色和弱着色 ===
混合图的k着色方式是一个函数。

<math>c : V \rightarrow [k] </math> 

其中<math> [k] = {1,2, \dots , k} </math>，当<math>uv \in E </math>（无向边）时<math>c(u) \neq c(v)</math>，当<math> \overrightarrow{uv} \in A </math>（有向边）时<math> c(u) \leq c(v) </math>。<ref name="BeckBladoCrawfordJeanLouisYoung">{{Harvard citation text|Beck|Blado|Crawford|Jean-Louis|2013|p=1}}</ref>再回到实例中，这意味着我们可以将有向边的前端和后端 <math>(v,w)</math>均标记为正整数2。

=== 存在 ===
假设混合图为G，能否做到将其完全着色是不确定的。为了使混合图有一个k着色方式，图中不能包含任何有向循环。<ref name="Ries">{{Harvard citation text|Ries|2007|p=1}}</ref> 如果这样的k着色方式存在，那么我们为了给整个图着色的最小'''着色数'''（k值）可记为<math>\chi(G)</math>。<ref name="Ries" /> 我们可以通过构建k的多项式函数来计算合理的k着色方式的数量，其被称为图G的'''着色多项式'''（可用无向图的[[着色多项式]]来类比），其定义式为<math>\chi_G(k)</math>。<ref name="BeckBladoCrawfordJeanLouisYoung">{{Harvard citation text|Beck|Blado|Crawford|Jean-Louis|2013|p=1}}</ref>

=== 计算弱色多项式 ===
[[塔特多项式]]中的删除–收缩方法可用于计算弱色多项式的混合图。这个方法涉及删除(或移除)有向或无向边，合并（或关联）与该无向或有向边相连的其余顶点形成一个顶点。<ref name="BeckBladoCrawfordJeanLouisYoung_a">{{Harvard citation text|Beck|Blado|Crawford|Jean-Louis|2013|p=4}}</ref> 在删除无向边<math>e</math>之后，从之前的混合图 <math>G=(V,E,A)</math> 可得到新的混合图 <math>(V, E-e, A)</math>。<ref name="BeckBladoCrawfordJeanLouisYoung_a" /> 可将删除无向边<math>e</math>之后剩余的边表示为 <math>G-e</math>。类似地，在删除有向边<math>a</math>之后，将剩余的边表示为<math>G-a</math>，可获得新的混合图<math>(V, E, A-a)</math>。<ref name="BeckBladoCrawfordJeanLouisYoung_a" /> 同样，我们可以将合并<math>e</math>和<math>a</math>分别表示为<math>G/e</math> 和 <math>G/a</math>。<ref name="BeckBladoCrawfordJeanLouisYoung_a" /> 根据以上给出的条件，我们得到以下方程来计算混合图的着色多项式：<ref name="BeckBladoCrawfordJeanLouisYoung_a" />

# <math>\chi_G(k) = \chi_{G-e}(k) - \chi_{G/e}(k)</math>,<ref name="BeckBladoCrawfordJeanLouisYoung_b">{{Harvard citation text|Beck|Blado|Crawford|Jean-Louis|2013|p=5}}</ref>
# <math>\chi_G(k) = \chi_{G-a}(k) + \chi_{G/a}(k) - \chi_{G_a}(k)</math>.<ref name="BeckBladoCrawfordJeanLouisYoung_b" />

== 应用 ==

=== 调度问题 ===
混合图可用于对[[车间调度问题]]进行建模，例如在一定的时间限制下执行一系列任务的问题。在这类问题中，无向边可用于设定两个任务不兼容(不能同时执行)的约束。有向边可用于优先级约束，即其中一个任务必须先于另一个任务执行。用这种方法从调度问题的角度定义的图称为[[析取图]]。混合图着色问题可用于规划执行所有任务的最小长度。<ref name="Ries">{{Harvard citation text|Ries|2007|p=1}}</ref>

=== 贝叶斯推理 ===
混合图也用作[[贝叶斯推理]]的[[概率图模型]]。下文中无环混合图(没有有向边循环的图)也称为'''链图'''。这些图的有向边用来表示两个事件之间的因果关系，其中第一个事件的结果影响第二个事件的概率。相反的是，无向边则表示两个事件之间的非因果关系。链图的无向子图的连通分量称为链。一个链图可以通过构造它的[[道德图]]从而转化为一个无向图，链图可以在其含有同一链的顶点对之间添加无向边，然后忽略有向边的方向从而形成无向图。

== 注释 ==
{{Reflist|30em}}

== 参考文献 ==

* {{Citation|last=Beck|first=M.|last2=Blado|first2=D.|last3=Crawford|first3=J.|last4=Jean-Louis|first4=T.|last5=Young|first5=M.|doi=10.1007/s00373-013-1381-1|journal=[[Graphs and Combinatorics]]|title=On weak chromatic polynomials of mixed graphs|year=2013|arxiv=1210.4634}}.
* {{Citation|last=Cowell|first=Robert G.|last2=Dawid|first2=A. Philip|author2-link=Philip Dawid|last3=Lauritzen|first3=Steffen L.|author3-link=Steffen Lauritzen|last4=Spiegelhalter|first4=David J.|author4-link=David Spiegelhalter|title=Probabilistic Networks and Expert Systems: Exact Computational Methods for Bayesian Networks|publisher=Springer-Verlag New York|year=1999|isbn=0-387-98767-3|page=27|url=https://books.google.com/books?id=G_4E_w_wJzcC&pg=PA27|doi=10.1007/0-387-22630-3|accessdate=2019-05-21|archive-date=2020-06-12|archive-url=https://web.archive.org/web/20200612040111/https://books.google.com/books?id=G_4E_w_wJzcC&pg=PA27|dead-url=no}}
* {{Citation|last=Hansen|first=Pierre|last2=Kuplinsky|first2=Julio|last3=de Werra|first3=Dominique|doi=10.1007/BF01194253|number=1|journal=Mathematical Methods of Operations Research|mr=1435900|pages=145–160|title=Mixed graph colorings|volume=45|year=1997}}.
* {{Citation|last=Ries|first=B.|doi=10.1016/j.dam.2006.05.004|number=1|journal=[[Discrete Applied Mathematics]]|mr=2281351|pages=1–6|title=Coloring some classes of mixed graphs|volume=155|year=2007}}.

== 外部链接 ==

* {{MathWorld|title=Mixed Graph}}
[[Category:图论]]
[[Category:有未审阅翻译的页面]]