图论

图论离散数学图图的基本概念通路与回路、连通的概念图的表示图的运算ABCD图论起源公元十八世纪有这样一个问题：在东普鲁士有个哥尼斯堡城（konigsberg，后属于苏联立陶宛苏维埃社会主义共和国，现名为加里宁格勒；现属于立陶宛共和国）。哥尼斯堡城位于pregel河畔，河中有两个岛，城市中的各个部分由七座桥相连。图论起源当时，城中的居民热衷于这样一个问题，从四块陆地的任一块出发，怎样才能做到经过每座桥一次且仅一次，然后回到出发点。问题看来并不复杂，但当地的居民和游人做了不少的尝试，却都没有取得成功。最早引入图论处理的问题就是哥尼斯堡七桥问题。1736年，瑞士数学家L.Eluer（欧拉）在他发表的“哥尼斯堡七座桥”的著名文章中阐述了解决这个问题的观点，从而被誉为图论之父。ABCD图论起源Euler将四块陆地表示成四个结点，凡陆地间有桥相连的，便在两点间连一条边。DCAB图论起源此时，哥尼斯堡七桥问题归结为：从A,B,C,D任一点出发，通过每条边一次且仅一次而返回出发点的回通路是否存在？图论起源欧拉断言这样的回通路是不存在的。理由是：从图中的任一点出发，为了要回到原来的出发点，要求与每个点相关联的边数均为偶数。这样才能保证从一条边进入某点后，再从另一条边出去，从一个点的不同的两条边一进一出才能回到出发点。而图中的A,B,C,D全是与奇数条边相连，由此可知所要求的回通路是不可能存在的。1图的基本概念1无向图和有向图2度的概念3图的分类4子图与补图5图的同构1.1无向图和有向图定义1一个无向图可以表示为G=（V，E），其中V是非空有限结点集，称V中的元素为结点或顶点；E是边集，其中的元素是由V中的元素组成的无序对，称E中的元素为边。若（v，w）是无序对，则（v，w）=（w，v）。例如,G=V,E如图所示,其中V={v1,v2,…,v5}E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}e1e2e3e4e5e6e7v5v1v2v3v4有向图定义1.2一个有向图可以表示为D=（V，E），其中V是非空有限结点集，称V中的元素为结点或顶点；E是有向边集，E中的元素是由V中的元素组成的有序对，称E中的元素为有向边。有向图D=（V，E）。结点集V={v1，v2，v3，v4}，有向边集E={v1，v1，v1，v2，v1，v2，v1，v3，v2，v3，v3，v4，v4，v3}。在有向图中，b，aa，b图的术语定义1.3如果关联一对结点的边多于一条，则称这些边为平行边。如果有边关联于一对结点，则称这对结点是邻接的。一条边的两个端点如果关联于同一个结点，则称为环，和任何边都不关联的点称为孤立点。边e2和e3是平行边，边e1关联结点v1和v3，则称v1和v3是邻接的，边e5=（v3，v3）是环，v4是孤立点。图的术语如果关联一对结点的方向相同的有向边多于一条，则称这些有向边为多重有向边或平行边。如关联于结点v1和v2的两条有向边是平行边，而关联于结点v3和v4的两条有向边方向相反，不是平行边。（v1，v1）称为环。对于有向边（v2，v3），称v2为起点，v3为终点，v2和v3是邻接的。图的术语•n阶图:n个顶点的图•零图:E=的图•平凡图:1阶零图在图的定义中规定结点集合V为非空集，但在运算中可能产生结点集为空集的运算结果，因此规定结点集为空集的图为空图，记为1.2度的概念定义1.6设G=V,E为无向图,vV,v所关联的边数称为v的度数，简称度，记作d(v)。悬挂顶点:度数为1的顶点悬挂边:与悬挂顶点关联的边G的最大度(G)=max{d(v)|vV}G的最小度(G)=min{d(v)|vV}例如d(v5)=3,d(v2)=4,d(v1)=4,(G)=4,(G)=1,v4是悬挂顶点,e7是悬挂边,e1是环e1e2e3e4e5e6e7v5v1v2v3v4顶点的度数(续)定义1.7设D=V,E为有向图,vV,以v为起点所关联的边数称为v的出度，记作d+(v)；以v为终点所关联的边数称为v的入度，记作d(v)。v的总度数(度)d(v)是v的出度和入度之和：d(v)=d+(v)+d-(v)+(D),+(D),(D),(D),(D),(D)悬挂顶点,悬挂边例如d+(a)=4,d-(a)=1,d(a)=5,d+(b)=0,d-(b)=3,d(b)=3,+=4,+=0,=3,=1,=5,=3e1e2e3e4e5e6e7dabc握手定理定理1.1设图G=(V,E)为无向图或有向图，G有n个结点v1,v2,…,vn，e条边(无向或有向),则图G中所有结点的度数之和为边数的两倍，即证图中每条边(包括环)均有两个端点,所以在计算各顶点度数之和时,每条边均提供2度,m条边共提供2m度.推论任何图(无向图和有向图)中，度数为奇数的结点的个数为偶数。1()2niidve定理1.2定理1.2在有向图中，所有结点的入度之和与所有结点的出度之和相等，都等于图中的有向边数。证在有向图中，每条有向边均有一个起点和一个终点。于是在计算图中各结点的出度之和与各结点的入度之和时，每条有向边各提供一个出度和一个入度。当然e条有向边共提供e个出度和e个入度。因此所有结点的入度之和与所有结点的出度之和相等，都等于图中的有向边数e。图的度数列设无向图G的顶点集V={v1，v2，……，vn}G的度数列:d(v1),d(v2),…,d(vn)如右图度数列:4,4,2,1,3设有向图D的顶点集V={v1，v2，……，vn}D的度数列d(v1),d(v2),…,d(vn)D的出度列:d+(v1),d+(v2),…,d+(vn)D的入度列:d(v1),d(v2),…,d(vn)如右图度数列:5,3,3,3出度列:4,0,2,1入度列:1,3,1,2e1e2e3e4e5e6e7v5v1v2v3v4e1e2e3e4e5e6e7dabc例题例自然数序列(3，3，2，2，1)，(4，2，2，1，1)能作为图的结点的度数序列吗？为什么？解在(3，3，2，2，1)中各个数之和为奇数，由握手定理可知，(3，3，2，2，1)不能作为图的结点的度数序列。(4，2，2，1，1)能作为图的结点的度数序列，下图中的两个图都是以（4,2,2,1,1）为结点度数序列。实例例已知图G有10条边,4个3度顶点,其余顶点的度数均小于等于2,问G至少有多少个顶点?解设G有n个顶点.由握手定理,43+2(n-4)210解得n8例已知5阶有向图的度数列和出度列分别为3,3,2,3,3和1,2,1,2,1,求它的入度列解2,1,1,1,2实例例证明不存在具有奇数个面且每个面都具有奇数条棱的多面体.证用反证法.假设存在这样的多面体,作无向图G=V,E,其中V={v|v为多面体的面},E={(u,v)|u,vVu与v有公共的棱uv}.根据假设,|V|为奇数且vV,d(v)为奇数.这与握手定理的推论矛盾.1.3图的分类定义1.8设图G=（V，E）为无向图或有向图，如果G中不含平行边，也不含环，则称为简单图。定义1.9设图G=（V，E）为无向图或有向图，如果G中含有平行边，则称为多重图。简单图多重图多重图简单图图的应用1、航班路线图有向多重图2、微博关注图有向简单图3、合作关系图无向简单图或多重图完全图(1)定义1.10设G=（V，E）是n阶无向简单图，若G中任何结点都与其余的n-1个结点相邻，则称G为n阶无向完全图，记作Kn。图1.7完全图顶点数n,边数m=n(n-1)/2,(G)=(G)=n-1K3K5完全图(2)设G=（V，E）为n阶有向简单图，若对于V中任意的两个结点u和v，既有有向边(u，v)，又有有向边(v，u)，则称G是n阶有向完全图。顶点数n,边数m=n(n-1),+(D)=+(D)=-(D)=-(D)=n-1,(D)=(D)=2(n-1)无特别说明时，完全图均指无向完全图。定理1.3定理1.3设G为任意n阶无向简单图，则(G)n-1。证明：略例题例5判断下列各非负整数列是否是简单图的结点度数序列？（1）（5,5,4,4,2,1）（2）（5,4,3,2,2）（3）（3,3,2,2,1,1）（4）解（1）根据握手定理的推论可知，不是图的结点度数序列，因为有3个奇数。（2）中有5个数，最大数是5，根据定理1.3，它不是简单图的结点序列。（3）是简单图的结点序列。下图的两个无向简单图都是（3,3,2,2,1,1）为结点度数序列。（4）中的最大值d1n,根据定理1.3，不是简单图的结点序列。12121(,,,),1nnniiddddddd且为偶数正则图定义1.11设G为n阶无向简单图，若vV（G），均有d(v)=k,则称G为k-正则图。K52正则图4正则图3正则图彼得松图正则图根据握手定理，n阶k-正则图的边数。当k为奇数时，n为偶数。当k=0时，0-正则图就是n阶零图。n阶无向完全图是(n-1)-正则图。2nkm环图和轮图定义1.12如果图G=（V，E）的结点集V={v1，v2，vn}（n3），边集E={（v1，v2），（v2，v3），（vn-1，vn），（vn，v1）}，则称G为环图，记为Cn。下图是C3,C4,C5,C6。定义1.13当给环图Cn-1（n4）添加一个结点，并把这个结点和Cn-1里的每个结点逐个连接后得到的图成为轮图，记作Wn。下图是轮图W4，W5，W6，W7。方体图定义1.14如果图G=（V，E）有2n个结点，每个结点表示一个长度为n的位串，任何两个相邻的结点表示的位串只有一位不同，则称G称为n方体图，记作Qn。0110110001010101100000111011001Q1Q2Q3方体图对任意nN，Qn是将两个Qn-1图的对应结点连接起来的简单图.Q0有1个结点.Q0Q1Q2Q3Q4结点数:2n.边数：n2n-1二分图定义1.15如果图G=（V，E）的结点集V能划分为两个子集：V1和V2，使每条边有一个端点在V1中,另一个端点在V2中，则称该图为二分图（或二部图）。定义1.16二分图G=（V，E）的结点集V能划分为两个子集：V1和V2，若V1中的每个结点和V2中的每个结点均有边相连，则称G为完全二分图。若|V1|=m，|V2|=n,则可记为Km,n。下图所示的是K2,3和K3,3。带权图定义1.17每个结点或每条边都带有数值的图称为带权图。可以用有序三元组或有序四元组表示带权图。如G=(V,E,f)，G=(V,E,g)或G=(V,E,f,g)，其中V是结点集，E是边集，f是结点所带的权的集合，g是边所带的权的集合。下图左边为边带权图，右边为结点带权图。355861091.4子图与补图定义1.18设图G=（V，E）①设eE，从G图中删去边e得到的图表示为G-e,称为删除边运算；设E1E，从G图中删去E1的所有边得到的图表示为G-E1,称为删除边集运算。②设vV，从G图中删去结点v及v关联的所有边得到的图表示为G−v,称为删除结点运算；设V1V，从G图中删去V1中所有结点及它们关联的所有边得到的图表示为G−V1,称为删除结点集运算。③设e=(u,v)E，从G图中删去边e,将e的两个端点u、v用一个新的结点w代替，将u,v关联的所有边都关联结点w，称为边e的收缩，记为G\e。④设u,vV，在u,v之间加一条边（u,v），称为加新边，表示为G(u,v)(或G+(u,v))。例题在下图中，(1)为图G，(2)为G-e1,(3)为G-{e1,e2}，(4)为G-v3,(5)为G-{v1,v3},(6)为G\e1。v1v2v3v4e1e2e3e4e5e6v1v2v3v4e2e3e4e5e6v1v2v3v4e2e3e5e6v1v2v4e2e3e5e6v2v4e5e6v1v2v4e2e3e4e5e6(1)(2)(3)(4)(5)(6)子图定义1.19设G=（V，E）和G