数学建模图论篇精.ppt

数学建模图论篇数学建模图论篇第1页，本讲稿共62页图论原理图论原理一一.图的概念图的概念 一个图一个图 G=,G=,其中结点集其中结点集V(G):V(G):是是G G的结点的结点的非空集合的非空集合.(V(G),.(V(G),简记成简记成V;V;边集边集E(G):E(G):是是G G的的边的集合边的集合.有时简记成有时简记成E.E.结点结点:用用 表示表示,旁边标上该结点的名称旁边标上该结点的名称.边边:有向边有向边:带箭头的弧线带箭头的弧线.从从u u到到v v的边表示成的边表示成(u,v)(u,v)无向边无向边:不带箭头的弧线不带箭头的弧线.u.u和和v v间的边表示成间的边表示成(u,v)(u,v)r w eV(G1)=r,e,wE(G1)=,A B C De1e5e7e6e3e4e2G1:G2:V(G2)=A,B,C,DE(G2)=e1,e2,e3,e4,e5,e6,e7 第2页，本讲稿共62页图论原理图论原理在图中在图中,结点的相对位置不同结点的相对位置不同,边的曲直、长短无关边的曲直、长短无关紧要紧要.邻接点邻接点:与一边关联的两个结点与一边关联的两个结点.u u v a v a b b 邻接边邻接边:关联同一个结点的两条边关联同一个结点的两条边.环环:只关联一个结点的边只关联一个结点的边.平行边平行边:在两个结点之间关联的多条边在两个结点之间关联的多条边.二二.有向图与无向图有向图与无向图 有向图有向图:只有有向边的图只有有向边的图.无向图无向图:只有无向边的图只有无向边的图.e1 v e2 第3页，本讲稿共62页图论原理图论原理三三.零图与平凡图零图与平凡图 孤立结点孤立结点:不与任何边关联的结点不与任何边关联的结点.u u 零图零图:仅由一些孤立结点构成的图仅由一些孤立结点构成的图.a.a 即此图的边的集合即此图的边的集合E=bE=b c c 平凡图平凡图:仅由一个孤立结点构成的图仅由一个孤立结点构成的图.|V(G)|=1,|E(G)|=0|V(G)|=1,|E(G)|=0四四.简单图与多重图简单图与多重图 简单图简单图:不含有环和平行边的图不含有环和平行边的图.多重图多重图:含有平行边的图含有平行边的图.G:A B C De1e5e7e6e3e4e2 cb a 第4页，本讲稿共62页图论原理图论原理五五.无向图结点无向图结点v v的度的度:1.1.定义定义:G G是个无向图是个无向图,vV(G),vV(G),结点结点v v所关联边数所关联边数,称之为结点称之为结点v v的的度，或称为度，或称为v v的次数的次数.记作记作 deg(v).(deg(v).(或或d(v).d(v).deg(a)=3,deg(b)=3,deg(c)=4,deg(d)=2,deg(a)=3,deg(b)=3,deg(c)=4,deg(d)=2,一个环给结点的度是一个环给结点的度是2.2.2.2.无向图的结点度序列无向图的结点度序列:令令G=G=是无向图是无向图,V=vV=v1 1,v,v2 2,v,v3 3,v,vn n,则称则称:(deg(vdeg(v1 1),deg(v),deg(v2 2),der(v),der(v3 3),),deg(v,deg(vn n)为图为图G G的结点度序列的结点度序列.例如上图的结点度序列为例如上图的结点度序列为:(3,5,4,2):(3,5,4,2)c a b d第5页，本讲稿共62页图论原理图论原理3.3.图的最大度图的最大度(G)(G)与最小度与最小度(G)(G):G=:G=是无向图是无向图,(G)=maxdeg(v)|vG (G)=mindeg(v)|vG(G)=maxdeg(v)|vG (G)=mindeg(v)|vG上图中上图中(G)=5 (G)=2(G)=5 (G)=2性质：性质：每个无向图所有结点度总和等于边数的每个无向图所有结点度总和等于边数的2 2倍倍.即即k-k-正则图正则图:一个无向简单图一个无向简单图G G中中,如果如果(G)=(G)=k(G)=(G)=k则称则称G G为为k-k-正则图正则图.deg(v)=2|E|vV 第6页，本讲稿共62页图论原理图论原理六六.完全图完全图1.1.无向完全图无向完全图 定义定义:G G是个简单图是个简单图,如果每对不同结点之间都有边相连如果每对不同结点之间都有边相连则称则称G G是个无向完全图是个无向完全图.如果如果G G有有n n个结点个结点,则记作则记作Kn.Kn.性质：性质：无向完全图无向完全图Kn,Kn,有边数有边数n(n-1)/2n(n-1)/2证明证明:因为因为KnKn中每个结点都与其余中每个结点都与其余n-1n-1个结点关联个结点关联,即每个结点的度即每个结点的度均为均为n-1,n-1,所以所以KnKn所有结点度数总和所有结点度数总和为为n(n-1),n(n-1),设边数为设边数为|E|,E|,于于是是n(n-1)=2|E|n(n-1)=2|E|所以所以|E|=n(n-1)/2E|=n(n-1)/2 K2K3K4K5第7页，本讲稿共62页图论原理图论原理2.2.有向图的完全图有向图的完全图 1).1).有向简单完全图有向简单完全图:G G是个是个有向简单图有向简单图,如果任何两个如果任何两个不同不同结点之间结点之间都有相互可达的边都有相互可达的边,则称它是有向简单完全图则称它是有向简单完全图.例如例如:性质性质:有有n n个结点的有向简单完全图有边数为个结点的有向简单完全图有边数为n(n-1).n(n-1).证明证明:显然它的边数是显然它的边数是K Kn n边数的边数的2 2倍倍.所以是所以是n(n-1).n(n-1).第8页，本讲稿共62页图论原理图论原理2).2).有向完全图有向完全图(有向全图有向全图)()(它与完全关系图一致它与完全关系图一致)G G是个有向图如果任何两个结点之间都有相互可达的边是个有向图如果任何两个结点之间都有相互可达的边,则称则称它是有向完全图它是有向完全图.其图形如下其图形如下:所以有所以有n n个结点的有向完全图个结点的有向完全图,有边数有边数 n n2 2.第9页，本讲稿共62页图论原理图论原理七七.子图和生成子图子图和生成子图1.1.子图子图:设设G=G=是图是图,如果如果G G=V=且且V V V,VV,V,E,E E,E,则称则称G G是是G G的子图的子图.可见可见G G1 1,G,G2 2,G,G3 3都是都是K K5 5的子图的子图.b cd e ab c ab cd eG1G2G3K5 ab cd e第10页，本讲稿共62页图论原理图论原理2.2.生成子图生成子图设设G=G=是图是图,G G=V=,G G是是G G的子图的子图,如果如果V V=V,V,则称则称G G是是G G的生成子图的生成子图.上例中上例中,G G1 1是是K K5 5的生成子图的生成子图.八八.补图补图由由G G的所有结点和为使的所有结点和为使G G变成完全图变成完全图,所需要添加的那些边组成的所需要添加的那些边组成的图图,称之为称之为G G相对完全图的补图相对完全图的补图,简称简称G G的补图的补图,记作记作 。G K5 G G第11页，本讲稿共62页图论原理图论原理图的同构图的同构设设G=G=和和G G=V=是图是图,如果存在双射如果存在双射f:Vf:VV V 且任何且任何v vi i,v,vj jV,V,若边若边(v(vi i,v,vj j)E,)E,当且仅当当且仅当 边边(f(v(f(vi i),f(v),f(vj j)E)E,(则称则称G G与与G G同构同构,记作记作GGGG.(同构图要保持边的同构图要保持边的“关联关联”关系关系)例如例如:右边所示的两个图右边所示的两个图:G=GG=G=V=构造映射构造映射f:Vf:VV Va bc d1 43 2a 1b 2c 3d 4a 1b 2c 3d 4第12页，本讲稿共62页图论原理图论原理两个图同构的必要条件两个图同构的必要条件:1.1.结点个数相等结点个数相等.2.2.边数相等边数相等.3.3.度数相同的结点数相等度数相同的结点数相等.4.4.对应的结点的度数相等对应的结点的度数相等.下面是同构的图下面是同构的图:ab ec d 13 45 2a fb ec d 3 51 62 4 第13页，本讲稿共62页图论原理图论原理判断下列图是否同构？和 和 和 31 2 ab c 第14页，本讲稿共62页图论原理图论原理如果一个结点对可对应若干条边，这种边成为多重如果一个结点对可对应若干条边，这种边成为多重边，包含多重边的图成为多重图。边，包含多重边的图成为多重图。带权图带权图(赋权图赋权图)定义定义:设设G=,G=,是个图是个图,如果如果G G的每条边的每条边e e上都标上都标有实数有实数c(e)(c(e)W),c(e)(c(e)W),称这个数为边称这个数为边e e的权的权,而此而此边为有权边边为有权边 称此图为称此图为带权图带权图.而无有权边的图则而无有权边的图则成为无权图。成为无权图。例如右图中例如右图中v v1 1 v v2 2v v3 3 v v6 6 的路长为的路长为12.12.v6 v5 v4v1 v3 v2365112336第15页，本讲稿共62页图论原理图论原理通路与回路通路与回路1.1.通路的定义通路的定义:给定图给定图G=,G=,v v0 0,v v1 1,v,v2 2,v,vn nV,V,e e1 1,e,e2 2,e,en nEE，其中，其中e ei i是关联是关联v vi i1 1,v vi i的边的边,则称结则称结点和边的交叉序列为图的通路。点和边的交叉序列为图的通路。如如v v0 0 e e1 1v v1 1 e e2 2v v2 2e en nv vn n是连接是连接v v0 0到到v vn n的路的路.v.v0 0是此路的起是此路的起点点,v vn n是此路的终点是此路的终点.路中含有的边数路中含有的边数n n称之为路的长度称之为路的长度.如果其中每条边的终点总是下一条边的起点，则边的如果其中每条边的终点总是下一条边的起点，则边的序列可以简写成（序列可以简写成（v v0,0,v v1,1,v v2,2,v,vn n)例如右图中例如右图中:v v0 0 e e2 2v v3 3 e e6 6v v2 2是一条长度为是一条长度为2 2的路的路.v3 v2v1 v0e1e2e3e4e5e6第16页，本讲稿共62页图论原理图论原理回路回路:如果一条路的起点和终点是一个结点如果一条路的起点和终点是一个结点,则称此路则称此路是一个回路是一个回路.如果一条路中所有如果一条路中所有边都不同边都不同,则称此路为则称此路为迹迹或或简单通路简单通路.如果一条如果一条回路回路中所有中所有边都不同边都不同,则称此回路为则称此回路为闭迹闭迹或或简简单回路单回路.如果一条路中所有如果一条路中所有结点都不同结点都不同,则称此路为则称此路为基本通路基本通路.如果一条如果一条回路回路中所有中所有结点都不同结点都不同,则称此路为则称此路为基本回路基本回路.一条基本通路一定是简单通路，但是一条简单通路不一条基本通路一定是简单通路，但是一条简单通路不一定是基本通路一定是基本通路第17页，本讲稿共62页图论原理图论原理性质：性质：一个有向一个有向(n,m)(n,m)图中任何基本通路长度都小于图中任何基本通路长度都小于或者等于或者等于n-1n-1，任何基本回路长度都小于或者等于，任何基本回路长度都小于或者等于n n。定义：定义：从一有向图的结点从一有向图的结点a a到另一结点到另一结点b b间如果存在一间如果存在一条通路，则称从条通路，则称从a a到到b b是可达的。是可达的。无向图的连通性无向图的连通性定义：定义：一个无向图一个无向图G G，如果它的任何两个结点间均是，如果它的任何两个结点间均是可达的，这称图可达的，这称图G G为连通图；否则，称为非连通图。为连通图；否则，称为非连通图。定义：定义：一个有向图一个有向图G G，如果忽略其边的方向得到的无，如果忽略其边的方向得到的无向图是连通的，这称为有向的连通图。向图是连通的，这称为有向的连通图。第18页，本讲稿共62页图论原理图论原理对于有向的连通图，还可以进一步将其分为三类：对于有向的连通图，还可以进一步将其分为三类：在简单有向图在简单有向图G G中中,如果任何两个结点间相互可达如果任何两个结点间相互可达,则称则称G G是是强连通强连通.如果任何一对结点间如果任何一对结点间,至少有一个结点到另一个结点可达至少有一个结点到另一个结点可达,则称则称G G是是单向连通单向连通.如果将如果将G G看成无向图后看成无向图后(即把有向边看成无向边即把有向边看成无向边)是连通的是连通的,则称则称G G是是弱连通弱连通.(a)(a)有回路有回路adbca,adbca,强连通强连通.(b)a(b)a到到d,dd,d到到a,a,都不可达都不可达 是弱连通是弱连通.(c)(c)单向连通单向连通.dc a b dc a b dc a b(a)(b)(c)第19页，本讲稿共62页图论原理图论原理欧拉图欧拉图:1.1.欧拉通路欧拉通路:在无孤立结点的图在无孤立结点的图G G中中,如果存在一条路如果存在一条路,它经过图中它经过图中每条边一次且仅一次每条边一次且仅一次,称此路为欧拉通路称此路为欧拉通路.2.2.欧拉回路欧拉回路:在无孤立结点的图在无孤立结点的图G G中中,若存在一条回路若存在一条回路,它经过图它经过图中每条边一次且仅一次中每条边一次且仅一次,称此回路为欧拉回路称此回路为欧拉回路.称此图为欧拉图。称此图为欧拉图。在在G G1 1中中:有欧拉路有欧拉路:acbefgdcfhacbefgdcfh在在G G2 2中中:有欧拉回路有欧拉回路:v v1 1v v2 2v v3 3v v4 4v v5 5v v2 2v v4 4v v6 6v v5 5v v3 3v v1 1a ge b d hc f G2G1v1 v5v4 v2 v3 v6第20页，本讲稿共62页图论原理图论原理欧拉通路的判定方法：欧拉通路的判定方法：定理：定理：无向连通图无向连通图G G中结点中结点a a和和b b间存在欧拉通路的充分必要条件是间存在欧拉通路的充分必要条件是a a与与b b的次数均为奇数而其他结点的次数均为偶数。的次数均为奇数而其他结点的次数均为偶数。如果如果G G有两个奇数度结点有两个奇数度结点:就从一个奇数度结点出发就从一个奇数度结点出发,每当到达一个每当到达一个偶数度结点偶数度结点,必然可以再经过另一条边离开此结点必然可以再经过另一条边离开此结点,如此重复下去如此重复下去,经过所有边后到达另一个奇数度结点经过所有边后到达另一个奇数度结点如果如果G G无奇数度结点无奇数度结点,则可以从任何一个结点出发则可以从任何一个结点出发,去构造一条欧拉路去构造一条欧拉路.a bc d1 24 3第21页，本讲稿共62页图论原理图论原理推论推论:无向图无向图G G具有欧拉回路具有欧拉回路,当且仅当当且仅当G G是连通的是连通的,且且所有结点的度都是偶数所有结点的度都是偶数.从此推论得知从此推论得知,七桥问题的图不是欧拉图七桥问题的图不是欧拉图.欧拉路与欧拉回路问题欧拉路与欧拉回路问题,也称一笔画问题也称一笔画问题.A B C De1e5e7e6e3e4e2第22页，本讲稿共62页图论原理图论原理汉密尔顿图汉密尔顿图(H(H图图)(Hamilton)(Hamilton图图)HamiltonHamilton是英国数学家是英国数学家,在在19591959年年,他提出他提出HamiltonHamilton回路回路.H H图起源于一种游戏图起源于一种游戏,这个游戏就是所谓周游世界问题这个游戏就是所谓周游世界问题.例如例如,某个城市的街道如图所示某个城市的街道如图所示:该城市的所有交叉路口都有形象各该城市的所有交叉路口都有形象各异的精美的雕塑异的精美的雕塑,吸引着许多游客吸引着许多游客,人人都想找到这样的路径人人都想找到这样的路径:游遍各游遍各个景点再回到出发点个景点再回到出发点-H-H回路回路.第23页，本讲稿共62页图论原理图论原理1.1.定义定义:设设G=G=是个无向有限图是个无向有限图,汉密尔顿路汉密尔顿路:通过通过G G中每个结点恰好一次的路中每个结点恰好一次的路.汉密尔顿回路汉密尔顿回路(H(H回路回路):):通过通过G G中每个结点恰好一次中每个结点恰好一次的回路的回路.汉密尔顿图汉密尔顿图(H(H图图):):具有汉密尔顿回路具有汉密尔顿回路(H(H回路回路)的图的图.例如右图中例如右图中,就是就是H H图图,因为它有因为它有H H回路回路:1234561:1234561 16 25 3 4第24页，本讲稿共62页图论原理图论原理2.2.汉密尔顿图的判定汉密尔顿图的判定:到目前为止并没有判定到目前为止并没有判定H H图的充分必要条件图的充分必要条件.定理定理1 1 (充分条件充分条件):G):G是完全图是完全图,则则G G是是H H图图.定理定理2 2(充分条件充分条件)设设G G是有是有n(n2)n(n2)个结点的简单图个结点的简单图,若对若对G G中每对结点中每对结点度数之和大于等于度数之和大于等于n,n,则则G G有一条有一条H H路路(H H回路回路)。K2K3K4K5第25页，本讲稿共62页图论原理图论原理在图在图G G1 1中中,满足充分条件满足充分条件(G)=4(G)=2(G)=4(G)=2任意两个任意两个结点度数之和大于等于结点度数之和大于等于5,5,所以是所以是H H图图.注意注意:上述条件只是充分条件上述条件只是充分条件,而不是必要条件而不是必要条件,即即不满足这个条件的不满足这个条件的,也可能有也可能有H H路路.例如例如:在图在图G G2 2中中,并不满足任意两个结点度数之和并不满足任意两个结点度数之和大于等于大于等于3,3,但是却有但是却有H H路路.15 24 3d c a b G2G1第26页，本讲稿共62页图论原理图论原理定理定理3 3:(必要条件必要条件)若图若图G=G=有有H H回路回路,则对则对V V的任的任何非空子有限集何非空子有限集S,S,均有均有W(G-S)W(G-S)|S|,|S|,其中其中W(G-W(G-S)S)是从是从G G中删去中删去S S中所有结点及与这些结点关联的中所有结点及与这些结点关联的边所得到的子图的连通分支数边所得到的子图的连通分支数.用此定理可以判断一个图不是用此定理可以判断一个图不是H H图图.如右图如右图G,G,取取 S=c S=c 不满足不满足 W(G-S)W(G-S)|S|.|S|.c eb a d第27页，本讲稿共62页图论原理图论原理图的矩阵表示法图的矩阵表示法图的矩阵表示不仅是给出图的一种表示方法图的矩阵表示不仅是给出图的一种表示方法,还可还可以通过这些矩阵讨论有关图的若干性质以通过这些矩阵讨论有关图的若干性质,更重要更重要的是可以用矩阵形式将图存入计算机中的是可以用矩阵形式将图存入计算机中,在计算在计算机中对图作处理机中对图作处理.这里主要讨论图的三种矩阵这里主要讨论图的三种矩阵.一一.邻接矩阵邻接矩阵 这是以结点与结点之间的邻接关系确定的矩阵这是以结点与结点之间的邻接关系确定的矩阵.第28页，本讲稿共62页图论原理图论原理1.1.定义定义:设设G=G=是个简单图是个简单图,V=v,V=v1 1,v,v2 2,v,v3 3,v,vn n,一个一个nnnn阶矩阵阶矩阵A=(aA=(aijij)称为称为G G的邻接矩阵的邻接矩阵.其中其中:例如例如,给定无向图给定无向图G G1 1和有向图和有向图G G2 2如图所示如图所示:aij=1 vi与与vj邻接邻接,即即(vi,vj)E 或或 E0 否则否则v1 v5v4 v2 v3G1第29页，本讲稿共62页图论原理图论原理v3 v2 v4 v5v1 G2第30页，本讲稿共62页图论原理图论原理2.2.从邻接矩阵看图的性质从邻接矩阵看图的性质:无向图无向图:每行每行1 1的个数的个数=每列每列1 1的个数的个数=对应结点的度对应结点的度 有向图有向图:每每行行1 1的个数的个数=对应结点的对应结点的出度出度（P133P133）每每列列1 1的个数的个数=对应结点的对应结点的入度入度第31页，本讲稿共62页图论原理图论原理3.3.邻接矩阵的乘积邻接矩阵的乘积在在(A(G(A(G1 1)2 2 中中a a34342 2 =2=2 表示从表示从v v3 3到到v v4 4有长度为有长度为2 2的路有的路有2 2条条:v1 v5v4 v2 v3G1v3 v2v4,v3 v5v4第32页，本讲稿共62页图论原理图论原理在在(A(G1)(A(G1)3 3中中a a23233 3=6 =6 表示从表示从v v2 2到到v v3 3有长度为有长度为3 3的路有的路有6 6条条:v2v1v2v3,v2v4v2v3,v2v3v2v3,v2v3v1v3,v2v3v5v3,v2v4v5v3第33页，本讲稿共62页图论原理图论原理性质：性质：设设G=G=是简单图是简单图,令令V=vV=v1 1,v,v2 2,v,v3 3,v,vn n,G G的邻接矩阵的邻接矩阵(A(G)(A(G)k k中的第中的第i i行第行第j j列元素列元素a aijijk k=m,=m,表示在图表示在图G G中从中从v vi i到到v vj j长度为长度为k k的路有的路有m m条条.例子见教材例子见教材P134P134 在实际应用中在实际应用中,有时只关心从一个结点到另一有时只关心从一个结点到另一个结点是否有路个结点是否有路,而不关心路有多长而不关心路有多长,比如电话网比如电话网络络.这就促使我们定义可达矩阵这就促使我们定义可达矩阵.第34页，本讲稿共62页图论原理图论原理二二.可达性矩阵可达性矩阵1.1.定义定义:设设G=G=是个简单图是个简单图,V=v,V=v1 1,v,v2 2,v,v3 3,v,vn n,一个一个nnnn阶矩阵阶矩阵P=(pP=(pijij)称为称为G G的可达性矩阵的可达性矩阵.其中其中:可以根据邻接矩阵可以根据邻接矩阵A A求可达矩阵求可达矩阵.设设|V(G)|=n|V(G)|=n 令令A A(k)(k)是将是将A Ak k中的非中的非0 0元素都写成元素都写成1,1,而得到的只含有而得到的只含有0 0和和1 1的的0-10-1矩阵矩阵.于是可达矩阵于是可达矩阵P P为为:P=A P=AA A(2)(2)A A(3)(3).A A(n)(n)pij=1 vi到到vj可达可达,(至少有一条路至少有一条路)0 否则否则第35页，本讲稿共62页图论原理图论原理按照矩阵相乘分别求出按照矩阵相乘分别求出A A(k)(k)(k2),(k2),然后再即可得然后再即可得到可达性矩阵到可达性矩阵P P。例如例如,G G2 2如图所示如图所示,求它的可达矩阵求它的可达矩阵P.P.v3 v2 v4 v5v1 G2第36页，本讲稿共62页图论原理图论原理P=AA(2)A(3)A(4)A(5)所以所以0010000010100100100100010A=1001001011011010001001001A(2)=0110101011100100100000010A(3)=1001001011011010001001001A(4)=A(2)A(5)=A(3)1111101011111110101101011P=第37页，本讲稿共62页图论原理图论原理无向图的矩阵表示法：无向图的矩阵表示法：由于无向图中的无向边用两条相反的有向边替代，由于无向图中的无向边用两条相反的有向边替代，使无向图转换为有向图，所以有向图中的邻接矩使无向图转换为有向图，所以有向图中的邻接矩阵、可达性矩阵等均可适用于无向图。阵、可达性矩阵等均可适用于无向图。性质：性质：无向图的邻接矩阵都是对称矩阵。无向图的邻接矩阵都是对称矩阵。多重图及有权图的矩阵表示法：多重图及有权图的矩阵表示法：多重图多重图G对应的对应的矩阵矩阵A=(aA=(aijij)中元素为中元素为aij=k 若vi与vj有k条有向边相连0 若从vi与vj无有向边相连第38页，本讲稿共62页图论原理图论原理有权图有权图G对应的对应的矩阵矩阵A=(aA=(aijij)中元素为中元素为矩阵与图的连通性矩阵与图的连通性一无向图为连通图的充分必要条件是此图的可达性一无向图为连通图的充分必要条件是此图的可达性矩阵除对角线元素外均为矩阵除对角线元素外均为1 1。有向图的强连通相当于无向连通图。有向图的强连通相当于无向连通图。aij=k 若vi与vj有边相连且此边权为k0 若从vi与vj无边相连第39页，本讲稿共62页图论原理图论原理 有向图的单向连通的充分必要条件是可达性矩有向图的单向连通的充分必要条件是可达性矩阵阵P P及其转置所组成的矩阵及其转置所组成的矩阵P P=P+P=P+PT T除对角线元素除对角线元素外均为外均为1 1。有向图的弱连通的充分必要条件是其邻接矩阵有向图的弱连通的充分必要条件是其邻接矩阵A A及其转置矩阵组成的矩阵及其转置矩阵组成的矩阵A A=A+A=A+AT T的可达性矩阵的可达性矩阵中除对角线元素外均为中除对角线元素外均为1 1。例例8.12,8.12,见教材见教材P138P138。第40页，本讲稿共62页常用图常用图树与生成树树与生成树树是一种特殊的图树是一种特殊的图,它是图论中重要的概念之一它是图论中重要的概念之一,它有着广泛的应用它有着广泛的应用.在计算机科学中有如判定树、在计算机科学中有如判定树、语法树、分类树、搜索树、目录树等等语法树、分类树、搜索树、目录树等等.一一.树树 (Tree)(Tree)1.1.树的定义树的定义:一个连通无回路一个连通无回路的的 无向图无向图T,T,称之为树称之为树.如如(a)(a)(a)第41页，本讲稿共62页常用图常用图2.2.叶结点叶结点:度数为度数为1 1的结点的结点,称为叶结点称为叶结点.3.3.分支结点分支结点(内结点内结点):):度数大于度数大于1 1的结点的结点.4.4.森林森林:一个无向图的每个连通分支都是树一个无向图的每个连通分支都是树.如如(b)(b)(b)第42页，本讲稿共62页常用图常用图5.5.与树定义等价的几个命题与树定义等价的几个命题定理定理:给定图给定图T,T,以下关于树的定义是等价的以下关于树的定义是等价的.无回路的连通图无回路的连通图.无回路且无回路且m=n-1 m=n-1 其中其中m m是是T T的边数的边数,n n是是T T的结点数的结点数.连通的且连通的且m=n-1.m=n-1.无回路但添加一条新边则得到一条仅有的回路无回路但添加一条新边则得到一条仅有的回路.连通的连通的,但删去任一条边但删去任一条边,T,T便不连通便不连通.每对结点之间有一条且仅有一条路每对结点之间有一条且仅有一条路.第43页，本讲稿共62页常用图常用图有向树有向树:在有向图中如果不考虑边的方向而构成树，在有向图中如果不考虑边的方向而构成树，则称此有向图为有向树。则称此有向图为有向树。外向树：外向树：如果一棵有向树如果一棵有向树,恰有一个结点的入度为恰有一个结点的入度为0,0,其余其余所有结点的入度均为所有结点的入度均为1,1,则称此树为外向树则称此树为外向树.1.1.树根树根:入度为入度为0 0的结点的结点.2.2.叶叶:出度为出度为0 0的结点的结点.3.3.分支结点分支结点(内结点内结点):):出度不为出度不为0 0的结点的结点.外向树结点的级外向树结点的级:从根结点到某个结点的通路的长度从根结点到某个结点的通路的长度,称称为该结点的级为该结点的级.第44页，本讲稿共62页常用图常用图外向树可以表示亲属关系：外向树可以表示亲属关系：父结点与子结点父结点与子结点:如果如果v 是根树中的一条边是根树中的一条边,则则称称v vi i是是v vj j的父结点的父结点,v,vj j是是v vi i的子结点的子结点.祖先结点与后裔结点祖先结点与后裔结点:在根树中在根树中,如果从如果从v vi i到到v vj j有路有路,则称则称v vi i是是v vj j的祖先结点的祖先结点,v,vj j是是v vi i的后裔结点的后裔结点.内向树：内向树：内向树和外向树的定义类似，它是出度为内向树和外向树的定义类似，它是出度为0 0的结点为的结点为根，其他结点出度都为根，其他结点出度都为1 1的树。的树。内向树也类似的有分支结点、级等概念内向树也类似的有分支结点、级等概念(P147)(P147)第45页，本讲稿共62页常用图常用图三三.举例举例:a)a)语法树语法树b)b)算术表达式树算术表达式树(a+b)c)(d(a+b)c)(de)e)句子句子 动词动词 冠词冠词 主语主语 谓语短语谓语短语 形容词形容词 名词名词 宾语宾语 The little boy saw apple The冠词冠词 名词名词+a b c e d第46页，本讲稿共62页常用图常用图m m元树元树:在根树中在根树中,如果每个结点的出度最大是如果每个结点的出度最大是m,m,则则称此称此 树是树是m m元树元树.m m元完全树元完全树:在根树中（除叶外）在根树中（除叶外）,如果每个结点的出如果每个结点的出度都是度都是m m,则称此树是则称此树是m m元完全树元完全树.m m2 2时则称为二元树和二元完全树。时则称为二元树和二元完全树。二叉树便于在计算机内存贮二叉树便于在计算机内存贮,设有算术表达式：设有算术表达式：(3(3(2(2x)+(x-2)(3+x)x)+(x-2)(3+x)+3 2 x x 2+x 3 第47页，本讲稿共62页常用图常用图m m元有序树转化成二元树元有序树转化成二元树因为二叉树便于存贮因为二叉树便于存贮,也便于处理也便于处理,所以通常可以将多叉树化成二叉树，所以通常可以将多叉树化成二叉树，方法是方法是:1.1.每个结点保留左儿子结点每个结点保留左儿子结点,剪掉右边其它分支剪掉右边其它分支.被剪掉的结点被剪掉的结点如下处理如下处理.2.2.同一个层次的结点同一个层次的结点,从左到右依次画出从左到右依次画出.r e c a b d g fh i j k lr a bc dh e f gi j k l第48页，本讲稿共62页常用图常用图生成树生成树在图论的应用中在图论的应用中,找出一个连通图的所有不同的生成树找出一个连通图的所有不同的生成树,以及找出最小生成树是很有意义的以及找出最小生成树是很有意义的.定义定义:如果图如果图G G的生成子图是树的生成子图是树,则称此树为则称此树为G G的生成树的生成树.性质：性质：连通图至少有一棵生成树连通图至少有一棵生成树.赋权图的最小生成树赋权图的最小生成树定义定义:一棵生成树中的所有边的权之和称为该一棵生成树中的所有边的权之和称为该生成树的生成树的权权.具有最小权的生成树具有最小权的生成树,称为称为最小生成树最小生成树.第49页，本讲稿共62页常用图常用图最小生成树很有实际应用价值最小生成树很有实际应用价值.例如结点是城市名例如结点是城市名,边的权表示两个城市间的距离边的权表示两个城市间的距离,从一个城市出发从一个城市出发走遍各个城市走遍各个城市,如何选择长度最短的旅行路线如何选择长度最短的旅行路线.又又如城市间的通信网络问题如城市间的通信网络问题,如何布线如何布线,使得总的线使得总的线路长度最短路长度最短.求最小生成树算法求最小生成树算法-Kruskal-Kruskal算法算法:(避圈法避圈法)v1 v5 v4v2 v3v8 v6v7 12213772486653443第50页，本讲稿共62页常用图常用图KruskalKruskal算法算法:设设G G是有是有n n个结点个结点,m m条边条边(mn-1)mn-1)的连通图的连通图.|S|=n-1,|S|=n-1,说明是树说明是树最后最后S=S=a a1 1,a,a2 2,a,a3 3,a,an n S=i=0 j=1将所有边按照权升序排序:e1,e2,e3,em|S|=n-1取ej使得使得S ej有回路有回路?j=j+1i=i+1ai=ejS=Saij=j+1输出S停YNYN第51页，本讲稿共62页边权边权e28e34e23e38e17e24e45e57e16e78e56e35e46e67e58e12e181 1 2 2 2 3 3 3 4 4 4 5 6 6 7 7 8v1 v5 v4v2 v3v8 v6v7 12213772486653443v1 v5 v4v2 v3v8 v6v7 1212433第52页，本讲稿共62页常用图常用图 在实际应用中在实际应用中,如高速公路设计、印刷电路设计如高速公路设计、印刷电路设计,都要求都要求线路不交叉线路不交叉,这就是平面图这就是平面图,一个图能否画在一个平面上一个图能否画在一个平面上,且任何边都不交叉且任何边都不交叉,这就是图的平面化问题这就是图的平面化问题.这个问题在这个问题在近些年来近些年来,特别是大规模集成电路的发展进一步促进了对特别是大规模集成电路的发展进一步促进了对平面图的研究平面图的研究.1.1.定义定义 设设G G是无向图是无向图,如果能将如果能将G G的所有结点和边都画在一个的所有结点和边都画在一个平面上平面上,且使得任何两条边除了端点外没有其它交点且使得任何两条边除了端点外没有其它交点,则则称称G G是个平面图是个平面图.一个图表面上是个非平面图一个图表面上是个非平面图,如果通过如果通过改变边的位置就变成平面图改变边的位置就变成平面图,称此图是可平面化的称此图是可平面化的.第53页，本讲稿共62页例如右图例如右图.就是就是可平面化的图可平面化的图.下面是两个下面是两个重要的非平面图重要的非平面图:K K5 5和和K K3,33,3v1 v5v4 v2 v3v1 v5v4 v2 v3v1 v5v4 v2 v3v1 v5v4 v2 v3 3 51 62 4 a fb ec da fb ec d常用图常用图第54页，本讲稿共62页2.2.平面图的面、边界及面的次数平面图的面、边界及面的次数 设设G G是个平面图是个平面图,图中边围成的图中边围成的区域区域,其内部不含有结点其内部不含有结点,也不含也不含有边有边,称这样区域为称这样区域为G G的一个的一个面面.面的边界面的边界:围成一个面围成一个面r r的所有的所有边构成的回路边构成的回路,称之为这个称之为这个r r面的边界面的边界.此回路中的边数此回路中的边数,称称之为之为r r面的次数面的次数,记作记作deg(r)deg(r).有限面与无限面有限面与无限面:面的面积有限称为有限面面的面积有限称为有限面,反之称为无反之称为无限面限面.所有平面图的外侧都有一个无限面所有平面图的外侧都有一个无限面.例如例如,上图中上图中 r r1 1:边界边界:ABCDFDA deg(r:ABCDFDA deg(r1 1)=6)=6 r r2 2:边界边界:ABCA deg(r:ABCA deg(r2 2)=3)=3 r r3 3:边界边界:ACDA deg(r:ACDA deg(r3 3)=3)=3 r r4 4:边界边界:ADA deg(r:ADA deg(r4 4)=)=2 2A DF B Cr1r2r3r4常用图常用图第55页，本讲稿共62页常用图常用图3.3.欧拉公式欧拉公式性质性质1 1：G G是个连通的平面图是个连通的平面图,设设n n、m m、r r分别表示分别表示G G中结点数、边数、面数中结点数、边数、面数,则有则有 n-m+r=2n-m+r=2称此式为称此式为欧拉公式欧拉公式.性质性质2 2：(必要条件必要条件)设设G G是有是有n n 个结点、个结点、m m条边的连条边的连通简单平面图通简单平面图,若若n3,n3,则则 m3n-6.m3n-6.第56页，本讲稿共62页常用图常用图用此性质用此性质2 2可以判定一个图不是平面图可以判定一个图不是平面图例如证明例如证明K K5 5不是平面图不是平面图:K K5 5中有中有