图论与网络流理论.ppt

《图论与网络流理论.ppt》由会员分享，可在线阅读，更多相关《图论与网络流理论.ppt（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图论与网与网络流理流理论二一二年十月十日第一章 图的基本概念1.1 图的基本概念1.2 最短路问题1.3 数及其性质1.4 生成树与最小生成树1.5 图的中心与中位点1.6 图的矩阵表示1.1 图的基本概念1.图（graph）定义：一集元素及它们之间的某种关系称为图。一个图G是指一个二元组(V(G),E(G)，其中:1）是非空有限集，称为顶点集，2）E(G)是顶点集V(G)中的无序或有序的元素偶对组成的集合，即称为边集,其中元素称为边.图G的阶是指图的顶点数|V(G)|,用v来表示；图的边的数目|E(G)|用 来表示.表示图，简记 用也用来表示边2 图的图示 通常，图的顶点可用平面上的一个点来

2、表示，边可用平面上的线段来表示（直的或曲的），这样画出的平面图形称为图的图示。3 一些术语和概念1.边和它的两端点称为互相关联。2.与同一条边关联的两个端点称为相邻的顶点，与同一个顶点关联的两条边称为相邻的边。3.两端点重合的边称为环边。4.若一对顶点之间有两条以上的边联结，则这些边称为重边。5.既没有环边也没有重边的图，称为简单图。6.任意两顶点都有一条边的简单图,称为完全图。记为Kv.7.边集为空的图称为空图。8.边集为空且只有一个顶点的图成为平凡图。9.边集和顶点集都为空的图称为零图。10.图G中顶点v所关联的边的数目（环边计两次）称为顶点v的度，记为dG(v)或d(v)。11.图G的最

3、大度：(G)=maxdG(v)|v V(G);12.图G的最小度：(G)=mindG(v)|v V(G);13.各个顶点的度都相等的图称为正则图。每个顶点的度都等于k的图称为k-正则图。14.设G是一个图，以V(G)为顶点集，以(x,y)|(x,y)E(G)为边集的图称为G的补图，记为定理1.1.1 对任何图G，其各顶点度数之和等于边数的2倍，即证明：按每个顶点的度来计数边，每条边恰数了两次。推论1.1.1 任何图中，奇数顶点的个数总是偶数（包括0）。4 子图5 图的并、联和对称差设G1、G2是两个图：G1、G2的并是指图（V1U V2，E1U E2），记为G1UG2若V1 V2=，则G1UG

4、2称为不交并（和）记为G1+G2A、B两集合，(A B)(A B)称为A与B的对称差。设两个相同顶点集的图G1=（V，E1）；G2=（V，E2），则图（V，E1 E2）称为G1、G2的对称差。6 路和圈图G中一个点边接续交替出现的序列称为图G的一条途径，其中 分别称为途径W的起点和终点，W上其余顶点称为中途点。图G中边不重复出现的途径称为迹。图G中顶点不重复出现的迹称为路。图G中起点和终点相同的途径称为闭途径。图G中边不重复出现的闭途径称为闭迹，也称为回路。中途点不重复的闭迹称为圈。注：（1）途径（闭途径）、迹（闭迹）、路（圈）上所含的边的个数称为它的长度。（2）简单图G中长度为奇数和偶数的圈

5、分别称为奇圈(odd cycle)和偶圈(even cycle)。（3）对任意，从x到y的具有最小长度的路称为x到y的最短路（shortest path），其长度称为x到y的距离(distance)，记为d(x,y)。（4）简单图G中最短圈的长度称为图G的围长(girth)，最长圈的长度称为图G的周长(circumference)。例1.1.2 设G是一个简单图，若(G)2，则G中必含有圈。证明：设G中的最长路为P=v0v1vK。因d(v0)2，故存在与相异的顶点v与相邻。若v P，则得到比P更长的路，这与P的取法矛盾。因此必定定v P，从而G中有圈。证毕。例1.1.3 设G是简单图，若(G)

6、3,则G必有偶圈。证明：设P=v0v1vK 是G 的最长路。因为d(v0)3，所以存在两个与v1相异的顶点v,v与v0相邻。v,v必都在路P 上，否则会得到比P 更长的路。无妨设v =vi,v=vj,(2i，jk，ij)。若i,j中有奇数，比如i 是奇数，则路P上v0到vi 的一段与边v0 vi 构成一个偶圈；若i,j都是偶数，则路P上vi到vj的一段与边v0 vi 及v0 vj 构成一个偶圈。证毕。7 二部图二部图(bipartite graph)：若图G的顶点集可划分为两个非空子集X和Y，使得G的任一条边都有一个端点在X中，另一个端点在Y中，则称G为二部图（或偶图），记为G(X Y,E)或

7、G=(X,Y)，(X,Y)称为G的一个顶点二划分。完全二部图(complete bipartite graph)：在二部图G(X Y,E)中，若X的每个顶点与Y的每个顶点有边连接，则称G为完全二部图；若|X|=m，|Y|=n，则记此完全二部图为 Kmn 。定理1.1.2 一个图是二部图当且仅当它不含奇圈。例1.1.5 判断下列判断下列图是不是二部是不是二部图。解：Herschel 图的一个顶点二划分如下：可见 Herschel 图是一个二部 图。Peterson 图中含有奇圈，因此不是二部图。8 连通性图中两点的连通：如果在图G 中u，v 两点间有路相通，则称顶点u，v 在图G 中连通。连通图

8、（connected graph）：若图G 中任二顶点都连通，则称图G 是连通图。图的连通分支（connected branch,component）：若图G 的顶点集V(G)可划分为若干非空子集V1 ,V2,V，使得两顶点属于同一子集当且仅当它们在G中连通，则称每个子图GVi为图G的一个连通分支（i=1,2,）注：（1）图G 的连通分支是G 的一个极大连通子图。（2）图G连通当且仅当1。定理1.1.3 若图G连通，则例例1.1.6 设有有2n 个个电话交交换台，每个台与至少台，每个台与至少n个台有个台有直通直通线路，路，证明明该交交换系系统中任二台均可中任二台均可实现通通话。证明：构造图G

9、如下：以交换台作为顶点，两顶点间连边当且仅当对应的两台间有直通线路。问题化为：已知图G有2n 个顶点，且(G)n，求证G连通。事实上，假如G 不连通，则至少有一个连通分支的顶点数不超过n。在此连通分支中，顶点的度至多是n 1。这与(G)n矛盾。证毕。例例1.1.7 若若图中只有两个奇度中只有两个奇度顶点，点，则它它们必必连通。通。证明：用反证法。设u、v为仅有的两个奇度顶点。假如u与v不连通，则它们必分属于不同的连通分支。将每个分支看成一个图时，其中只有一个奇度顶点。这与推论1.1.1 矛盾。证毕。9 图的同构我们已经知道，同一个图可以有不同形状的图示。反过来，两个不同的图也可以有形状相同的图

10、示。比如：易见G1 和G2 的顶点及边之间都一一对应，且连接关系完全相同，只是顶点和边的名称不同而已。这样的两个图称为是同构的同构的(isomorphic)。定定义1.1.1 对两个图G=(V(G),E(G)与H=(V(H),E(H)，如果存在两个一一映射：:V(G)V(H)，:E(G)E(H)，使得对任意e=(u，v)E(G)，都有(u),(v)E(H)且(e)=(u),(v)，则称图G与H同构，记为G H。两图同构，首先它们的阶必须相等，边数必须相等；其次要有相同的环边、重边及圈的状态；还应保持顶点的度，即在同构映射下相对应的顶点必须有相同的度。这些都是两图同构的必要条件，可用来判断两图不

11、同构。为判定两图同构，一般要按定义构造出两图顶点间的一一映射，然后检验它是否保持邻接关系。有时也可根据图的特点使用特殊方法。1.2 最短路问题1、赋权图对图G的每条边e，赋以一个实数w(e)，称为边e的权。每个边都赋有权的图称为赋权图。权在不同的问题中会有不同的含义。例如交通网络中，权可能表示运费、里程或道路的造价等。2、最短路问题最短路问题：给定赋权图G及G中两点u,v，求u到v的具有最小权的路（称为u到v的最短路）。注：赋权图中路的权也称为路的长，最短(u，v)路的长也称为u，v间的距离，记为d(u，v)。最短路问题是一个优化问题，属于网络优化和组合优化的范畴。对这种优化问题的解答一般是一

12、个算法。最短路问题有很多算法，其中最基本的一个是Dijkstra算法3、Dijkstra算法定理 1.2.1 Dijkstra 算法结束时，对任一个顶点v，其标号l(v)恰是v0 到v 的最短路的长。定理1.2.2 Dijkstra 算法的计算复杂度为O(2)。1.3 树及其性质不含圈的图称为森林(forest)，不含圈的连通图称为（tree）。定理1.3.1 下列命下列命题等价：等价：（1）G 是树；（2）G 中无环边且任二顶点之间有且仅有一条路；（3）G中无圈且=1；（4）G连通且=1;（5）G连通且对任何e E(G)，G e不连通；（6）G无圈且对任何e E(G)，G+e恰有一个圈。1.

13、4 生成树与最小生成树最小生成树问题是一个优化问题，需要设计优化算法寻找其最优解。求解最小生成树问题的算法较多，本节主要介绍Kruskal 算法和Prim 算法。（一）Kruskal算法（Joseph Bernard Kruskal,1956）1.算法思想：先从图G 中找出权最小的一条边作为最小生成树的边，然后逐次从剩余边中选边添入最小生成树中，每次选边找出不与已选边构成圈的权最小的一条边。直至选出(G)1条边为止。(二)Prim算法（Robert Clay Prim，1957）（三）Prim 算法的矩算法的矩阵实现求最小求最小树的的权矩矩阵法法最后得到的最小生成树由边v1v2、v1v4、v4v3、v4v5构成，其权为20+25+10+15=70。1.5 图的中心与中位点求图的中心和重心的算法1.6 图的矩阵表示