数学建模图论篇精品文稿.ppt
《数学建模图论篇精品文稿.ppt》由会员分享,可在线阅读,更多相关《数学建模图论篇精品文稿.ppt(62页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、数学建模图论篇数学建模图论篇第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
2、)(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 邻接边邻接边:关联同一个结点的两条边关联同一个结点的两条边.环环:只关联一个结点的边只关联一个结点的边.平行边平行边:在两个结点之间关联的多条边在两个结点之间关联的多条边.二二.有向图
3、与无向图有向图与无向图 有向图有向图:只有有向边的图只有有向边的图.无向图无向图:只有无向边的图只有无向边的图.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四四.简单图与多重图简单图与多重图 简单图简单图:不含有环和平行边的图不含有环和
4、平行边的图.多重图多重图:含有平行边的图含有平行边的图.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,一个环给结点的度是一
5、个环给结点的度是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
6、(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是个简单图是个简单图,如果每对不同结点之间都有边相连如果每对
7、不同结点之间都有边相连则称则称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第
8、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).有向完全图有向完全图(有向全图有向全图
9、)()(它与完全关系图一致它与完全关系图一致)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 a
10、b 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页图论原理图论
11、原理图的同构图的同构设设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页图论原理图论原理两个图
12、同构的必要条件两个图同构的必要条件: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页图论原理图论原理如果一个结点对可对应若干条边,这种边成为多重如果一个结点对可对应若干条边,这种边成为多重边,包含多重边的图成为多重图。边,包含多重边的图成为多重图。带权图带权图(赋权图赋权
13、图)定义定义:设设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
14、,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称之为路的长度称之为路的长度.如果其中每条边的终点总是下一条边的起点,则边的如果其中每条边的终点总是下一条边的起点,则边的
15、序列可以简写成(序列可以简写成(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页图论原理图论原理回路回路:如果一条路的起点和终点是一个结点如果一条路的起点和终点是一个结点,则称此路则称此路是一个回路是一个回路.如果一条路中所有如果一条路中所有边都不同边都不同,则称此路为则称此路为迹迹或或简单通路简单通路.如果一条如果一条回路回路中所有中所有边都不同边都不同,则称此回路为则称此回路为闭迹闭迹或或简
16、简单回路单回路.如果一条路中所有如果一条路中所有结点都不同结点都不同,则称此路为则称此路为基本通路基本通路.如果一条如果一条回路回路中所有中所有结点都不同结点都不同,则称此路为则称此路为基本回路基本回路.一条基本通路一定是简单通路,但是一条简单通路不一条基本通路一定是简单通路,但是一条简单通路不一定是基本通路一定是基本通路第17页,本讲稿共62页图论原理图论原理性质:性质:一个有向一个有向(n,m)(n,m)图中任何基本通路长度都小于图中任何基本通路长度都小于或者等于或者等于n-1n-1,任何基本回路长度都小于或者等于,任何基本回路长度都小于或者等于n n。定义:定义:从一有向图的结点从一有向
17、图的结点a a到另一结点到另一结点b b间如果存在一间如果存在一条通路,则称从条通路,则称从a a到到b b是可达的。是可达的。无向图的连通性无向图的连通性定义:定义:一个无向图一个无向图G G,如果它的任何两个结点间均是,如果它的任何两个结点间均是可达的,这称图可达的,这称图G G为连通图;否则,称为非连通图。为连通图;否则,称为非连通图。定义:定义:一个有向图一个有向图G G,如果忽略其边的方向得到的无,如果忽略其边的方向得到的无向图是连通的,这称为有向的连通图。向图是连通的,这称为有向的连通图。第18页,本讲稿共62页图论原理图论原理对于有向的连通图,还可以进一步将其分为三类:对于有向的
18、连通图,还可以进一步将其分为三类:在简单有向图在简单有向图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)单向连通单向连通.
19、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中中:有欧拉路有欧拉路:acbefgdcfhacbe
20、fgdcfh在在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有两个奇数度结点有两个奇数度
21、结点:就从一个奇数度结点出发就从一个奇数度结点出发,每当到达一个每当到达一个偶数度结点偶数度结点,必然可以再经过另一条边离开此结点必然可以再经过另一条边离开此结点,如此重复下去如此重复下去,经过所有边后到达另一个奇数度结点经过所有边后到达另一个奇数度结点如果如果G G无奇数度结点无奇数度结点,则可以从任何一个结点出发则可以从任何一个结点出发,去构造一条欧拉去构造一条欧拉路路.a bc d1 24 3第21页,本讲稿共62页图论原理图论原理推论推论:无向图无向图G G具有欧拉回路具有欧拉回路,当且仅当当且仅当G G是连通的是连通的,且且所有结点的度都是偶数所有结点的度都是偶数.从此推论得知从此推
22、论得知,七桥问题的图不是欧拉图七桥问题的图不是欧拉图.欧拉路与欧拉回路问题欧拉路与欧拉回路问题,也称一笔画问题也称一笔画问题.A B C De1e5e7e6e3e4e2第22页,本讲稿共62页图论原理图论原理汉密尔顿图汉密尔顿图(H(H图图)(Hamilton)(Hamilton图图)HamiltonHamilton是英国数学家是英国数学家,在在19591959年年,他提出他提出HamiltonHamilton回路回路.H H图起源于一种游戏图起源于一种游戏,这个游戏就是所谓周游世界问题这个游戏就是所谓周游世界问题.例如例如,某个城市的街道如图所示某个城市的街道如图所示:该城市的所有交叉路口都
23、有形象各该城市的所有交叉路口都有形象各异的精美的雕塑异的精美的雕塑,吸引着许多游客吸引着许多游客,人人都想找到这样的路径人人都想找到这样的路径:游遍各游遍各个景点再回到出发点个景点再回到出发点-H-H回路回路.第23页,本讲稿共62页图论原理图论原理1.1.定义定义:设设G=G=是个无向有限图是个无向有限图,汉密尔顿路汉密尔顿路:通过通过G G中每个结点恰好一次的路中每个结点恰好一次的路.汉密尔顿回路汉密尔顿回路(H(H回路回路):):通过通过G G中每个结点恰好一次中每个结点恰好一次的回路的回路.汉密尔顿图汉密尔顿图(H(H图图):):具有汉密尔顿回路具有汉密尔顿回路(H(H回路回路)的图的
24、图.例如右图中例如右图中,就是就是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回路
25、回路)。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页图论
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 建模 图论篇 精品 文稿
限制150内