数模-图论及其算法.ppt

图论及其算法 南京理工大学理学院 肖 伟 一、背景 问题哥尼斯堡（Knigsberg）七桥问题 哥尼斯堡有一条河，河中有一个岛，共建七座桥联系被河隔开的四块陆地（如图） 。城里人希望做一次散步，从一点出发，经过每座桥一次仅一次，再回到原出发点 。1736年 Euler否定了该问题。 A C D A C B D B 二、图的定义 一个图G是一个三重元素组， V(G)是图的顶点集合，E(G)是图的边的集合，G 是从边集E到顶点偶对集合上的函数。顶点集通 常用v表示，边集通常用e表示。如图所示。 a b c d e1 e2 e3 e4 e5 图1 图2 v1 v2 v3 e1 e2 e3 e4 三、各种图的定义 如果图的边e所对应的顶点偶对是有序的，则称是e有向边， 否则为无向边。对有向边e=，顶点a称为边e的始点，b是终点 ，他们统称为边e的端点。顶点a、b称为邻接的，e称为是关联结点 a、b的。不与任何顶点邻接的顶点称为孤立点。全由孤立点构成的 图称为零图。如果一条边的始点和终点相同，则称此边为环（自回 路）。如果两个结点之间有多余一条边，则将他们称为平行边。两 结点之间边的条数称为边的重数，没有边时，重数为0。 1. 如果图中每一条边都是无向边，则称为无向图，如图1。 2. 如果图中每一条边都是有向边，则称为有向图，如图2。 3. 含有平行边的图称为多重图。非多重图称为线图。无环的线图 称为简单图。 4. 如果图G中每条边e都指定了一个数相对应，记为W(e)，则称此 图为赋权图。 四、图的基本概念 1. 结点的度 在有向图中，以顶点v为始点的边的数目称为结点v的引出次数（出度 ），记为deg+(v)=d+(v)；以顶点v为终点的边的数目称为结点v的引 入次数（入度），记为deg-(v)=d-(v)；结点v的引出次数和引入次数 之和称为结点v的次数（度数），记作deg(v)=d(v)；在无向图中， 结点v的次数就是与结点v相关联的边的条数，记作deg(v)=d(v)；对 于孤立点v，显然deg(v)=0。n个结点和m条边的图称为(n,m)图。 定理 1 设G是一个(n,m)无向图，其结点集V=v1,v2,vn，则 说明：如果为无向图，则结论为 定理 2 任何图的奇次结点有偶数个。 2. 正则图的定义：图中所有结点的度数均相同；对每个结点度 数为k的图，称为k-正则图。 3. 图的同构：给定两个图G1=和G2=，如果存在从 V1到V2的一一映射，使对任意a,bV1，边(a,b)E1，当且仅 当(a) ，(b) E2 ，并且(a,b)和(a) ,(b)有相同 的重数。 说明：如果两个图同构，则应有如下结论：1）定点数同；2）边 数同；3）度数相同的结点数相同。 问题：到现在为止，还没有可行的办法判定两个图同构？ 4. 图的运算： 给定两个图G1=和G2=，定义： 1）G1与G2的并G3=为V3=V1V2，E3=E1E2，记为G3=G1G2 ； 2）G1与G2的交G3=为V3=V1V2，E3=E1 E2，记为G3=G1G2 ； 3）G1与G2的差G3=为E3=E1-E2，V3=(V1-V2) E3中相关联的点 记为G3=G1-G2 ； 4）G1与G2的环和G3= G1G2 ， G3=(G1G2 )-(G1G2 )； 5）删除边的运算； 6）删除图的顶点的运算（删除顶点及其相关联的边）。 图 3 a b c G1 b a c d G2 e2 e1 e3e1 e5 e4 a b c G1删去边e2 e3e1 a b e1 G1删去结点c a b d c e1e3 e5 e2 e4 G1G2 b a c e1 G1G2 bc a d e2 e4 e3 e5 G1G2 b c a G1-G2 5. 子图：给定两个图G1=和G2=。 1）如果V2V1且E2E1，则称G2是G1的子图。如果G2G1，则G2是G1的 真子图。 2）如果G1=G2且E2 E1，则称G2为G1的生成子图。 3)由图的一些边E0 E与其所有相关联的结点组成的图，称为由边集 E0导出的子图。 4）由图G=中的一些顶点集V0 V 和E中的两端点都在V0中的边 所组成的子图称为由顶点集V0导出的子图。 6. 完全图：如果图中任意两结点之间都存在唯一的一条（有向）边 ，则称此图为完全图。 注意：如果是无向图，则任意两结点之间只有唯一一条边；如果是 有向图，则任意两结点之间存在方向相反的不同两条边。 7. 补图：给定线图A=，设|V|=n，定义图A的补图 ，其中E0是V生成的完全图的边删除E所得。 8. 一个无向图，如果同构于它的补，则该图称为自补图。 9. 图的支配集：对于图G的一个顶点子集，如果G中不在该顶点集中 的结点至少与该集中某结点相邻，则称该顶点集为图G的支配集。 尤其，如果支配集的任何真子集都不是图G的支配集，则称该集为 最小支配集。 10. 图的独立集：对于图G的一个顶点子集，如果其中任何两点都不 相邻，则称该点集为图的独立集。对于一个独立集，如果任意增 加图中的一个点后，此集不再独立，则称该独立集为最大独立集 。 五、路径和回路 1. 路径图中一个点边交替序列v0e1v1e2v2envn称为图的一条路径， 如果是有向图，则须保持方向的一致，即vk-1和vk分别是ek的始点和 终点；始点与终点重合的路径称为回路；如果路径中的边不重复出现 ，则称此路径（回路）为简单 路径（简单回路）；如果路径中同 一顶点不重复出现，则称此路径（回路） 为链或基本路径（基本回路）。 在图4中，有下列结论： 1） P1=v1e1v2e7v5 基本路径，简单路径； 2）P1=v2e2v3e3v3e4v3 简单回路，非基本路径； 3） P3=v4e6v2e7v5e8v4e6v2e2v3 路径； 4） P4=v2e7v5e8v4e6v2 基本回路。 v1 v2 v3 v4 v5 e4 e1 e2 e3 e5 e 6 e7 e8 图4 2. 路径P中所含边的条数称为路径P的长度。 3. 图中两结点 v1 、v2之间最短路径的长度称 为从v1到v2的距离，记为d(v1 ，v1)。如果从 v1到v2的路径不存在，则d(v1 ，v1) =。 定理 3 给定简单图G=(V,E)，如果|V|=n，且 存在从v1到v2的路径，则存在一条从v1到v2的 长度不超过n-1的基本路径。 定理 4 如果图G=(V,E)，|V|=n中，存在从v1 到v2的简单回路，则存在一条长度不超过n-1 的基本回路。 六、特殊图 1. 给定图G=(V，E)，设v1 ， v2 V。如果存在从v1到v2的路径，则称v2 从v1可达。如果图中任意两顶点都可达，则称此图为连通图。在有向 图中，对任意两结点v1 ， v2 ，如果存在从v1到v2的有相路径，则称此 图为单向连通图。如果任意两点之间可以互相可达，则称此图为强连 通图。有向图的底图是连通的，则称此图为弱连通的。 2. 给定有向图G=(V，E)，设G0是G的子图，如果G0是强连通的（单向连通 的、弱连通的），并且不存在包含G0的更大子图保持这种连通性，则 称图G0是G的强分图（单向分图、弱分图）。 注意： 1）强（弱）连通分图和连通分图是给定图顶点集的价关系。 2）无向图和弱连通图中，这种顶点集的等价关系也同时将图中的所有 边划归到不同的分图中。对强连通图而言，这种情况不成立，即一条 边所关联的两个端点可能不在同一分图中（例如单向边）。 3）单向分图不是原图顶点集的等价关系，因为传递性不成立。如图4， v3到v4可达，v5到v4可达，但v3到v5不可达， 3. 赋权图，给定图G=(V，E)，给图中每条边e都赋一个实数值 w(e)形成赋权图G=(V，E，W )。图中路径P的长度W(p)定义为 路径中每条边的权之和。图中任意两点u、v之间的距离定义为 其中P是u到v的路径。如果u与v之间不可达，则定义d(u,v)= 。 说明： 最短路问题:给定一个赋权图，通常需要求两点之间的最短距 离，这就是所谓最短路问题。尤其是需要讨论给顶点（源）到 其它各点之间的最短路。 4. 树 A. 树的定义：连通而不含回路的无向图称为无向树，简称树。连 通分支数大于等于2，且每个连通分支均是树，这样的图称为森林 。 B. 树的等价定理 设G=(V，E)，|V|=n，|E|=m，则下列各命题等价。 （1）G连通而不含回路； （2）G的每对顶点之间存在唯一的路径； （3）G连通，且n=m+1; （4）G中无回路，且n=m+1； （5）G中无回路，但在G中任两个不相邻的顶点之间增加一条边， 就形成唯一的一条回路； （6）G是连通的，且每条边都是桥； （7）G是连通的，但删除任意一条边后，G都不连通。 C. 生成树的定义： G=(V，E)是无向连通图，T是G的生成子图，并 且T是树，则称T是G的生成树。对于赋权图G=(V,E,W)，如果生成 树T满足： 则称为最小生成树。 D. 最小生成树的算法 算法I（避圈法）： （1）在赋权图G=(V,E,W)中取权值最小的边e1，加入树T中； （2）假设已经找到树T的边集E(T),在边集EE(T) 中取最小权值 的边ek，如果加入树T的边集E(T)后不构成圈，则记树T的边集为 E(T)+ek；如果加入后构成圈，则在边集E-E(T)-ek中寻找最 小权的边，再加入树T中，直到不构成圈。 （3）重复（2），直到|E(T)|=n-1. 算法II(破圈法)，此法与算法I类似，只是每次在图G中任选一个 圈，然后删除圈上最大权重的边，直到无圈为止。 七、Dijkstra算法 给定赋权图G=(V，E，W)及其源a0，点a0到图中其它各点最短路算法为： （1）把顶点集V分成两部分S和T，S为已标集合，T为剩余顶点集，令S=a0，T=V-S 。 （2）在T中找出一点u使得 d(a0,a1)=min w(x,a0)，其中x为T中任意结点。记 S1=Sa1， T1=V- S1 。并在点a1处标记 d(a0,a1)。 （3）设已找到Si=a0，a1，a2，ai，并且d(a0,ak)（k=1,2, ,i）已知。在Ti=V-Si中 找出点ai+1，使得 d(a0,ai+1)=mind(a0,ak)+ w(ak,u)，akSi，u Ti中的任意顶点。记Si+1=a0，a1，a2 ，ai+1，并在点ai+1处标记 d(a0,ai+1)， Ti+1=V-Si+1 。 （4）如果Ti+1=，则停止。否则重复（3）。 范例：赋权图如图5，最短路如图6。 a v1v2 v3v4 2 3 4 6 5 10 7 图5 1 2 a v1 v2 v3v4 2 3 6 5 10 7 图6 1 2 2 3 5 4 7 4 八、Euler图 1. 定义：通过图中每条边一次且仅一次的路径称为Euler路径；如果是 回路，则称Euler回路；具有Euler回路的图称为Euler图。 2. 判定Euler图的充要条件。 定理5 简单图G具有一条Euler路径的充要条件是G具有零个或两个奇 数次的顶点。 推论：无向简单图是Euler图，当且仅当图中每个顶点的度数为偶数。 定理6 有向图G=(V,E)具有Euler回路，当且仅当任意vV有 。有向图具有Euler路径，当且仅当可能除两个顶点以外的所有顶点 有 ，例外的两个顶点中，引入次数与引出次数差1。 应用：回答哥尼斯堡七桥问题。 九、Hamilton图 给定无向图G=，通过图中每个结点一次且仅一次的路径（ 回路）称为Hamilton路径（回路、圈）。具有哈密尔顿回路的图 称为哈密尔顿图。 定理7 设G=是Hamilton图，则对V的每个非空真子集S均成立 这里|S|表示顶点集S的点数，(G-S)表示G删去点集S后得到的 图的连通分图个数。 定理8 设G=，|V|=n2，是简单图。如果在G中每一对顶点的 次数之和大于等于n，则在G中存在一条Hamilton圈。 推论 8-1 在简单图G=中，如果vV，有deg(v)n/2，则该 图是Hamilton图 十、巡回售货员问题 一个售货员从一个城市出发，经历n个城市售货后返回出发城市。 如果已知任意两个城市都是相同的，且城市vi和vj之间的距离为 W(i,j)，则需要设计一个算法找出售货员的最短路径。下面给 出一种算法最邻近算法： （1）任取一点作为始点，找出与始点最近的点，形成只有 一条边的初始路径。 （2）设顶点x为最新加入路径的点，从不在路径中的所有点 中，选一个与x最近的点，将其与x连接的边加入路径中。 （3）重复步骤（2），直至所有点都在这条路径中，将最后 加入的点与初始点连接的边加入路径中，由此获得回路。 十一、 图的矩阵表示 1. 图的邻接矩阵给定有向线图G=，V=v1，v2，vn，图 的邻接矩阵A=(aij)nn定义为 说明： 1）图的邻接矩阵不唯一，但可通过行列变换进行相互转换。理解矩 阵同构。 2）有向图G自反的，当且仅当aii=1。（vi到vi有边） 3）有向图G反自反的，当且仅当aii=0。（ vi到vi无边） 4）有向图是对称的，当且仅当aij=aji。（ vi到vj有边，且vj到vi有 边） 5）有向图是反对称的，当且仅当aij=1aji =0。（vi到vj有边，且vj 到vi无边） 6）零图零矩阵。 7）图中每点都有环，但无边单位矩阵。 8）图G=有邻接矩阵A，定义G的逆图G-1=，其邻接矩阵 为AT。 9）无向图同样有邻接矩阵。 2. 图的邻接矩阵运算含义 1）AAT的含义：计AAT=(bij)， bij表示起始于i、j两点且终点相同 的结点数。尤其bii=deg+(vi)。 2）ATA的含义：计ATA=(bij)， bij表示终止于i、j两点且起点相同 的结点数。尤其bii=deg-(vi)。 3）An的含义：计An=(aij(n)。a）n=1时， aii=1表示存在边 ；b）n=2时， aij(2)表示存在从vi到vj的长度为2的不同 路径数；c）一般An的含义为， aij(n)表示存在从vi到vj的长度为 n的不同路径数。 4）Br=A+A2+Ar的含义：bij表示存在从vi到vj的长度小于等于r 的不同路径数。 3. 可达性矩阵给定有向线图G=，V=v1，v2，vn，假 定结点已排序，图的可达性矩阵P=(pij)nn定义为 说明： 1）如果已知Bn ，则只需将其中非零元素写成1，便得可达性 矩阵P。 2）强分图等于PPT。 十二、二部图 1. 二部图的定义：如果无向图G=的顶点集合V可以划分为两个子集 X和Y，使G中的每条边的两个端点分属于X和Y中，则称G为二部图或偶 图，又记G=。尤其是，如果X中的每一顶点都与Y中的每一顶 点相邻接，则称G为完全二部图，计为Kmn，其中|X|=m，|Y|=n。 定理 9 无向图为二部图的充分必要条件为图中所有回路的长度都为偶数 。 2. 最大匹配：给定二部图G =，如果E的子集M中的边无公共端点 ，则称M为二部图的一个匹配。含有最多边数的匹配称为图的最大匹 配。 3. 交替链：如果二部图中的一条链由不属于匹配M的边和属于M的边交替 组成，且链的两端点不是M中边的端点，则称链为图中关于匹配M的交 替链。 范例：如图7。图的匹配 M1=(x1,y5), (x3,y1), (x4,y3)。 交替链(x2,y1, x3,y4)。 x1x2x3x4 y1 y2y3 y4y5 图 7 4. 交替链算法 给定匹配M，首先将X中端点不在M中的点进行标记，用*标记。然 后进行如下操作： （1）选X中标有*的点，如x，用x标记端点yY，且(x,y)M。重复 这一过程。 （2）选Y中新标记的点，如y，用y标记端点xX，且(x,y)M。重 复这一过程。 （3）终止原则：M中没有Y中点可标记。 5. 最大匹配算法 给定图G的一个匹配M。 （1）找出关于M的交替链P1； （2）删去P1中M的边，添加P1中不属于M的边，形成新集合M1，它是 图G的匹配； （3）重复这一过程直至没有关于M的交替链，便可获得最大匹配。 十三、平面图 1. 平面图 平面图的定义：给定无向图G=，如果能把它图示在一个平 面上，使得边只与顶点相交，则称此图为平面图。 注意： 1）将平面图“图示在平面上”，也可说成“把平面图嵌入一 个平面上”。 2）平面图将平面分成了独立的面，面的边界为图的边组成。 如果面的面积有限，该面称为有限面，否则，称为无限面。 无限面唯一。 Euler公式：给定平面图G=，|V|=n，|E|=m。设平面图的 面有k个，则有 n-m+k=2。 定理 10 给定任意简单平面图(n,m)（n4）都有 推论 10-1 K5是非平面图。 定理 11 每个面用四条边或更多边围成的任何连通平面图都有 推论 11-1 K3,3不是平面图。 2. 对偶图 给定平面图G=，构造一个新图G*=如下：V*是图G的 面数，如果G的两个面（对应G*的两个顶点）有公共边，则将G*的 这两个顶点相连形成一个边。这样形成的图G*称为图G的对偶图。 定义 无向图G的顶点子集S称为图的割集，当且仅当，删去S中的所 有边时，G的连通分图个数将增加，而删去任何S的真子集都不会 增加G的连通分图个数尤其是，|S|=1时，我们称这条边为G的桥 边 3. 五色问题 对图中每个顶点着色，如果任何两相邻顶点的颜色都不相同，则 称这种着色为图的正常着色 四色猜想（定理）用四种颜色可以给任何简单平面图正常着色。 十四、图论小结 一、图的主要概念 1.简单图：无环、无向、无平行边、连通的图； 2.赋权图（有向图）：图中每条边都赋有实数权； 3.正则图：图中各结点次数相同，k-正则图图中各结点次数都为k； 4.子图：给定图G=，如果G0=满足V0V，E0 E，则称图G0是图G的子图 。尤其是，如果V0=V，则称图G0是图G的生成子图；如果子图G0中没有孤立结点， G0 由E0唯一决定，则称G0由边集E0导出的子图；如果任意两结点u,v V0 ,都有u,v E0 ，则称G0由顶点集V0 导出的子图； 5.完全（有向）图：图中任意两顶点之间都有边（相反方向的两条边）相连； 6.Euler图：具有Euler回路的图； 7.Hamilton图：具有Hamilton圈