节欧拉图与哈密顿图.pptVIP

第13节 欧拉图与哈密顿图 主要内容： 欧拉(Euler)图 哈密顿(Hamilton)图 哥尼斯堡七桥问题： 欧拉图 “一笔画”问题： 欧拉图的定义 定义1 包含图的所有顶点和所有边的闭迹称为 欧拉闭迹. 存在一条欧拉闭迹的图称为欧拉图. 定义2 包含图的所有顶点和边的迹称为欧拉迹. 包含欧拉迹的图称为半欧拉图. 说明： (1)上述定义对无向图和有向图都适用. (2)规定平凡图为欧拉图. (3)环不影响图的欧拉性. 欧拉图的判别定理 定理1 图G是欧拉图当且仅当G是连通的且每个顶 点的度都是偶数。 证 (必要性)设G是一个欧拉图，则G中有一条包含 G的所有顶点和所有边的闭迹，所以G是连通的. 设G是n个顶点m条边的欧拉图，则G中存在欧拉 闭迹. 设为C=vi0ej1vi1ej2...vi(m-1)ejmvi0，在这里每条边都 不相等. v，v在C中每出现一次就获得两度，若出现k次就获得2k度，所以degv=2k，即v的度数为偶数. (充分性)设G是连通的且每个顶点的度都是偶 数，则知G中有一个圈Z1. 否则Z1不包含G的所有边，这时从G中删去圈Z1上 的边，得到的图记为G1. G1的每个顶点的度均为偶数，并且至少有一个顶点的度数不为零，则G1中有圈Z2，从G1中删去Z2得到的图记为G2. 如果Z1包含了G的所有边，从而也就包含了G的所 有顶点，因此Z1是G的欧拉闭迹，故G是欧拉图. 欧拉图的判别定理 若G2中还有边，则同样的方式，G2中有圈Z3，如 此等等，最后必得到一个图Gn，Gn中无边. 于是我们得到了G中的n个圈Z1,Z2,...,Zn,，它们是两 两无公共边的，因此，G的每条边在且仅在其中的一个 圈上，于是G的边集被划分为n个圈. 由于G是连通的，所以每个圈Zi至少与其余的某个 圈有公共顶点，从而图G由一些边不重的相互之间有公 共顶点的圈构成. 欧拉图的判别定理 且这些圈构成一条欧拉闭迹。对圈的个数n用归纳 法证明。当n=1时，按圈的定义显然成立. 假设当n=k时成立，也就是k个边不重的有公共顶点 的圈Z1,Z2,...,Zk形成一个欧拉闭迹. 当n=k+1，因为每个圈与其它圈有公共顶点，所以 圈Zk+1必与某个圈Zi有公共顶点，设这个公共顶点为v， 在圈Zk+1上从v开始走遍Zk+1. 按归纳假设前k个圈是一个欧拉闭迹，因此从v开始 有一条欧拉闭迹. 因此定理成立. 欧拉图的判别定理 推论1 设G是一个连通图，则下列命题等价： (1) G是一个欧拉图. (2) G的每个顶点的度都是偶数. (3) G的边集能划分成若干互相边不相交的圈. 欧拉图的判别定理推论  假设G是连通的且恰有两个奇度顶点u和v，在 G中的u与v间加一条边得到图G (G 可能是多重图)， 则G 的所有顶点的度都是偶数，由定理1，G 有欧 拉闭迹. 从这个欧拉闭迹中去掉我们增加的u与v间的边，便 得到G的欧拉迹. 推论2 图G有一条欧拉迹当且仅当G是连通的 且恰有两个奇度顶点. 证  设G有欧拉迹，则由定理6.5.1的证明可知， 除了这条迹的起点和终点外的每个顶点的度都是偶数. 欧拉图的判别定理推论 无欧拉迹 欧拉图 欧拉图 有欧拉迹 非欧拉图 有欧拉迹 非欧拉图 无欧拉迹 实 例 哈密顿图 周游世界问题(W. Hamilton, 1859年) 定义1 图G的一条生成路称为G的哈密顿路. 所谓G的生成路就是包含G的所有顶点的路. G的一个包含所有顶点的圈称为G的一个哈密顿圈. 具有哈密顿圈的图称为哈密顿图. (1)有哈密顿路的图是连通图. (2)每个哈密顿图是连通的，并且每个顶点的度大 于或等于2. (3)完全图是哈密顿图. 哈密顿图 (4)有哈密顿通路不一定有哈密顿回路. (5)环与平行边不影响图的哈密顿性. 说明： 定理1 设G=(V, E)是哈密顿图，则对V的每个非空 子集S，均有 (G-S)≤S，其中G-S是从G中去掉S中 那些顶点后所得到的图，而(G-S)是图G-S的支数. 证 设H是G的哈密顿圈，先考虑(H-S)的支数.