《离散数学713》由会员分享，可在线阅读，更多相关《离散数学713（71页珍藏版）》请在金锄头文库上搜索。
1、离散数学,1,一、图定义一个图是一个三元组,简记为G。,7-1 图的基本概念,其中： Vv1,v2,v3,vn是一个非空集合,vi(i1,2,3,n)称为结点,简称点,V为结点集； Ee1,e2,e3,em是一个有限的集合，ei(i1,2,3,m)称为边,E为边集，E中的每个元素都有V中的结点对（有序偶或无序偶）与之对应。 例,离散数学,2,图的术语,图的术语 若边e与结点无序偶(u，v)相对应，则称边e为无向边,记为e(u，v)，这时称u，v是边e的两个端点； 若边e与结点有偶相对应，则称边e为有向边(或弧)，记为e，这时称u是边e的始点(或弧尾).v是边e的终点(或弧头)，统称为e的端点；
2、 在一个图中，关联结点vi和vj的边e，无论是有向的还是无向的，均称边e与结点vI和vj相关联，而vi和vj称为邻接点，否则称为不邻接的；,离散数学,3,续：,续： 关联于同一个结点的两条边称为邻接边； 图中关联同一个结点的边称为自回路(或环)； 图中不与任何结点相邻接的结点称为孤立结点； 仅由孤立结点组成的图称为零图； 仅含一个结点的零图称为平凡图； 含有n个结点、m条边的图称为(n，m)图；,离散数学,4,续：,续： 每条边都是无向边的图称为无向图； 每条边都是有向边的图称为有向图； 有些边是无向边，而另一些是有向边的图称为混合图。 在有向图中，两个结点间(包括结点自身间)若有同始点和同终
3、点的几条边，则这几条边称为平行边，在无向图中，两个结点间(包括结点自身间)若有几条边，则这几条边称为平行边，两结点vi，vj间相互平行的边的条数称为边(vi，vj)或的重数； 含有平行边的图称为多重图。非多重图称为线图；无自回路的线图称为简单图。,离散数学,5,(a),例：,(b),(c),(d),例：,离散数学,6,(e),(f),例：,例：,(g),离散数学,7,二、度数 定义 在无向图G中，与结点v(vV)关联的边的条数，称为该结点的度数，记为deg(v)；,二、度数,定义 在有向图G中，以结点v(vV)为始点引出的边的条数，称为该结点的引出度数,简称出度,记为deg+(v)；以结点v(
4、vV)为终点引入的边的条数，称为该结点的引入度数，简称入度,记为deg-(v)；而结点的出度和入度之和称为该结点的度数，记为deg(v)，即deg(v)deg+(v)+deg-(v)； (G)最小度，(G)最大度 定义 在图G中，对任意结点vV，若度数deg(v)为奇数，则称此结点为奇度数结点，若度数deg(v)为偶数，则称此结点为偶度数结点。,离散数学,8,例： deg(v1)3，deg+(v1)2，deg-(v1)1； deg(v2)3，deg+(v2)2，deg-(v2)1； deg(v3)5，deg+(v3)2，deg-(v3)3； deg(v4)deg+(v4)deg-(v4)0；
5、deg(v5)1，deg+(v5)0，deg-(v5)1；,例：,离散数学,9,定理,定理 1.在图G中，则所有结点的度数的总和等于边数的两倍，即：,在有向图G中，则所有结点的出度之和等于所有结点的入度之和，即：3.定理 在所有图中，度数为奇数的结点个数为偶数.,离散数学,10,定理,。,证明设V1v|vV且deg(v)奇数，V2v|vV且deg(v)偶数。显然，V1V2，且V1V2V，于是有：,由于上式中的2m和偶度数结点度数之和均为偶数，因而也为偶数。于是|V1|为偶数(因为V1中的结点v之deg(v)都为奇数)，即奇度数的结点个数为偶数。,离散数学,11,三、完全图,三、完全图 定义 在
6、图G中，若所有结点的度数均有相 同度数d，则称此图为d次正则图。 定义 一个(n，m)(n2)的简单无向图，若它 为n-1次正则图，则称该(n，m)图为无向简单 完全图，简称完全图,记为Kn。 有向完全图 定理 设无向完全图G有n个顶点，则G有 条边。,离散数学,12,四、子图和补图 定义 设有图G和图G1，若G和G1满足：若V1V，E1E，则称G1是G的子图，记为G1G；若G1G，且G1G(即V1V或E1E)，则称G1 是G的真子图，记为G1G； 定义 若V1V，E1E，则称G1是G的生成子图，记为G1G； 定义设有图G和图G2，若V2V，V2，以V2为结点集，以两个端点均在V2中的边的全体
7、为边集的G的子图称为V2导出的子图，简称G的导出子图。,四、子图和补图,离散数学,13,例：,例：,它的真子图G和生成子图G。,离散数学,14,四、子图和补图 定义 设G为具有n个结点的简单图,从完全图Kn中删去G中的所有的边而得到的图称为G的补图(或G的补)，记为 。关于完全图的子图的补图称为此子图的绝对补图。定义 是图，是的子图，”，” 是”中边所关联的所有顶点集合，则”称为关于的相对补图。,四、子图和补图,离散数学,15,例：,例：求下图的补图。,离散数学,16,五、图的同构,五、图的同构 例:如下图 (a)、(b)、(c)、(d)所示。,图(a)、图(b)、图(c)和图(d)所表示的图
8、形实际上都是一样的,离散数学,17,定义,定义 设有图G和图G1,如果存在双射函数g:VV1,且e(vi,vj)(或)是G的一条边当且仅当e1(g(vi),g(vj) (或) 是G1的一条边则称G和G1同构，记为GG1。同构的充要条件：两个图的结点和边分别存在一一对应，且保持关联关系。,离散数学,18,例：,例：如图(a)、(b)所示的两个图G和G1，GG1？,解：显然，定义函数g：VV1，满足g(vi)vi（i1，2，3，4，5），可以验证g一定是一个满足定义的双射，所以GG1。,离散数学,19,必要条件,两个图同构的必要条件： 结点数目相同； 边数相同； 度数相同的结点数相同。,注意：这三
9、个条件并不是充分条件。例如下面两个图满足这三个条件，但它们不同构。,离散数学,20,7-2 路与回路,一、路,定义 给定图G=V,E,设v0，v1，vnV,e1，e2，enE,其中ei是关联结点vi-1,vi的边,交替序列v0e1v1e2envn称为联结v0到vn的路。 v0,vn分别为该路的起点和终点，统称为路的端点。 路中边的条数称为该路的长度。 此时，若v0vn，则该路称为回路。,离散数学,21,若路中所有边全不相同，则称此路为一条迹； 若路中所有结点全不相同，则称此路为通路。 若回路中除v0vn以外所有结点全不相同，则称此圈。（闭的通路） 在简单图中一条路v0e1v1e2envn ，由
10、它的结点序列v0v1 vn确定,所以简单图的路,由可由其结点序列v0v1 vn表示。在有向图中,结点数大于1的一条路可由边序列e1e2 en 表示。,续：,离散数学,22,例：考虑如下路：,例：,离散数学,23,定理,定理在一个具有n个结点的图中，如果从结点vj到结点vk存在一条路，则从结点vj到结点vk必存在一条不多于n-1条边的路。,推论在无向图G中，如果从结点vj到结点vk存在一条路，则必存在一条从vj到vk而长度小于n的通路。,离散数学,24,二、无向图的连通性,二、无向图的连通性定义 设G是一个图，对vi，vjV，从vi到vj如存在一条路，则称结点vi和vj是连通的。定义 设G是一个
11、无向图，该无向图G中的每个连通的划分块称为G的一个连通分支，用W(G)表示G中的连通分支数。定义 设G是一个无向图，若G中任意两个结点之间都是连通的，即图G只有一个连通分支，则称该无向图G是一个无向连通图，否则，则称G是一个非连通图(或分离图)。,离散数学,25,G1是连通图，W(G1)1； G2是非连通图，且W(G2)4。,例：,例：,离散数学,26,定义设无向图G=V,E为连通的，若有结点集V1是V的真子集，使得图G删除了V1所有结点后，所得的子图是不连通的，而删除了V1的任意真子集后，所得的子图仍然是连通图。则称集合V1为图G的点割集。若某一结点就构成点割集，则称该结点为割点。这样，一个
12、连通图，删除它的一个点割集后，将分成两个或多于两个连通分支。,割点,离散数学,27,割点,若G不是完全图，我们定义k(G)=min| V1 | |V1 是G的点割集为G的点连通度(或连通度)。 连通度k(G)是为了产生一个不连通图需要删去的 点的最少数目。一个不连通图的连通度等于存在着割点的连通图的点连通度完全图Kp的点连通度,离散数学,28,定义 设无向图G=V,E为连通的，若有边集E1是E的真子集，使得图G删除了E1所有边后，所得的子图是不连通的，而删除了E1的任意真子集后，所得的子图仍然是连通图。则称集合E1为图G的边割集。若某一边构成边割集，则称该边为割边(或桥)。G的割边也就是G中的
13、一条边e使得W(G-e)W(G)。例,割边,离散数学,29,割边,与点连通度相似，我们定义非平凡图G的边连通 度为：(G)=min| E1 |E1是G的边割集，边连 通度(G)是为了产生一个不连通需要删去边的 最少数目。 平凡图(G ) 一个不连通图(G),离散数学,30,定理 对于任何一个图G =V,E，有 k(G)(G)(G) 证明 若G不连通，则k(G)=(G)=0，故上式成立。 若G连通， 证明(G)(G)。若G是平凡图，则(G)=0(G)，若G是非平凡图，则因每一结点的所有关连边必含一个边割集，故(G)(G)。,定理,离散数学,31,再证k(G)(G) .设(G)=1，即G有一割边，
14、显然此时k(G)=1，上式成立。 .设(G)2，则必可删去某(G)条边，使G不连通，而删除(G)-1条边，它仍然连通，而且有一条桥e=(u，v)。对(G)-1条边中每一条边都选取一个不同于u，v的端点，将这些端点删去必至少删去(G)-1条边。若这样产生的图是不连通的，则k(G)(G)-1(G)，若这样产生的图是连通的，则e=(u，v)仍然是桥，此时再删去u，v，就必产生一个不连通图，故k(G)(G)。 由此得k(G)(G)(G)。,续：,离散数学,32,定理 一个连通无向图G =V,E的某一点v是图G的割点，当且仅当存在两个节点u和w，使得节点u和w的每一条路都通过v。,定理,离散数学,33,
15、三、有向图的连通性,三、有向图的连通性定义 设G是一个有向图，对vi，vjV，从vi到vj如存在一条路，则称结点vi到vj是可达的。,在有向图中，如从vi到vj可达，但从vj到vi则不一定是可达的。,为此，若将可达性看成是图G的结点集合V上的二元关系的话，对有向图来说，该可达性关系满足什么性质？,离散数学,34,定义,定义 在图G中，对vi，vjV，如果从vi到vj存在路，则称长度最短的路为从vi到vj的短程线,从vi到vj的短程线的长度称为从vi到vj的距离，记为d(vi,vj)。 d(vi，vj)满足下列性质：d(vi，vj)0；d(vi，vi)0；d(vi，vk)+d(vk，vj) d(
16、vi，vj)；d(vi，vj) (当vi到vj不可达)。 此外，有关距离的概念对无向图也适用。,离散数学,35,在(a)中有：d(v2，v1) d(v1，v2)d(v3，v1) d(v1，v3) 在(b)中有：d(v1，v3)， d(v3，v7)， d(v1，v7)。,例：,例：,离散数学,36,定义 设G是一个有向图，若G中任意两个结点之间都是相互可达的，则称该有向图G是一个强连通图 ； 设G是一个有向图，若G中任意两个结点之间至少单方向可达的，则称该有向图G是一个单侧连通图； 设G是一个有向图，若略去G中所有有向边的方向后所得到的无向图G1是一个无向连通图，则称该有向图G是一个弱连通图。,
