离散数学-图论.ppt

图论内容提要起源于一些数学游戏：迷宫问题、博奕问题、马的行走路线等在计算机科学等领域有广泛的应用直观、简洁等特点基本内容：图的基本概念、路径与回路、Euler图、Hamilton图、平面图、树等。图论抽象的图一个图G是一个三元组V(G),E(G),G，其中V(G)是一个非空的结点集合，E(G)是边集合，G是从边集合到结点集合的函数。如果把G总是看成是结点之间的一种关联，并在E(G)中清楚地描述这种关联，那么一个图G通常简记为一个二元组序偶形式G=V，E，其中V是一个非空结点集合，E是连接结点的边的集合。图论图的抽象性及方向性图的结点与连接都是一种抽象的表示，其位置与长度没有意义。如果边是两个结点之间的有序偶，则称该边是有向边，记为vi,vj。包含有向边的图为有向图。如果边是两个结点之间的无序偶，则称该边为无向边，记为（vi,vj）。包含无向边的图为无向图。注意：既有有向边又有无向边的图称为混合图。图论邻接点与特殊的图在一个图中，若两个结点由一条边关联，则称这两结点是邻接点。不与其它任何结点相关联的结点称为孤立结点。仅由孤立结点组成的图称为零图。仅由一个结点组成的图称为平凡图。任意两个结点都相邻的图称为完全图。图论思考有n个结点的无向完全图Kn有多少条边？有向图的情形呢？图论邻接边关联于同一结点的两条不同的边则称为邻接边。关联于同一结点的两条相同的边则称为 自回路或环。环既可以是有向的，也可以是无向的。图论有向图的度设vi,vj是有向图G=V，E中的任意一条有向边，vi是该边的起始结点，vj是终止结点。在有向图G=V，E中，以一结点为起始结点的边的个数称为该结点的出度；以一结点为终止结点的边的个数称为该结点的入度。一结点的出度和入度之和称为该结点的度数，记作deg(v)。图论有向图度数的性质在任何有向图中，所有结点的入度之和等于所有结点的出度之和，并等于图中边的个数。孤立结点的入度和出度均为0有向环的对应结点的入度和出度均增加1图论无向图的度在无向图G=V，E中，与结点相关联的边的个数称为该结点的度数，记作deg(v)。在无向图G=V，E中，结点度数的总和是边数的两倍。在无向图G=V，E中，度数为奇数的结点必定是偶数个。图论补图给定一个图G=V，E，构造另一个图，它的结点集合与G相同，而边的集合则为相同完全图中边集合与E的差集，称该图为原图G相对于完全图的补图，记作G。图论子图设G=V，E是一个图，如果有另一个图G=V，E，使得V是V的子集，E是E的子集，则称G是G的子图。如果G的子图G包含G的所有结点，则称该子图为G的生成子图。图论差图设G=V，E是G=V，E的子图，若给定另外一个子图G“=V”，E“使得E“=E-E，且V”中仅包含E“的边所关联的结点，则称G“是图G与子图G的差图，或称子图G相对于图G的补图，记作 G“=G-G。显然，同时有G=G-G“。图论图的同构设G=V，E和G=V，E都是图，且两个图的结点和边分别存在一一对应关系，且保持相应的关联，则称两个图同构。两个图同构说明一个图的两种画法。图论路与回路设G=V，E是图，v0,v1,vn V，e1,e2,enE,其中 ei=,交替序列v0e1v1e2envn称为从v0连接到vn的路。v0是此路的起点，vn是此路的终点。路中边的数目是此路的长度。当起点与终点相等时，此路称为回路。注意：对于简单图的情形，可以仅用结点序列或边序列来表示路或回路。图论特殊的路与回路迹：路中所有的边均不相同；通路：路中所有的结点均不相同；圈：回路中除起点与终点外的结点均不相同；图论路的性质在一个具有n个结点的图中，如果从结点vj到结点vk存在一条路，则从结点vj到结点vk一定存在一条不多于n-1条边的路，即存在一条边数小于n的通路。此结论对于有向图和无向图都适用吗？图论无向图的连通性在无向图G中，结点u和v之间如果存在一条路，则称这两个结点是连通的。如果G中任意两个结点之间都连通，那么称图G为连通图。图论无向图的连通分支如果无向图G不连通，而G1是G的子图，且G1是连通的，则称G1是G的一个连通子图。如果连通子图G1是最大的连通子图，即增加任意一个G中的结点到G1，将使得G1成为不连通，那么称G1是G的一个连通分支。G的连通分支的个数记为w(G)。一个无向图G是连通的当且仅当w(G)=1。图论思考结点的连通性是结点集V上的一个等价关系！连通性所划分的等价类是什么？图论点割集设无向图GV，E为连通图，若有点集V1是V的真子集，使得图G在删除了V1中所有结点后，所得的子图是不连通的，而在删除了V1的任意真子集后，所得的子图仍然是连通的，则称V1是G的一个点割集；如点割集中仅有一个结点则称此结点为割点。图论割点的判定设无向图G=V，E是连通图，结点v是G的割点的充要条件是存在结点u和w，使得u和w的每一条路都经过结点v.图论点连通度若G是不完全图，定义点连通度k(G)为结点数最少的点割集的结点数，即从G中最少删除k(G)个结点后，图G即成为不连通。注意：若G不连通，则k(G)=0；若G存在割点，则k(G)=1；规定完全图Kp的k(Kp)=p-1（为什么？）。图论边割集设无向图G=V，E为连通图，若有边集E1是E的真子集，使得图G在删除了E1中所有边后，所得的子图是不连通的，而在删除了E1的任意真子集后，所得的子图仍然是连通的，则称E1是G的一个边割集；如边割集中仅有一条边则称此边为割边（或称为桥），即使得w(G-e)w(G).图论边连通度设G是不完全图，G的边连通度(G)为边数最少的边割集的边数，即从G中删除(G)条边后图G即成为不连通。若G不连通，则(G)=0；若G存在割边，则(G)=1；若G是平凡图，则(G)=0；若G是完全图Kp，则(Kp)=p-1。图论点连通度与边连通度的性质对于任何一个无向图G，有k(G)(G)。图论有向图中结点之间的可达性设G=V，E是有向图，若存在从结点u到结点v的一条路，则称从u可达v。显然，可达不一定是双向的！比较：无向图中结点之间的连通性与有向图中结点的可达性注意：可达性只有自反性和传递性，所以它不是等价关系！图论有向图的连通性在一个有向图G=V，E中，（1）任意两个结点之间都是互相可达的，则称G是强连通的；（2）任意两个结点之间至少从一个结点到另外一个结点是可达的，则称图G是单连通的；（3）如果在G中删除边的方向而得到的无向图是连通的，则称G是弱连通的。图论有向图的连通分支设G=V，E是有向图，（1）G1是具有强连通性质的最大子图，则称G1是G的强连通分支（强分图）；（2）G1是具有单连通性质的最大子图，则称G1是G的单连通分支（单分图）；（3）G1是具有弱连通性质的最大子图，则称G1是G的弱连通分支（弱分图）。图论强连通有向图的性质一个有向图G是强连通的，当且仅当G中有一个回路，它至少包含每个结点一次。一个有向图G的每一个结点位于且仅位于G的一个强连通分支中。图论图的矩阵表示回忆：关系的邻接矩阵表示。设G=V，E是图，V=v1,v2,vn，建立n阶方阵A(G)=(aij)，使得 aij=1，vi与vj邻接；aij=0，否则，则称A(G)为图G的邻接矩阵。图论可达性矩阵设G=V，E是图，V=v1,v2,vn，建立n阶方阵P(G)=(aij)，使得 aij=1，从vi到vj至少存在一条路；aij=0，否则，则称P(G)为图G的可达性矩阵。比较：可达性矩阵与邻接矩阵的区别图论思考邻接矩阵与可达矩阵之间有什么联系？如何从邻接矩阵计算出可达矩阵？图论欧拉路和欧拉回路设G=V，E是无孤立结点的图，若存在一条路，经过图G中每条边一次且仅一次，则该条路称为欧拉路；若存在一条回路，经过图G中每条边一次且仅一次，则该条回路称为欧拉回路。含有欧拉回路的图称为欧拉图。图论欧拉图的判别准则无向图G具有一条欧拉路的充分必要条件是G是连通图且只有两个度数为奇数的结点或者没有奇数度的结点。无向图G是欧拉图的充分必要条件是G是连通图且没有奇数度的结点。图论欧拉图的应用哥尼斯堡七桥问题一笔画问题图论有向图的欧拉路与欧拉回路给定有向图G，通过图中每边一次且仅有一次的一条单向路，称为单向欧拉路；通过图中每边一次且仅有一次的一条单向回路，称为单向欧拉回路。图论有向图的欧拉路与欧拉回路的判别准则有向图G具有一条单向欧拉回路，当且仅当G是连通的，且每个结点的出度等于入度。有向图G具有一条单向欧拉路，当且仅当G是连通的，而且除两个结点外，每个结点的出度等于入度，而这两个结点中，一个结点的入度比出度大1，另一个结点的出度比入度大1。图论汉密尔顿路与回路给定一个图G，若存在一条路经过图中的每个结点一次且仅一次，这条路称为汉密尔顿路。若存在一条回路，经过图中的每个结点一次且仅一次（端点除外），这条路称为汉密尔顿回路。具有汉密尔顿回路的图称为汉密尔顿图。图论思考欧拉图与汉密尔顿图的相似与区别汉密尔顿图的判别条件能够有欧拉图那么漂亮吗？图论汉密尔顿图的性质若图G=V，E具有汉密尔顿回路，则对于V的每个非空子集S均有 w(G-S)|S|成立。其中w(G-S)是G中删除S中结点后得到的图的连通分支数。图论汉密尔顿图的判别没有充分必要条件！注意：对于V的每个非空子集S均有 w(G-S)|S|成立的图不一定是汉密尔顿图。例如：Peterson图。图论汉密尔顿路与回路的构造设G是具有n个结点的简单图，如果G中每一对结点度数之和大于等于n-1，则在G中存在一条汉密尔顿路。注意：上述条件只是充分的而不是必要的！设G是具有n个结点的简单图，如果G中每一对结点度数之和大于等于n，则在G中存在一条汉密尔顿回路。图论图的闭包与汉密尔顿图给定具有n个结点的图G=V，E，若将图G中度数之和至少是n的非邻接结点连接起来，并重复上述操作，直到不再有这样的结点对为止，最终所得到的图，称为是原图G的闭包，记作C(G)。当且仅当一个简单图的闭包是汉密尔顿图时，这个简单图是汉密尔顿图。图论汉密尔顿图的应用周游世界游戏图论平面图设G=V，E是一个无向图，如果能够把G的所有结点和边画在平面上，且使得任何两条边除了端点之外没有其他的交点，就称G是一个平面图。注意：只要有一个同构图是平面图，就可判定它是平面图。图论平面图的面及边界设G是一个连通平面图，由图中的边所包围的区域，在此区域内既不包含图的结点，也不包含图的边，这样的区域称为G的一个面；包围该面的诸边所构成的回路称为这个面的边界。图论面的次数平面图中一个面的边界的回路长度称为该面的次数，记作deg(r).在一个有限平面图中每个面的次数之和等于其边数的两倍。注意：不要遗漏无限面！一个面内部的边需要计算两次！图论平面图的欧拉定理设有一个连通平面图G=V，E，它的结点数(v)、边数(e)和面数(r)之间欧拉公式成立，即 v-e+r=2.图论欧拉定理的一些推广与应用设G是一个有v个结点e条边的连通简单平面图，若v 3则e 3v-6.可以用上述定理判别有些图不是平面图。例如：K5不是平面图；K3，3不是平面图。图论Kuratowski定理一个图是平面图，当且仅当它不包含与K3，3或K5在2度结点内同构的子图。所谓在2度结点内同构指的是两个图或者是同构的，或者是通过反复插入或除去度数为2的结点后同构。图论对偶图给定平面图G=V，E，它具有面F1，F2，Fn，若有图G*=V*，E*满足下列条件：（1）对于图G的任何一个面Fi，内部有且仅有一个结点vi*V*;（2）对于图G的任何二个面Fi和 Fj的公共边界ek，存在且仅存在一条边ek*E*，使ek*=（vi*，vj*），且ek*与ek相交；（3）当且仅当ek只是一个面Fi的边界时，vi*存在一个环ek*与ek相交。则称图G*是G的对偶图。图论对偶图的性质对偶是相互的！一个连通的平面图的对偶图也是连通平面图。图论思考对于图的着色问题，即对平面图中的面进行着色，使其相邻的面的颜色均不相同，可以归结为对其对偶图中的结点进行着色，使对偶图中的相邻结点具有不同的颜色。图论图的着色方法对于图G着色时，需要的最少的着色数称为G的着色数，记作x(G).着色基本步骤：（1）将图G中的结点按照度数的递减次序进行排列；（2）用第一种颜色对第一点进行着色，并按照排列次序，对与前面着色点不邻接的每一点着上同样的颜色；（3）用第二种颜色对其余结点进行着色，重复（2），直到所有的结点全都着上色。图论关于着色的结论对于完全图K，有x(K)=n.任意平面图G最多是5一色的。任意平面图G是4一色的！图论树的基本概念一个连通且无回路的无向图称为树。树中度数为1的结点称为树叶。树中度数大于1的结点称为分枝点或内点。一个无回路的无向图称为森林，它的每个连通分支是树。图论树的等价定义给定图T，以下的定义是等价的：（1）无回路的连通图；（2）无回路且e=v-1；（3）连通且e=v-1；（4）无回路，但增加一条新边，得到一个且仅有一个回路；（5）连通，但删除任一边后便不连通；（6）每一对结点之间有一条且仅有一条路。图论生成树若图G的一个生成子图是一棵树，则称该树是G的一棵生成树。生成树中的边称为树枝；图G的不在生成树中的边称为弦；显然，所有弦组成的集合与生成树相对于图G互补。显然，生成树一般不唯一。图论生成树的性质连通图至少有一棵生成树。一条回路和任何一棵生成树的补至少有一条公共边。一个边割集和任何生成树至少有一条公共边。图论最小生成树带权图：图G中的边e赋予一个正数C(e)，称为边的权。在图G的所有生成树中，生成树T中边的权的总和最小，则称T为G的最小生成树。图论最小生成树的Kruskal算法（1）选取最小权边e1；置边数I=1;（2）当I=n-1时结束。否则转（3）；（3）设已选取的边为e1，e2，ek，在G中选取新边ek+1，使加入后与已有的边不构成回路且ek+1是满足此条件的最小权边；（4）I=I+1，转（2）。图论有向树如果一个有向图在去掉边的方向时是一棵树，那么称这个有向图为有向树。对于一棵有向树，如果恰有一个结点的入度为0，其余所有结点的入度均为1，则称此有向树为根树。其中，入度为0的结点称为根，出度为0的结点称为树叶，出度不为0的结点称为分枝点。图论根树的结构与层次根树包含一个或多个结点，这些结点中某一个称为根，其他所有结点被分成有限个子根树。从根到某一结点的单向路的长度，称为该结点的层次。根结点通常画在最高层。根据结点的层次与连接，可以定义父亲-儿子关系，兄弟关系等。图论思考家族树的对应图论m叉树在根树中，若每个结点的出度小于或等于m，则称这棵数为m叉树。如果每一个结点的出度恰好等于m或为零，则称这棵树为完全m叉树。特别地，当m=2时，称为二叉树。