图论第2章欧拉图和哈密尔顿图主要内容欧拉路：在无孤立结点的图G(有向图或无向图)中，如果存在一条路经过每一条边一次且仅一次，则称该路为欧拉路。欧拉图：如果存在一条回路经过每一条边一次且仅一次，则称该回路为欧拉回路。具有欧拉回路的图称为欧拉图。定理：无向图G具有一条欧拉路当且仅当G是连通的且有零个或两个奇度结点。证：必要性：设G具有一条欧拉路，则G是连通的且有零个或两个奇度结点。设vi是图G的任意结点，若vi不是L的端点，每当沿L经过vi一次都经过该结点关联的两条边，为该结点的度数增加2。由于G的每一条边都在该路上，且不重复，所以vi的度数必为偶数。若vi是L的端点v0，当v0=vk时，则v0和vk的度数也为偶数，即G中无奇度结点；当v0≠vk时，则v0和vk的度数均为奇数，即G中有两个奇度结点。①若G中有两个奇度结点，则从其中的一个v0开始构造一条简单路。从v0出发经关联边e1进入v1，若v1是偶数度结点，则必可以由v1经关联边e2进入v2。如此下去，每边只取一次。由于G是连通图，必可到达另一个奇度结点vk，从而得到一条简单路L1：v0e1v1e2v2…ekvk。②若G中无奇度结点，则从任意结点v0出发，用上述方法必可回到结点v0，得到一条简单回路L1：v0e1v1e2v2…v0。推论：无向图G具有一条欧拉回路当且仅当G是连通的且所有结点都是偶度的。这个推论说明，无向图G是欧拉图当且仅当G是连通的且所有结点都是偶度的。图(a)中有一个欧拉回路，是欧拉图；图(b)中有一个欧拉路，但没有欧拉回路，不是欧拉图；图(c)中没有欧拉路，更没有欧拉回路，不是欧拉图。定理：有向图G具有一条欧拉回路当且仅当G是强连通的且每个结点的入度等于出度。定理：有向图G具有一条欧拉路当且仅当G是单向连通的且除了两个结点外，每个结点的入度等于出度，而在这两个结点中，一个结点入度比出度大1，另一个结点入度比出度小1。注：这两个定理可以看作是前面定理和推论的推广。因为对于有向图的任意一个结点，如果入度与出度相等，则该结点的度数为偶数。若入度与出度之差为1时，则该结点的度数为奇数。图(a)是强连通的，具有一个欧拉回路，是欧拉图；图(b)是单向连通的，具有一个欧拉路，但没有欧拉回路；图(c)中没有欧拉路，更没有欧拉回路。欧拉图欧拉图欧拉图汉密尔顿路：在图G(有向图或无向图)中，如果存在一条路，经过每个结点一次且仅一次，则该路称为汉密尔顿路。汉密尔顿图：如果存在一条回路，经过每个结点一次且仅一次，则称该路为汉密尔顿回路。具有汉密尔顿回路的图称为汉密尔顿图。汉密尔顿图是由爱尔兰数学家威廉·汉密尔顿爵士(SirWillianHamilton)于1859首先提出的。与欧拉图不同，判断一个图是否为汉密尔顿图至今还没有一个简单的充分必要条件，只有一些必要条件和充分条件。判断一个图是汉密尔顿图的充分必要条件是图论中尚未解决的基本难题之一。汉密尔顿图汉密尔顿图令S={a,b}，则W(G-S)=3，|S|=2，故W(G–S)≤|S|不成立，所以该图不是汉密尔顿图。证：设v是割点。删除结点v，图成为不连通的，且至少有两个连通分支。令S={v}，则W(G–S)≥2＞1=|S|，即W(G–S)＞|S|G不是汉密尔顿图。若G中有桥，则该桥的一个端点是割点。可以归结为G中有割点的情况。所以G也不是汉密尔顿图。汉密尔顿图汉密尔顿图证：只要证图G中任意两不同结点度数之和大于等于n-1即可。用反证法。设图G中存在两个结点v1和v2，使得deg(v1)＋deg(v2)＜n–1，即deg(v1)＋deg(v2)≤n–2。删去结点v1和v2后，得到图G′，G′是具有n-2个结点的无向简单图。设G′的边数为m′,则m′≥m-(n-2)＞(n-1)(n-2)-(n-2)=(n-2)(n-3)，即m′＞(n–2)(n–3)G′是具有n–2个结点的无向简单图，它最多有(n–2)(n–3)/2条边。所以m′≤(n–2)(n–3)/2。由此得出矛盾，所以deg(v1)＋deg(v2)≥n–1。解：因为有5个风景点，故可看成一个有5个结点的无向图，其中每处均有两条路与其它结点相通，所以deg(vi)=2，i=1,…,5。故对任意两点vi，vj均有deg(vi)+deg(vj)=2+2=4=5-1由定理可知，此图中一定有一条汉密尔顿路。汉密尔顿图汉密尔顿图证：任取一结点a用A标记，所有与它相邻接的结点标记为B。继续不断地用A标记所有邻接于B的结点，再用B标记所有邻接于A的结点，直到所有的结点标记完毕。B汉密尔顿图总结