
_START_ARTICLE_
混合图
_START_PARAGRAPH_
混合图（mixed graph）G = (V, E, A)是由顶点 （节点）的集合V、无向边的集合E和有向边的集合A所组成的数学对象。
_START_SECTION_
定义和标识
_START_PARAGRAPH_
考虑一对相邻的顶点。有向边，是一个有方向的边，其可以表示为 或  (即该有向边为由指向)。 同样地，无向边，是一个没有方向的边，其可以表示为 或 。_NEWLINE_在以下给出的应用实例中，我们不考虑混合图中包含自环或多重边的情况。_NEWLINE_混合图或混合循环中的循环，是由有向边在混合图中构成的循环。如果不能从有向边形成循环，则认为混合图的方向是无环的。如果一个混合图的所有方向都是无环的，我们称它为有向无环图。
_START_SECTION_
着色
_START_PARAGRAPH_
混合图着色可以看作是使用k种不同颜色(其中k是正整数)对混合图顶点进行标记或赋值。通过边连接的两端顶点必须颜色不同。颜色可以由1到k的数字表示，对于有向边，箭头后端的颜色对应数字必须小于箭头前端的颜色对应数字。
_START_SECTION_
实例
_START_PARAGRAPH_
例如右图，我们可用于混合图的k着色方式为。由于  和  之间有边连接，他们必须用不同颜色进行标记(如将 和  分别标记为1和2)。  和之间为有向边连接，因此箭头后端的颜色标记必须小于箭头前段的颜色标记。
_START_SECTION_
强着色和弱着色
_START_PARAGRAPH_
混合图的k着色方式是一个函数。_NEWLINE_ _NEWLINE_其中，当（无向边）时，当（有向边）时。再回到实例中，这意味着我们可以将有向边的前端和后端均标记为正整数2。
_START_SECTION_
存在
_START_PARAGRAPH_
假设混合图为G，能否做到将其完全着色是不确定的。为了使混合图有一个k着色方式，图中不能包含任何有向循环。 如果这样的k着色方式存在，那么我们为了给整个图着色的最小着色数（k值）可记为。 我们可以通过构建k的多项式函数来计算合理的k着色方式的数量，其被称为图G的着色多项式（可用无向图的着色多项式来类比），其定义式为。
_START_SECTION_
调度问题
_START_PARAGRAPH_
混合图可用于对车间调度问题进行建模，例如在一定的时间限制下执行一系列任务的问题。在这类问题中，无向边可用于设定两个任务不兼容(不能同时执行)的约束。有向边可用于优先级约束，即其中一个任务必须先于另一个任务执行。用这种方法从调度问题的角度定义的图称为析取图。混合图着色问题可用于规划执行所有任务的最小长度。
_START_SECTION_
贝叶斯推理
_START_PARAGRAPH_
混合图也用作贝叶斯推理的概率图模型。下文中无环混合图(没有有向边循环的图)也称为链图。这些图的有向边用来表示两个事件之间的因果关系，其中第一个事件的结果影响第二个事件的概率。相反的是，无向边则表示两个事件之间的非因果关系。链图的无向子图的连通分量称为链。一个链图可以通过构造它的道德图从而转化为一个无向图，链图可以在其含有同一链的顶点对之间添加无向边，然后忽略有向边的方向从而形成无向图。