2.6　独立集与匹配

设X是V的一个子集，若X中任意两个顶点在G中均不相邻，则称X为G的独立集。若X是G的独立集，但任意增加一个顶点后就破坏它的独立性，则称这个独立集X为极大独立集。G的一个独立集X称为G的最大独立集，如果G不包含满足|Y|>|X|的独立集。G的最大独立集的基数称为G的独立数，记为α（G）。图2-17给出了彼得森图的极大和最大独立集。

图2-17　彼得森图的极大和最大独立集

匹配问题是运筹学的重要问题之一，也是图论的重要内容。它在所谓“人员分配”和“最优分配”等实际问题中有着重要的作用。

设M是E的一个子集，它的元素是G中的边，并且这些边中的任意两个均不相邻，则称M为G的匹配。若顶点v与匹配M中的某条边关联，则称v是M饱和的，否则称v是M非饱和的。若G的每个顶点均为M饱和的，则称M为G的完美匹配。若匹配M不可能是图G的任何一个匹配的真子图，则称M为G的极大匹配。若G没有另外的匹配M'，使得>，则M称为G的最大匹配。显然每个完美匹配都是最大匹配。图2-18给出五棱柱的一个极大匹配和一个完美匹配。

图2-18　五棱柱的极大匹配和完美匹配

定义2-7　设M是G的一个匹配，G的M交错路是指其边在M和E（G）\M中交替出现的路。如果G的一条M交错路的起点和终点都是M非饱和的，则称其为一条M可扩路或M增广路。

定理2-4　（Berge，1957）图G的匹配M是最大匹配的充分必要条件是G中不存在M可扩路。

定理2-5　（Tutte，1947）图G有完美匹配的充分必要条件是对∀S⊆V（G），O（G\S）≤。

关于二部图的匹配，有下面定理。

定理2-6　（Hall，1935）设G是具有二划分（X，Y）的二部图，则G有饱和X的匹配当且仅当对∀S⊆X，≥，其中N（S）表示S中所有点的邻点组成的集合。