第八章图.

1第八章图§1图的基本概念§2路与图的连通性§3图的矩阵表示§4特殊的图2图论•图论是近年来发展迅速而又应用广泛的一门新兴学科。•图论最早起源于一些数学游戏的难题研究。如：哥尼斯堡七桥问题、迷宫问题等。•1847年，克希霍夫用图论分析电路网络，最早将图论应用于工程科学。•图论的内容十分丰富,它是一门应用性很强的学科。计算机科学、网络理论、信息论、运筹学、语言学、物理、化学等都以图作为工具,来解决实际问题和理论问题。31图的基本概念•离散数学研究的图是不同于几何图形、机械图形的另一种数学结构,不关心图中顶点的位置、边的长短和形状,只关心顶点与边的联结关系。•如下图（a）和（b）abcde1e2e6e4e3e5（a）abcde1e6e2e4e3e5（b）abcde1e2e6e4e3e54（1）定义:一个图G是一个三元组V(G),E(G),ΦG,其中V(G)为顶点集合,E(G)是边的集合，ΦG是从边集E到结点偶对集合上的函数。讨论定义：(a)V(G)={V1，V2，…，Vn}为有限非空集合,Vi称为结点,简称V是点集。(b)E(G)={e1，…，em}为有限的边集合,ei称为边，每个ei是连结V中的某两个顶点的,称E为边集。(c)可用e＝vi,vj或e＝(vi,vj)，来表示图的边，这样可把图简化成：Ｇ＝Ｖ，Ｅ。1图的基本概念5（2）每一条边都是无向边的图称无向图。每一条边都是有向边的图称有向图。bcdabcda1图的基本概念6例：对有向图可表示为：Ｇ＝〈Ｖ，Ｅ〉，其中Ｖ＝｛a、b、c、d｝Ｅ＝｛a,b,b,a,b,d,d,a,d,d,c,c｝则：Ｇ＝〈Ｖ，Ｅ〉=〈｛a，b，c，d｝，｛a,b,b,a,b,d,d,a,d,d,c,c｝〉1图的基本概念7（3）在一个图中，若两个结点有一条有向边或者一条无向边关联,则这两个结点成为邻接点。（4）孤立结点：在一个图中不与任何结点相邻接的结点，称为孤立结点。如下图中结点v5。（5）零图：仅由孤立结点构成的图称为零图。v1v2v3v4v51图的基本概念8（6）平凡图：仅由一个孤立结点构成的图称为平凡图。（7）邻接边：关联于同一结点的两条边称为邻接边。（8）自回路（环）：关联于同一结点的一条边称为自回路。如下图，中（c，c）是环acba1图的基本概念9（9）度数：在图G=V，E中，与结点v（vV）关联的边数，称为该结点的度数，记作deg（v）。约定：每个环在其对应结点上度数增加2。ABCED1图的基本概念最大度,记为：△（G）最小度,记为：δ（G）10•定理1：每个图中，结点度数的总和等于边数的两倍。即证：∵每条边必关联两个结点，而一条边给于关联的每个结点的度数为1。故上述定理成立。deg()2vVvE1图的基本概念11•定理2：在任何图中，度数为奇数的结点必定是偶数个。证：设V1和V2分别是G中奇数度数和偶数度数的结点集，则由上述定理有：由于是偶数之和，必为偶数，而是偶数。故得是偶数，即是偶数。12deg()deg()deg()2vVvVvVvvvE2deg()vVv2E1deg()vVv1V1图的基本概念12（10）入度，出度：在有向图中，射入一个结点的边数称为该结点的入度。由一个结点射出的边数称为该结点的出度。结点的出度与入度和是该结点的度数。定理3：在任何有向图中，所有结点的入度和等于所有结点的出度之和。1图的基本概念13bcda证：∵每一条有向边必对应一个入度和出度，若一个结点具有一个入度或出度，则必关联一条有向边，所以，有向图中各结点入度和等于边数，各结点出度和也是等于边数，因此，任何有向图中，入度之和等于出度和。1图的基本概念14（11）连接于同一对结点间的多条边称为是平行的。定义：含有平行边的任何一个图称为多重图。不含有平行边和环的图称作简单图。（12）完全图：简单图G=V，E中，若每一对结点间都有边相连，则称该图为完全图。aabc（a）aabc（b）（c）aabcd1图的基本概念15定理4：n个结点的无向完全图的边数为：证明：在有n个结点的无向完全图中，任意两点间都有边连接，n个结点中任意取两点的组合为：故有n个结点的无向完全图的边数为21(1)2nCnn1(1)2Enn1(1)2nn1图的基本概念16（13）补图：给定一个图G，由G中所有结点和所有能使G成为完全图的添加边组成的图，称为G的相对于完全图的补图，或简称为G的补图。记作。如下图，（a）和（b）互为补图。G（a）（b）1图的基本概念17（14）子图：设图G=V，E，如果有图G=V，E，且EE，VV，则称G为G的子图。如下图，（b）、（c）都是（a）的子图。（a）bcdhgafe（b）bcdhgfe（c）bcdhgaf1图的基本概念18（15）生成子图：如果G的子图包含G的所有结点，则称该子图为G的生成子图。如下图，（b）、（c）都是（a）的生成子图。（a）（c）1图的基本概念19（16）．定义：设图G=V，E及图G=V，E，如果存在一一对应的映射g：vi→vi且e=（vi，vj）是G的一条边，当且仅当e=（g（vi），g（vj））是G的一条边，则称G与G同构，记作G≌G。两个图同构的充要条件是：两个图的结点和边分别存在着一一对应的关系，且保持关联关系。1图的基本概念20dbea（a）u3u4u2u1（b）存在着一一对应映射g：g(a)=u3，g(b)=u1，g(c)=u4，g(d)=u2，且有：a,ca,b,b,d,c,d分别与u3,u4,u3,u1,u1,u2,u4,u2一一对应1图的基本概念21两图同构的一些必要条件：（1）结点数目相同。（2）边数相等。（3）度数相同的结点数目相同这几个条件不是两个图同构的充分条件。下面两图，满足上述三个条件，但并不同构1图的基本概念222路与图的连通性定义：在图G=V，E中，设v0，v1，…vn∈V,e1,e2…en∈E，其中ei是关联于结点vi-1,vi的边，结点与边的交替序列v0e1v1…envn称为联结v0到vn的路。v1v4v5v2v3e1e2e3e4e5e6e7e8v1v4v5v2v3e1e2e3e4e5e6e7e8v0v3v4v1v2e1e2e3e4e5e6e7e823路的其它概念（1）V0和vn分别称作路的起点与终点。（2）一条路中所有的边的数目称作路的长度。（3）若V0=vn则路称作回路。（4）一条路中所有的边均不重复，则此路称作轨迹。（5）一条路中所有的结点均不重复，则此路称作路径。路径是轨迹，但轨迹不一定是路径。（6）对于回路，除V0=vn外，其余结点均不相同，则此路称作圈。v0v3v4v1v2e1e2e3e4e5e6e7e824无向图的连通性[定义]在任何图G=(V,E)中,若从节点u到v存在一条路,则称u到v是可达的。[定义]设G=(V,E)是无向图,对于G中任意两个节点u和v均可达,则称G是连通图25•[定义]设G=(V,E)是无向图,G中极大的连通子图称为G的连通分支,图G的连通分支数记为w(G).•由定义知,图G的连通分支满足3个条件:(1)连通分支是G的子图；(2)该子图本身是连通图；(3)在该子图中再添加原图的任意边或节点都不连通.26•在图(a)中仅一个连通分支.在图(b)中有3个连通分支.27•有向图的连通性•无向图只有连通与不连通两种情况,而有向图存在多种连通特性。•有向图的连通性分3种情形：强连通图，单向连通图，弱连通图。28•(1)强连通图•[定义]设G=(V,E)是有向图,u,vV均相互可达,则称G为强连通图.•由定义易知,下图是一个强连通图.特别地,平凡图是强连通图.29•[定理]设G=(V,E)是n阶(n≥2)有向图,则G强连通当且仅当G中存在一条回路,它通过所有节点.[定义]设G=(V,E)是有向图,G的极大的强连通子图称为G的强连通分支.下图有四个强连通分支：]3,2,1[G]4[G]6[G]5[G30•[定理]设G=(V,E)是有向图,则G的任意节点都位于且仅位于的一个强连通分支中.(2)单向连通图[定义]设G=(V,E)是有向图,对于任意u,vV,从u可达v或者从v可达u,则称G为单向连通图.31下述定理对确定有向图的单向连通分支是非常有用的.[定理]设G=(V,E)是有向图,则G单向连通当且仅当G中存在一条路,它通过所有节点.32•[定义]设G=(V,E)是有向图,G的极大的单向连通子图称为G的单向连通分支.•下图有两个单向连通分支]5,4,3,2,1[G]6,5[G33•(3)弱连通图•[定义]设G=(V,E)是有向图,若不考虑边的方向是一个无向连通图,则称有向图G为弱连通图，简称有向图连通.34•有向图的三种连通图之间的关系：•强连通图单向连通图弱连通图.•但反过来均不成立!•[定义]设G=(V,E)是有向图,G的极大的弱连通子图称为G的弱连通分支.35定义设无向图G=V,E是连通图,若存在V1V,使图G删除了V1中所有的结点后,所得的子图是不连通的，而对于任意的V2V1，图G删除了V2中所有的结点后,所得的子图是连通的，则称V1是G的点割集。若某一个结点构成一个点割集，则称该结点为割点。点割集与边割集36在下图中,{v2,v4},{v3}和{v5}都是点割集,v3和v5都是割点。点割集与边割集37定义设G为无向连通图且为非完全图,则称(G)=min{|V1||V1为G的点割集}为G的点连通度,简称连通度。(G)简记为。规定:完全图Kn(n1)的点连通度为n-1；非连通图的点连通度为0；平凡图的点连通度为0。38定义设无向图G=V,E是连通图,若存在E1E,使图G删除了E1中所有的边后,所得的子图是不连通的，而对于任意的E2E1，图G删除了E2中所有的边后,所得的子图是连通的，则称E1是G的边割集。若某一条边构成一个边割集，则称该条边为割边或桥。39在下图中,{e6},{e5},{e2,e3},{e1,e2},{e3,e4},{e1,e4},{e1,e3},{e2,e4}都是割集,其中e6和e5是桥。40定义设G为无向连通图且为非平凡图,则称(G)=min{|E1||E1为G的边割集}为G的边连通度。规定:平凡图的边连通度为(G)=0；非连通图的边连通度也为0；2路与图的连通性41定理对于任何无向图G,有:(G)(G)(G)。本定理证明略。例(1)给出一些无向简单图,使得:==；(2)给出一些无向简单图,使得:。解(1)无向完全图Kn和零图Nn都满足要求。42(2)在两个Kn(n4)之间放置一个顶点v,使v与两个Kn中任意两个不同的顶点相邻,所得简单图满足要求。因为这样的图中有一个割点v,所以,=1(当n=4时,=3)；因为有两条边组成的边割集,所以,=2(当n=5时,=4)。43§3图的矩阵表示矩阵是研究图的有关性质的最有效的工具，可运用图的矩阵运算求出图的路径、回路和其它一些性质。１．图的邻接矩阵表示方法[定义]设Ｇ＝＜Ｖ，Ｅ＞是简单图，其中V={v1,v2,…vn}定义一个nxn的矩阵A，并把其中各元素aij表示成：EvvEvvajijiij〉若〈〉若〈,0,1则称矩阵A为图G的邻接矩阵。44（1）零图的邻接矩阵称为零矩阵，即矩阵中的所有元素均为0；（2）在图的邻接矩阵中，①行中1的个数就是行中相应结点的出度②列中1的个数就是列中相应结点的入度例：设图Ｇ＝＜Ｖ，Ｅ＞如下图所示讨论定义：45２．矩阵的计算：可以用来计算两结点间路径的长度。１０００１１０１００１１０１００A定理：设A(G)是图G的邻接矩阵，则(A(G))l中i行j列元素aij(l)等于G中联结vi与vj的长度为l路的数目。46０１００１１１１２１０１００１１AAA2