《计算机数学基础》离散数学辅导(6)
第6章 几种特殊的图
本章重点:欧拉图和哈密顿图,平面图和树的基本概念.
一,重点内容
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=中V3,任意不同结点,则G是哈密顿图.(充分条件,定理4)
(2) 有向完全图D=, 若,则图D是哈密顿图. (充分条件,定理5推论)
(3) 设无向图G=,V1V,则P(G-V1)V1(必要条件,定理3)
若此条件不满足,即V1V,使得P(G-V!)>V1,则G一定不是哈密顿图(非哈密顿图的充分条件).
3.平面图
平面图 一个图能画在平面上,除结点之外,再没有边与边相交.
面,边界和面的次数 由连通平面图G的边围成的其内部不含G的结点和边的区域是面,常用r表示. 围成面的各边组成的回路是边界. 边界回路的长度是面的次数,记作deg(r).
重要结论
(1)平面图(所有面的次数之和=边的2倍)(定理6).
(2)欧拉公式:平面图 面数为r,则(结点数与面数之和=边数+2)(定理7)
(3)平面图(定理8)
判定条件:图G是平面图的充分必要条件是G不含与K3,3或K5在2度结点内同构的子图.
4. 树
树 连通无回路的无向图.
树的判别 图,T是树的充分必要条件是(六个等价定义) (定理14):
(1) T是无回路的连通图; (2) 图T无回路且m=n-1;
(3) 图T连通且m=n-1
(4) 图T无回路,若增加一条边,就得到一条且仅一条回路;
(5) 图T连通,若删去任一边,G则不连通;
(6) 图T的每一对结点之间有一条且仅有一条通路.
生成树 图G的生成子图是树,该树就是生成树.
权与带权图 n个结点的连通图G,每边指定一正数,称为权,每边带权的图称为带权图. G的生成树T的所有边的权之和是生成树T的权,记作W(T).
最小生成树 带权最小的生成树.
有向树 有向图删去边的方向为树,该有向图就是有向树.
根树与树根 非平凡有向树,恰有一个结点的入度为0(该结点为树根),其余结点的入度为1,该树为根树.

下一页