离散数学第7章.

第四篇图论图论是近年来发展迅速而又应用广泛的一门新兴学科。它最早起源于一些数学游戏的难题研究，如1736年欧拉（L.Euler)所解决的哥尼斯堡七桥问题。以及在民间广为流传的一些游戏问题：例如迷宫问题、棋盘上马的行走路线问题等等。这些古老的问题当时吸引了许多学者的注意，从而在这些问题研究的基础上，又提出了著名的四色猜想和环游世界各国的问题。例：用定理解决哥尼斯堡桥的问题第四篇图论图论不断发展，它在解决运筹学，网络理论，信息论，控制论，博奕论以及计算机科学等各个领域的问题时，显示出越来越大的效果。对于这样一门应用广泛的学科，其包含的内容是丰富的，本篇我们只准备介绍基本的概念和定理，为今后有关学科及课程的学习和研究提供方便。电力网因特网复杂网络的事例——技术网络复杂网络的事例——社会网络朋友关系网演员网科学家合著网科学引文网复杂网络的事例——交通运输网络城市公共交通网道路交通网航空网复杂网络的事例——生物网络神经网络生态网络蛋白质相互作用网络基因网络新陈代谢网络SantaFe研究所的科学家合作网复杂网络的事例——科学家合作网经济物理学科学家合作网复杂网络的事例——科学家合作网复杂网络的事例——中药方剂网示意图点（药材），边（药材之间相互作用），局域世界（方剂）§1图的基本概念•定义:图（graph）G由一个三元组V(G),E(G),G表示，其中：•非空集合V(G)={v1,v2,…,vr}称为图G的结点集，其成员vi(i=1,2,…,r)称为结点或顶点（nodesorvertices）；•集合E(G)={e1,e2,…,es}称为图G的边集，其成员ej(j=1,2,…s)称为边(edges)。•函数G：E(G)→(V(G),V(G))，称为边与顶点的关联映射（associatvemapping）§1图的基本概念•例：G=V(G)，E(G)，G•其中V(G)={a，b，c，d}，E(G)={e1，e2，e3，e4，e5，e6}，G(e1)=(a，b)，G(e2)=(a，c)，G(e3)=(b，d)，G(e4)=(b，c)，G(e5)=(d，c)，G(e6)=(a，d)abcde1e2e3e4e5e6§1图的基本概念讨论定义：(1)V(G)={V1，V2，…，Vn}为有限非空集合,Vi称为结点,简称V是点集。(2)E(G)={e1，…，em}为有限的边集合,ei称边，每个ei都有V中的结点对与之相对应,称E为边集。即每条边是连结V中的某两个点的。§1图的基本概念(3)若Ｇ中每一条边e与有序偶对vi,vj或无序偶对(vi,vj)相关联，则可说边e连接结点vi和vj(4)可用e＝vi,vj或e＝(vi,vj)，以结点来表示图的边，这样可把图简化成：Ｇ＝Ｖ，Ｅ。例：有图如下，试写成定义表达式Ｇ＝〈Ｖ，Ｅ〉，其中Ｖ＝{v1,v2,v3,v4,v5}Ｅ＝{x1,x2,x3,x4,x5,x6}§1图的基本概念例：对有向图可表示为：Ｇ＝〈Ｖ、Ｅ〉，其中Ｖ＝｛a、b、c、d｝Ｅ＝｛a,b,b,a,b,d,d,a,d,d,c,c｝§1图的基本概念下面定义一些专门名词：(1)有向边：若边ej与结点序偶vj,vk关联，那么称该边为有向边。(2)无向边：若边ej与结点无序偶(vj,vk)关联，那么称该边为无向边。§1图的基本概念(3)邻接结点：由一条边（有向或无向）连接起来的结点偶对。(4)（ｎ，ｅ）图：具有ｎ个结点（顶点），ｅ条边的图。§1图的基本概念(5)有向图：在Ｇ中每一条边均为有向边。(6)无向图：每条边均为无向边的图。(7)混合图：有些边是无向边，有些边是有向边的图称为混合图。§1图的基本概念V1’v1v4v5v1v2v3v4V2’V3’V4’(a)无向图(b)有向图(c)混合图(孤立点)v2v3环§1图的基本概念(8)点和边的关联：如ei=(u，v)或ei=u，v称u，v与ei关联。(9)点与点的相邻：关联于同一条边的结点称为邻接点。(10)边与边的邻接：关联于同一结点的边称为邻接边。§1图的基本概念(11)孤立结点：不与任何结点相邻接的结点称为孤立结点。(12)零图：仅有孤立结点的图。(13)平凡图：仅有一个孤立结点的图。(14)自回路(环)：关联于同一结点的边称为自回路，或称为环。§1图的基本概念(15)平行边：在有向图中，始点和终点均相同的边称为平行边，无向图中若两点间有多条边，称这些边为平行边，两点间平行边的条数称为边的重数。定义：在图G=V，E，vV，与结点v关联的边数称为该点的度数，记为deg(v)。孤立结点的度数为0。图G最大度记为(G)=max{deg(v)|vV(G)}，最小度数记为(G)=min{deg(v)|vV(G)}§1图的基本概念定义：在有向图中，vV，以v为始点的边数称为该结点的出度，记作deg+(v);以v为终点的边数称为该结点的入度，记作deg-(v)。•显然有deg(v)=deg+(v)+deg-(v)如：G1是无向图，deg(v1)=3，deg(v2)=1G2是有向图，deg+(v1)=2，deg-(v1)=3，deg(v1)=5，v1v2G1v1v3v4v2G2定理：每个图中，结点度数总和等于边数的两倍。即deg(v)=2|E|vV定理：在任何图中,度数为奇数的结点必定是偶数个。定理：在任何有向图中，所有结点的入度之和等于所有结点的出度之和。定义：含有平行边的图称为多重图。简单图：不含平行边和环的图称为简单图。定义：简单图G=V，E中，若每一对结点间均有边相连，则称该图为完全图。有n个结点的无向完全图记为Kn。定理：在任何图中,n个结点的无向完全图Kn的边数为n(n-1)/2。无向完全图：每一条边都是无向边不含有平行边和环每一对结点间都有边相连证明：n个结点中任取两个结点的组合数为Cn2=n(n-1)/2故的边数为|E|=n(n-1)/2定义：给定一个简单图G，由G中所有结点和所有能使G成为完全图的添加边组成的图，称为G的相对于完全图的补图，或简称为G的补图，记为G。即G=V，E1，G=V，E2，其中E2={(u，v)u，vV，(u，v)E1}。v5v1v2v3v4v5v1v2v3v4v5v1v2v3v4(a)完全图K5(b)图G(c)图G的补图G’定义：设图G=V，E，如果有图G’=V’，E’，且E’E，V’V，则称G’为G的子图。当V’=V时，则称G’为G的生成子图。相对于图G的补图定义：设G’=V’，E’是G=V，E的子图，若给定另一个图G”=V”，E”使得E”=E-E’，且V”中仅包含E”的边所关联的结点，则称G”是子图G’相对于图G的补图。定义：设图G=V，E及图G’=V’，E’，如果存在一一对应的映射g：vivi’且e=(vi，vj)(或vi，vj)是G的一条边，当且仅当e’=(g(vi)，g(vj))(或g(vi)，g(vj))是G’的一条边，则称G与G’同构，记作G≌G’。两图同构的一些必要条件：1.结点数目相同；2.边数相等；3.度数相同的结点数目相等。§2路与回路定义:给定图G=V,E,设v0,v1,…,vnV，e1,…,enE,其中ei是关联于结点vi-1,vi的边，交替序列v0e1v1e2…envn称为结点v0到vn的路（拟路径Pseudopath）。v0和vn分别称为路的起点和终点，边的数目n称作路的长度。当v0=vn时，这条路称作回路（闭路径closedwalk）。例如路：v1e2v3e3v2e3v3e4v2e6v5e7v3v5e8v4e5v2e6v5e7v3e4v2v4e8v5e6v2e1v1e2v3v2e1v1e2v3e7v5e6v2§2路与回路若一条路中所有的边e1,…,en均不相同称作迹（路径walk）。若一条路中所有的结点v0,v1,…,vn均不相同,称作通路（Path）。闭的通路,即除v0=vn之外，其余结点均不相同的路，称作圈（回路circuit）。§2路与回路定理：在一个具有n个结点的图中，如果从结点vj到结点vk存在一条路，则从结点vj到结点vk必存在一条不多于n-1条边的路。§2路与回路推论：在一个具有n个结点的图中，如果从结点vj到结点vk存在一条路，则从结点vj到结点vk必存在一条边数小于n的通路。§2路与回路定义：在无向图G中，如果从结点u和结点v之间若存在一条路，则称结点u和结点v是连通的（connected）。§2路与回路结点之间的连通性是结点集V上的等价关系。把子图G(V1),G(V2),…,G(Vm)称为图G的连通分支（connectedcomponents）,图G的连通分支数记为W(G)。§2路与回路定义：若图G只有一个连通分支，则称G是连通图。显然在连通图中，任意两个结点之间必是连通的。§2路与回路对于连通图，常常由于删除了图中的点或边，而影响了图的连通性。删除结点：所谓在图中删除结点v，即是把v以及与v关联的边都删除。删除边：所谓在图中删除某条边，即是把该边删除。§2路与回路v3v2v1v6v4(a)v5v5v1v2v3v6v4(c)ev3v2v6v4(b)v5e定义：设无向图G=V,E是连通图,若有结点集V1V,使图G中删除了V1的所有结点后,所得到的子图是不连通图,而删除了V1的任何真子集后,所得到的子图仍是连通图,则称V1是G的一个点割集(cut-setofnodes)。若某一个点构成一个点割集，则称该点为割点。sabcdabcdba§2路与回路点连通度：为了产生一个不连通图需要删去的点的最少数目，也称为连通度,记为k(G)。即k(G)=min{|V1||是G的点割集}称为图G的点连通度(node-connectivity)。§2路与回路(1)若G是平凡图则k(G)=0(2)k(Kn)=n-1(3)若图存在割点，则k(G)=1(4)规定非连通图的连通度k(G)=0§2路与回路v5v1v2v3v4v5v1v3v4点割集V1={v2}§2路与回路定义：设无向图G=V,E是连通图,若有边集E1E，使图G中删除了E1的所有边后，所得到的子图是不连通图，而删除了E1的任何真子集后，所得到的子图仍是连通图，则称E1是G的一个边割集(cut-setofedges)。若某一条边就构成一个边割集，则称该边为割边或桥。割边e使图G满足W(G-e)W(G)。§2路与回路边连通度(edge-connectivity)(G)定义：非平凡图的边连通度为(G)=min{|E1||E1是G的边割集}边连通度(G)是为了产生一个不连通图需要删去的边的最少数目。§2路与回路(1)若G是平凡图则(G)=0(2)若G存在割边，则(G)=1，(3)规定非连通图的边连通度为(G)=0§2路与回路定理：对于任何一个图G,有k(G)≤(G)≤δ(G)。δ(G)=min(deg(v)，vV)§2路与回路若G不连通，则k(G)=(G)=0，故上式成立。若G连通，可分两步证明上式也成立：1)先证明(G)≤(G)：如果G是平凡图，则(G)=0≤(G)，若G是非平凡图，则因每一结点的所有关联边必含一个边割集，(因(G)=min{deg(v)|vV}，设uV使的deg(u)=δ(G)，与u相关联的条边必包含一个边割集，至少这条边删除使图不连通。)故(G)≤(G)。§2路与回路2)再证k(G)≤(G)：(a)设(G)=1，即G有一割边，显然这时k(G)=l，上式成立。§2路与回路(b)设(G)≥2，则必可删去某(G)条边，使G不连通，而删去其中(G)-1条边，它仍是连通的，且有一条桥e=(u，v)。对(G)-1条边中的每一条边都选取一个不同于u，v的端点，把这些端点删去则必至少删去(G)-1条边。若这样产生的图是不连通的，则k(G)≤(G)-1(G)，若这样产生的图是连通的，则e仍是桥，此时再删去u或v就必产生一个不连通图，故k(G)≤