图论部分 第八章、一些特殊的图 8.1 二部图
二部图：定义 设无向图 G=
完全二部图：又若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=
由Hall定理不难证明, 上一页图(2)没有完备匹配.
定理 设二部图G=
Hall定理中的条件称为“相异性条件”, 第二个定理中的条件 称为 t 条件. 满足 t 条件的二部图一定满足相异性条件.
8.2 欧拉图
欧拉通路: 图中行遍所有顶点且恰好经过每条边一次的通路. 欧拉回路: 图中行遍所有顶点且恰好经过每条边一次的回路. 欧拉图: 有欧拉回路的图.
半欧拉图: 有欧拉通路而无欧拉回路的图. 几点说明：
上述定义对无向图和有向图都适用. 规定平凡图为欧拉图.
欧拉通路是简单通路, 欧拉回路是简单回路. 环不影响图的欧拉性.
欧拉图的判别法
定理 无向图G为欧拉图当且仅当G连通且无奇度顶点.
无向图G是半欧拉图当且仅当G连通且恰有两个奇度顶点. 定理 有向图D是欧拉图当且仅当D连通且每个顶点的入度都等于出度. 有向图D具有欧拉通路当且仅当D连通且恰有两个奇度顶点, 其中一个入度比出度大1, 另一个出度比入度大1, 其余顶点的入度等于出度.
8.3 哈密顿图
哈密顿通路: 经过图中所有顶点一次且仅一次的通路.
哈密顿回路: 经过图中所有顶点一次且仅一次的回路. 哈密顿图: 具有哈密顿回路的图.
半哈密顿图: 具有哈密顿通路而无哈密顿回路的图. 几点说明： 平凡图是哈密顿图.
哈密顿通路是初级通路，哈密顿回路是初级回路. 环与平行边不影响图的哈密顿性.
无向哈密顿图的一个必要条件
定理 设无向图G=
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中有割点或桥,
离散数学第八章一些特殊的图知识点总结
