图论回路问题.pdf

回路问题 图论 欧拉图（E图） 这里主要讨论图的遍历问题,一个是遍历过程中要求经过 的所有边都不同;一个是遍历过程中要求经过的所有结点 都不同. 欧拉在1736年发表了第一篇关于图论的论文, 就是就 七 桥问题. A A e e 1 e 5 2 B e6 D B D e 3 e 4 e C 7 C 定义:在无孤立结点的图G中,若存在一条回路,它 经过图中每条边一次且仅一次,称此回路为 欧拉回路.称此图为欧拉图,或E图 有欧拉回路: v1 v v v v v v v v v v v 1 2 3 4 5 2 4 6 5 3 1 v2 v3 v v 如何判定一个图中是否有 4 5 v 欧拉路,或有欧拉回路? 6 a b 1 4 c d 3 2 定理8.1 —个连通无间图G＝(T,G)具有欧拉回路的 充要条件是它的每一个结点的次数均为偶数。 证： 必要性 设G具有欧拉回路，用C表示这个回路，故G的所 有结点都在这个回路上，对任一结点 ，回路 v V ∈ C至少穿过它一次，(到达该结点和离开出结点称 为穿过结点一次)否则这个结点将是孤点，与题设 矛盾，而每穿过结点一次都将使结点的次数增加 2、因边是不重复的，故给点的次数一定是2 的整 数倍，即为偶数。 • 充分性 设图G的每一结点次数均为偶数。 (1)图的每一结点次数都是最小的偶数2，由于图是连通，因而只能有一个 回路，图是一个多边形，显然这个回路就是欧拉回路。 (2)图的某些结点(或者所有结点)的次数是大于2的偶数，不妨用图(a)来描 述，则图至少有一个基本回路．例如图中的bde