混合图(mixed graph)G = (V, E, A)是由顶点 (节点)的集合V、无向边的集合E和有向边的集合A所组成的数学对象[1]

定义和标识

编辑
 
混合图的实例

考虑一对相邻的顶点  有向边,是一个有方向的边,其可以表示为    (即该有向边为由 指向 )。[2] 同样地,无向边,是一个没有方向的边,其可以表示为   [2]

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

混合图或混合循环中的循环,是由有向边在混合图中构成的循环。[1]如果不能从有向边形成循环,则认为混合图的方向是无环的。[1]如果一个混合图的所有方向都是无环的,我们称它为有向无环图[1]

着色

编辑
 
混合图实例

混合图着色可以看作是使用k种不同颜色(其中k是正整数)对混合图顶点进行标记或赋值[3]通过连接的两端顶点必须颜色不同。颜色可以由1到k的数字表示,对于有向边,箭头后端的颜色对应数字必须小于箭头前端的颜色对应数字。[3]

实例

编辑

例如右图,我们可用于混合图的k着色方式为  。由于    之间有边连接,他们必须用不同颜色进行标记(如将   分别标记为1和2)。   之间为有向边连接,因此箭头后端 的颜色标记必须小于箭头前段 的颜色标记。

强着色和弱着色

编辑

混合图的k着色方式是一个函数。

 

其中 ,当 (无向边)时 ,当 (有向边)时 [1]再回到实例中,这意味着我们可以将有向边的前端和后端  均标记为正整数2。

存在

编辑

假设混合图为G,能否做到将其完全着色是不确定的。为了使混合图有一个k着色方式,图中不能包含任何有向循环。[2] 如果这样的k着色方式存在,那么我们为了给整个图着色的最小着色数(k值)可记为 [2] 我们可以通过构建k的多项式函数来计算合理的k着色方式的数量,其被称为图G的着色多项式(可用无向图的着色多项式来类比),其定义式为 [1]

计算弱色多项式

编辑

塔特多项式中的删除–收缩方法可用于计算弱色多项式的混合图。这个方法涉及删除(或移除)有向或无向边,合并(或关联)与该无向或有向边相连的其余顶点形成一个顶点。[4] 在删除无向边 之后,从之前的混合图   可得到新的混合图  [4] 可将删除无向边 之后剩余的边表示为  。类似地,在删除有向边 之后,将剩余的边表示为 ,可获得新的混合图 [4] 同样,我们可以将合并  分别表示为  [4] 根据以上给出的条件,我们得到以下方程来计算混合图的着色多项式:[4]

  1.  ,[5]
  2.  .[5]

应用

编辑

调度问题

编辑

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

贝叶斯推理

编辑

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

注释

编辑

参考文献

编辑

外部链接

编辑