计算机数学基础离散数学辅导(6).doc

1 《计算机数学基础》离散数学辅导(6) ??第6章几种特殊的图(2001 级用) 中央电大冯泰本章重点:欧拉图和哈密顿图、平面图和树的基本概念. 一、重点内容 1. 欧拉图?欧拉通路( 回路) 与欧拉图通过图 G 的每条边一次且仅一次,而且走遍每个结点的通路( 回路) ,就是欧拉通路( 回路). 存在欧拉回路的图就是欧拉图. 欧拉回路要求边不能重复, 结点可以重复. 笔不离开纸, 不重复地走完所有的边, 且走过所有结点,就是所谓的一笔画.?欧拉图或通路的判定(1) 无向连通图 G 是欧拉图?G 不含奇数度结点(G 的所有结点度数为偶数):( 定理 1) (2) 非平凡连通图 G 含有欧拉通路?G 最多有两个奇数度的结点; ( 定理 1 的推论) (3) 连通有向图 D 含有有向欧拉回路( 即欧拉图)?D 中每个结点的入度=出度连通有向图 D 含有有向欧拉通路?D 中除两个结点外,其余每个结点的入度=出度, 且此两点满足 deg -(u)- deg +(v)=? 1.( 定理 2) 2. 哈密顿图?哈密顿通路( 回路) 与哈密顿图通过图 G 的每个结点一次,且仅一次的通路( 回路), 就是哈密顿通路( 回路). 存在哈密顿回路的图就是哈密顿图. 判断哈密顿图是较为困难的.?哈密顿图的充分条件和必要条件(1) 在无向简单图G =< V,E>中?V?? 3, 任意不同结点 VvuGvu???) deg( ) deg( ,, ,则G 是哈密顿图.( 充分条件,定理 4) (2) 有向完全图 D=<V,E >,若3?V ,则图 D 是哈密顿图.( 充分条件,定理 5 推论) (3) 设无向图 G =< V,E >,?V 1?V ,则 P(G-V 1)??V 1?( 必要条件,定理 3) 若此条件不满足,即?V 1?V, 使得 P(G-V ! )>?V 1?,则G 一定不是哈密顿图( 非哈密顿图的充分条件). 3. 平面图?平面图一个图能画在平面上,除结点之外,再没有边与边相交. 面、边界和面的次数由连通平面图 G 的边围成的其内部不含 G 的结点和边的区域是面, 常用 r 表示. 围成面的各边组成的回路是边界. 边界回路的长度是面的次数, 记作 deg( r ). ?重要结论(1) 平面图 ereEvVEVG ri i2) deg( ,,,, 1????????则( 所有面的次数之和=边的 2 倍)( 定理 6). (2) 欧拉公式:平面图,,,,eEvVEVG?????面数为 r ,则2???rev ( 结点数与面数之和=边数+ 2)( 定理 7) (3) 平面图633,,,,????????veveEvVEVG,则若( 定理 8) ?判定条件:图G 是平面图的充分必要条件是 G 不含与 K 3 ,3或K 5在2 度结点内同构的子图. ?树连通无回路的无向图.?树的判别图mEnVEVT?????,,, ,T 是树的充分必要条件是( 六个等价定义) 2 ( 定理 14): (1) T 是无回路的连通图; (2) 图T 无回路且 m=n-1; (3) 图T 连通且 m=n-1 (4) 图T 无回路,若增加一条边,就得到一条且仅一条回路; (5) 图T 连通,若删去任一边, G 则不连通; (6) 图T 的每一对结点之间有一条且仅有一条通路. ?生成树图G