离散数学第八章一些特殊的图知识点总结

图论部分 第八章、一些特殊的图 8.1 二部图

二部图：定义 设无向图 G=, 若能将V 划分成V1 和 V2 (V1?V2=V, V1?V2=?), 使得G中的每条边的两个端 点都一个属于V1, 另一个属于V2, 则称G为二部图, 记为, 称V1和V2为互补顶点子集.

完全二部图：又若G是简单图, 且V1中每个顶点都与V2中每个顶点相邻, 则称G为完全二部图, 记为Kr,s, 其中r=|V1|, s=|V2|. 注意: n 阶零图为二部图.

匹配：设G=,

匹配(边独立集): 任2条边均不相邻的边子集 极大匹配: 添加任一条边后都不再是匹配的匹配 最大匹配: 边数最多的匹配

匹配数: 最大匹配中的边数, 记为?1 例 下述3个图的匹配数 依次为3, 3, 4.

设M为G中一个匹配

vi与vj被M匹配: (vi,vj)?M v为M饱和点: M中有边与v关联 v为M非饱和点: M中没有边与v关联 M为完美匹配: G的每个顶点都是M饱和点

定理(Hall定理) 设二部图G=中，|V1|?|V2|. G中存 在从V1到V2的完备匹配当且仅当V1中任意k 个顶点至少与V2 中的k个顶点相邻(k=1,2,…,|V1|).

由Hall定理不难证明, 上一页图(2)没有完备匹配.

定理 设二部图G=中, 如果存在t?1, 使得V1中每个 顶点至少关联 t 条边, 而V2中每个顶点至多关联t条边，则G 中存在V1到V2的完备匹配.

Hall定理中的条件称为“相异性条件”, 第二个定理中的条件 称为 t 条件. 满足 t 条件的二部图一定满足相异性条件.

8.2 欧拉图

欧拉通路: 图中行遍所有顶点且恰好经过每条边一次的通路. 欧拉回路: 图中行遍所有顶点且恰好经过每条边一次的回路. 欧拉图: 有欧拉回路的图.

半欧拉图: 有欧拉通路而无欧拉回路的图. 几点说明：

上述定义对无向图和有向图都适用. 规定平凡图为欧拉图.

欧拉通路是简单通路, 欧拉回路是简单回路. 环不影响图的欧拉性.

欧拉图的判别法

定理 无向图G为欧拉图当且仅当G连通且无奇度顶点.

无向图G是半欧拉图当且仅当G连通且恰有两个奇度顶点. 定理 有向图D是欧拉图当且仅当D连通且每个顶点的入度都等于出度. 有向图D具有欧拉通路当且仅当D连通且恰有两个奇度顶点, 其中一个入度比出度大1, 另一个出度比入度大1, 其余顶点的入度等于出度.

8.3 哈密顿图

哈密顿通路: 经过图中所有顶点一次且仅一次的通路.

哈密顿回路: 经过图中所有顶点一次且仅一次的回路. 哈密顿图: 具有哈密顿回路的图.

半哈密顿图: 具有哈密顿通路而无哈密顿回路的图. 几点说明： 平凡图是哈密顿图.

哈密顿通路是初级通路，哈密顿回路是初级回路. 环与平行边不影响图的哈密顿性.

无向哈密顿图的一个必要条件

定理 设无向图G=是哈密顿图, 则对于任意V1?V且

V1??, 均有 p(G?V1)?|V1|.

证 设C为G中一条哈密顿回路, 有p(C?V1) ? |V1|. 又因为

C?G, 故 p(G?V1) ? p(C?V1) ? |V1|. 几点说明

定理中的条件是哈密顿图的必要条件, 但不是充分条件. 可利用该定理判断某些图不是哈密顿图. 由定理可知, Kr,s当s?r+1时不是哈密顿图. 当r?2时, Kr,r是哈密顿图, 而Kr,r+1是半哈密顿图.

例 设G为n阶无向连通简单图, 若G中有割点或桥,