图的边覆盖集、边独立集

Published on 2016 - 06 - 25

边覆盖集

边覆盖点、边覆盖集、边覆盖数

覆盖与边覆盖集:设无向图为G(V,E),边的集合E*⊆E,若对于∀v∈V,∃e∈E*,使得:v与e相关联,则称e覆盖v,并称E*为边覆盖集(Edge Covering Set),或简称边覆盖。

在图8(a)中,取E*={e1,e4,e7},则E*就是图G的一个边覆盖集,因为图G中每个顶点都被E*中某条边“覆盖”住了。

通俗地讲,所谓边覆盖集E*,就是G中所有的顶点都是E*中某条边的邻接顶点(边覆盖顶点)。

注意:在无向图中存在用尽可能少的边去“覆盖”住所有顶点的问题,所以边覆盖集有极小和最小的概念。最大边覆盖集的概念是没有意义的,因为对任何一个无向图G(V,E),取E*=E,总是满足边覆盖集的定义。

极小边覆盖:若边覆盖E*的任何真子集都不是边覆盖,则称E*是极小边覆盖。

最小边覆盖:边数最少的边覆盖集称为最小边覆盖。

边覆盖数(Edge Covering Number):最小的边覆盖所含的边数称为边覆盖数,记作α1(G),或简记为α1。

在图8(a)中,{e1,e4,e7}和{e2,e5,e6,e7}都是极小边覆盖,{e1,e4,e7}是最小边覆盖,因此α1=3。

在图8(b)中,{e1,e3,e6}和{e2,e4,e8}都是极小边覆盖,也都是最小边覆盖,因此α1=3。

例5 应用边覆盖集安排ACM竞赛题目的讲解

某高校举办了一次全校ACM程序设计个人赛,共出了8道题目(P1~P8)。赛后组委会要求比赛前10名学生(s1~s10)来讲解题目,并要求他们每人选择两道题目来讲解,比如s1学生准备讲解P2和P8;s2学生准备讲解P6和P8等。要讲解这8道题目至少需要多少名学生。

以题目P1~P8为顶点,如果某学生sk准备讲解题目Pi和Pj,则在顶点Pi和Pj之间连一条边sk,这样构造的无向图如图9所示。本题要求解的是讲解这8道题目至少需要多少名学生,转换成求图9的最小边覆盖集。在本题中,边sk“覆盖住”顶点Pi含义是学生sk讲解题目Pi。图9中粗线所示的边构成了一个最小边覆盖集,共5条边,因此至少需要5名学生来讲解,很明显某些学生只能讲一道题目。

边独立集(匹配)

边独立集、边独立数

边独立集(匹配):设无向图为G(V,E),边的集合E*⊆E,若E*中任何两条边均不相邻,则称E*为G的边独立集(Edge Independent Set),也称E*为G的匹配(Matching)。所谓任何两条边均不相邻,通俗地讲,就是任何两条边都没有公共顶点。

例如,在图10(a)中,取E*={e1,e4,e7},则E*就是图G1的一个边独立集,因为E*中每两条边都没有公共顶点。

图7.10 边独立集

注意:在无向图中存在将尽可能多的、相互独立的边包含到边的集合E*中的问题,所以边独立集有极大和最大的概念。最小边独立集的概念是没有意义的,因为对任何一个无向图G(V,E),取E*=(空集),总是满足边独立集的定义。

极大匹配:若在E*中加入任意一条边所得到的集合都不匹配,则称E*为极大匹配。

最大匹配:边数最多的匹配称为最大匹配。

边独立数(Edge Independent Number):最大匹配的边数称为边独立数或匹配数,记作β1(G),简记为β1。

在图10(a)中,{e2,e6}、{e3,e5}和{e1,e4,e7}都是极大匹配,{e1,e4,e7}是最大匹配,因此β1=3。

在图10(b)中,{e1,e3}、{e2,e4}和{e4,e7}都是极大匹配,也都是最大匹配,因此β1=2。

以下几个概念都是针对无向图G(V,E)中一个给定的匹配M而言的。

在无向图G中,若边(u,v)∈M,则称顶点u与v被M所匹配

盖点与未盖点:设v是图G的一个顶点,如果v与M中的某条边关联,则称v为M的盖点(有的文献上也称为M饱和点)。如果v不与任意一条属于匹配M的边相关联,则称v是匹配M的未盖点(相应地,有的文献上也称为非M饱和点)。所谓盖点,就是被匹配中的边盖住了,而未盖点就是没有被匹配M中的边“盖住”的顶点。

例如,在图11(a)所示的无向图中,取定M={e1,e4},M中的边用粗线标明,则顶点v1与v2被M所匹配;v1、v2、v3和v4是M的盖点,v5和v6是M的未盖点。

而在图11(b)中,取定M={e1,e4,e7},则G中不存在未盖点。

例6 飞行员搭配问题1——最大匹配问题

飞行大队有若干个来自各地的飞行员,专门驾驶一种型号的飞机,每架飞机有两个飞行员。由于种种原因,例如互相配合的问题,有些飞行员不能在同一架飞机上飞行,问如何搭配飞行员,才能使出航的飞机最多。

为简单起见,设有10个飞行员,图12中的v1,v2,…,v10就代表这10个飞行员。如果两个人可以同机飞行,就在他们之间连一条线,否则就不连。

图12中的3条粗线代表一种搭配方案。由于一个飞行员不能同时派往两架飞机,因此任何两条粗线不能有公共端点。因此该问题就转化为:如何找一个包含最多边的匹配,这个问题就是图的最大匹配问题。

最大边独立集(最大匹配)与最小边覆盖集之间的联系

从最大匹配出发可以构造最小边覆盖,从最小边覆盖出发也可以构造最大匹配。通常,可以按如下方法进行。

  1. 从最大匹配出发,通过增加关联未盖点的边获得最小边覆盖。
  2. 从最小边覆盖出发,通过移去相邻的一条边获得最大匹配。

任取一个最大匹配,例如在图13(a)中,取匹配M={e2,e4},M中的边用粗线标明,则M∪{e6}、M∪{e8}、M∪{e7}都是图的最小边覆盖,其中顶点v5是M的未盖点,而边e6、e8、e7都与v5关联。

任取一个最小边覆盖,例如在图13(b)中,取最小边覆盖W={e1,e3,e6},W中的边用粗线标明,从中移去一条相邻的边,如去掉e6,则{e1,e3}是最大匹配;去掉e3,则{e1,e6}是最大匹配。

定理4 设无向图G的顶点个数为n,且G中无孤立点。

  1. 设M为G的一个最大匹配,对于G中M的每个未盖点v,选取一条与v关联的边所组
  2. 设W1为G的最小边覆盖,若G中存在相邻的边就移去其中的一条,设移去的边集为N1,则M1=W1-N1为G中一个最大匹配。
  3. G中边覆盖数α1与匹配数β1,满足:α1+β1=n,即:边覆盖数+边独立数=n。

参考文档