图论

1图论•侯越先，[e-mail]，25楼B-1223室•一般性参考：《离散数学》，左孝凌等，上海科学技术出版社《现代图论》英文版，Bollobas等，科学出版社《算法导论》英文版，Cormen等，高教出版社•本ppt下载：求实BBS四区人工智能版21.图的基本概念•引入：实体和实体之间的关系是现实世界的两个基本要素。图论（GraphTheory，GT）有效地刻画了实体与实体之间的关系，是研究现实世界的有力数学工具，在算法理论、人工智能、软件理论和软件工程、计算机网络等计算机科学的不同分支中均有重要应用。•例子：聚会握手问题•例子：柯尼斯堡7桥问题31图的基本概念•定义1：一个图G是一个序偶V(G)，E(G)，其中V(G)是一个非空的结点（vertex）集合，E(G)是边（edge）集合，且E(G)V×V。通常，可以将图G简记为V，E。•例：{a，b，c，d}，{a，bb，cc，dd，a}•注:1.若边ei与结点的序偶vj,vk相关联，称该边为有向边。2.若边ei与结点的无序偶(vj,vk)相关联，称该边为无向边；若无需区别边的方向，可以用(vj,vk)指代有向边或者无向边。3.邻接点：由一条边关联的两个结点。4.孤立结点：不与任何结点相邻接的点。5.零图：仅由孤立结点组成的图。6.平凡图：仅由一个孤立结点组成的图。7.邻接边：关联于同一结点的两条边。41图的基本概念8.环（loop）：关联于同一结点的边，也称为自回路9.有向图、无向图和混合图：本课程只涉及有向图和无向图•定义2：设G=V,E是一个图，则|V|称为G的阶数（order），|E|称为G的规模（size）。•定义3：在图G=V,E中，与结点v(v∈V)关联的边数，称为该结点的度数（degree），记作deg(v)。51.图的基本概念•注：1每个环在其对应的结点上增加两度。2记△(G)=max{deg(v)|v∈V｝δ(G)=min{deg(v)|v∈V｝△(G)和δ(G)分别称为图G的最大度和最小度•定理1：每个图中，结点度数的总和等于边数的两倍。•定理2：在任何图中，度数为奇数的结点必定是偶数个。•定义4：在有向图中，射入一个结点的边数称为该结点的入度，由一个结点射出的边数称为该结点的出度。结点的出度与入度的和就是该结点的度数。VvEv2)deg(61.图的基本概念•定理3：在任何有向图中，所有结点的入度之和等于出度之和。•定义5：连接同一对结点的边称为平行边（paralleledge），含有平行边的图称为多重图（multigraph）；不含有平行边和自回路的图称为简单图(simplegraph)。•定义6：简单图G＝V,E中，若每一对结点间都有边相连，称该图为完全图（completegraph）。通常将有n个结点的无向完全图记作Kn。•例子•定理4：Kn的边数为n(n-1)/271.图的基本概念•定义7：设图G＝V,E，如果图G’＝V’,E’满足E’E，V’V，则G’称为G的子图（subgraph）若G’包含了E中所有连接了V’中任意两个点的边，则G’称为V’的导出子图（inducedsubgraph）若V’=V，则称G’为G的一个生成子图（spanningsubgraph）•例子81.图的基本概念•定义10：给定一个图G，由G中所有结点和所有能使G成为完全图的添加边组成的图，称为G相对于完全图的补图，简称G的补图，记作•问题：G相对于完全图的补图是否可能是G的生成子图？•定义11：设G’=V’,E’是G=V,E的子图，若给定另外一个图G”=V”,E”使得E”=E-E’，且V”中仅包含E”的边所关联的结点。则称G”是子图G’的相对于G的补图。•注：相对于完全图的补关系是对称的；相对于任意图G的补关系则不是对称的。•例子G91.图的基本概念•定义12：设图G=V,E及图G’=V’,E’，如果存在双射f：V→V’，使得e=(vi,vj)是G的一条边，当且仅当e’=(f(vi),f(vj))是G’的一条边，则称G与G’同构，记作GG’。•例子•图同构的必要条件：结点数相同；边数相同；度数相同的结点数目相同。•问题：代数系统之间的同构与图同构之间的关系？101.图的基本概念•定理5：设G＝V,E是简单图，，则G中必包含一个三角。•问题：定理5给出的边界是否是紧的？•为便于讨论图算法，给出算法复杂性的几个基本定义•定义13：对于给定的函数g(n)，定义如下的函数集合O(g(n)):={f(n)|存在正常数c和n0，使得对于所有n≥n0，0≤f(n)≤cg(n)}，称g(n)为O(g(n))中任意函数f(n)的渐近上界（注：一般要求g(n)和f(n)定义于N）4||,||2nEnV111.图的基本概念•注：算法的时间复杂性，可通过计算开销对于输入长度的函数的渐近上界来刻画•例子：给定图G=V,E，构造一个求△(G)的算法，使其时间复杂性的渐近上界为O(n+m)，这里n=|V|，m=|E|。•定义14：如果一个算法的时间复杂性的渐近上界是输入长度的多项式函数，则称该算法是有效的，•思考题：尝试给出一个判定图同构的算法，说明该算法的在时空效率方面是否是有效的。122.路与回路•定义1：给定图G=V,E，设v0,v1,…,vn∈V，e1,e2,…,en∈E，其中ei是关联于结点vi-1，vi的边，交替序列v0e1v1e2…envn称为结点v0到vn的路(walk)。•注：v0和vn分别称作路的起点和终点。边的数目n称作路的长度。当v0=vn时，这条路称作回路(closedwalk)。若一条路中所有的边e1,e2,…,en均不相同，称作迹(trail)。起点和终点重合的迹称为闭迹(closedtrailorcircuit)。若一条路中所有的结点v0,v1,…,vn均不相同，称作通路(path)。闭的通路，即除v0=vn外，其余的结点均不相同的路，称作圈(cycle)。132.路与回路长度为L的通路记为PL长度为L的圈记为CL，C3称为三角，C4称为四边形，C5称为五边形…简单图路中，路可以由其结点序列v0v1…vn表示；结点数大于1的路也可由边序列e1e2…en表示。•例子•定理1：无向图G=V,E的边集合E可以被划分为一组圈，当且仅当V中的任意结点v的具有偶数度。•问题：定理1如何推广到有向图？142.路与回路•定理2：在一个具有n个结点的图中，若从结点vj到结点vk存在一条路，则从vj到vk必存在一条不多于n－1条边的通路。•定义2：无向图G中，结点u和v之间若存在一条路，则称结点u与结点v是连通的(connected)。注：结点之间连通性是G的结点集V上的等价关系；由此等价性，可决定V上的一个划分V1,V2,…,Vk，使得属于同一分块的结点之间互相连通，将这样的分块称为图G的一个连通分支(connectedcomponent)。以W(G)表示图G的连通分支数•例子152.路与回路•定义3：若图G只有一个连通分支，则称G是连通图•在图中删除点v，即是把v以及与v关联的边都删去；在图中删除边e，仅需把该边删去。•定义4：设无向图G＝V,E为连通图，若有点集V1V,使图G删除了V1的所有结点后，所得的子图不是连通图，而删除了V1的任何真子集后，所得的子图仍是连通图，则称V1是G的一个点割集。若某一结点构成点割集，则称其为割点(cutvertex)。•问题：一个图是否可能有多个点割集？•注：若G不是完全图，定义k(G)=min{|V1||V1是G的点割集}为G的点连通度。k(G)是为了产生一个不连通图需要删去的最少结点数。不连通图或平凡图的点连通度约定为0，存在割点的图的点连通度为1。162.路与回路完全图Kp中，删去任何m个(mp-1)点后仍是连通图，但是删去个p-1个点后产生了一个平凡图，故定义k(Kp)为p-1•定义5：设无向图G＝V,E为连通图，若有边集E1E,使图G删除了E1的所有边后，所得的子图是不连通图，而删除了E1的任一真子集后，所得的子图是连通图，则称E1是G的一个边割集。若某一个边构成边割集，则称该边为割边（或桥bridge）。•问题：一个图是否可能有多个边割集？•注：非平凡图G的边连通度定义为：λ(G)=min{|E1||E1是G的边割集}。λ(G)是为了产生一个不连通图需要删去的最少边数。对平凡图G或一个不连通图G，定义其λ(G)为0•问题：λ(Kp)=?172.路与回路•定理3：若W(G)=n，在G中删除一边获得G’，则W(G’)≤n+1•定理4：对于任何一个图G，有k(G)≤λ(G)≤δ(G)•定理5：一个连通无向图G中的结点v是割点存在两个结点u和w，使得结点u和w的每一条路都通过v。•定义6：若u可达v，它们之间所有路中，最短路的长度称为结点u和v之间的距离，记作du,v，若从u到v不可达，du,v＝∞。称D=max{du,v|u,v∈V}为图G=V,E的直径•注：du,v≥0，du,u＝0du,v＋dv,w≥du,w182.路与回路对于无向图，d(u,v)=d(v,u)•定义7：在简单有向图G中，任一对结点间，至少有一个结点到另一个结点是可达的，则称这个图是单侧连通的。若对于图G中任一对结点两者之间是相互可达的，则称这个图是强连通的。若在图G中略去边的方向，将它看成无向图后，图是连通的，则称该图为弱连通的。•例子•注：若图G是强连通的，则必是单侧连通的；若图G是单侧连通的，则必是弱连通的。以上两命题，其逆不真。192.路与回路•定理6：一个有向图是强连通的当且仅当G中有一个回路，它至少包含每个结点一次。•定义7：在简单有向图中，具有强连通性质的极大子图称为强分图；具有单侧连通性质的极大子图称为单侧分图；具有弱连通性质的极大子图称为弱分图。•问题：简单有向图是否可能有多个强（弱、单侧）分图？•定理7：在有向图G＝V,E中，它的每一结点位于且只位于一个强分图中。202.路与回路•定义8：如果图G=V,E的结点集合V可划分为两个非空集合V1、V2的并，使得任意e∈E均连接了分处V1和V2中的两个结点，则称其两分图（bipartitegraph）。•例子•定理8：简单图G=V,E是两分图iff不包含任何奇圈。•定理9：若无向图G恰有两个奇数度结点，则此两点间必有一条路•定理10：设G＝V,E是简单图，，则G中必包含一个三角。•问题：定理5给出的边界是否是紧的？2||,||4nVnE213.图的矩阵表示•定义1：设G=V,E是一个简单图，它有n个结点V={v1,v2,…vn}，定义n阶方阵A(G)=(aij)为G的邻接矩阵：若G是无向图，aij=1，iffviadjvj，aij=0，ifvinadjvj或i=j，这里adj表示邻接，nadj表示不邻接。若G是有向图，aij=1iffvi，vj∈E•注：如无特别说明，只考虑简单图的邻接矩阵。无向图G的邻接矩阵A(G)是对称的；有向图的邻接矩阵则一般不对称。对于有向图，邻接矩阵第i行的元素和等于结点vi的出度；第j列的元素和等于结点vj的入度。223.图的矩阵表示•例子•定义2：将n阶方阵A的列作一置换，再将相应的行作同样的置换，得到一个新的n阶方阵A’，则称A’与A置换等价。•注：任意置换可分解为一组初等置换的复合；任意置换矩阵可表示为一组初等置换矩阵的乘积。所以任意置换可由置换矩阵表示置换等价是n阶布尔矩阵集合上的等价关系。图的结点按不同次序所写出的邻接矩阵是彼此置换等价的，可取图的任一邻接矩阵作为该图的矩阵表示233.图的矩阵表示•可由图的邻接矩阵求得图上点与点之间路的数目：设有向图G的结点集合V={v1,v2,…vn}，它的邻接矩阵为A(G)=(aij)n×n，则从结点vi到结点vj的长度为2的路的数目为：ai1a1j+ai2a2j+…+ainanj=∑kaikakj这