《图论(第一次)课件》由会员分享，可在线阅读，更多相关《图论(第一次)课件（65页珍藏版）》请在金锄头文库上搜索。
1、数学建模,图论与网络模型,2,引例,例1 最短路问题（SPPshortest path problem） 一名货柜车司机奉命在最短的时间内将一车 货物甲地运往乙地。从甲地到乙地的公路网纵横 交错，因此有多种行车路线，这名司机应选择哪 条线路呢?,3,例2 公路连接问题 某一地区有若干个主要城市，现准备 修建高速公路把这些城市连接起来，使得 从其中任何一个城市都可以经高速公路直 接或间接到达另一个城市。,4,例3 指派问题（assignment problem） 一家公司经理准备安排名员工去完成项 任务，每人一项。由于各员工的特点不 同，不同的员工去完成同一项任务时所获 得的回报是不同的。,5,
2、例4 中国邮递员问题（CPPchinese postman problem） 一名邮递员负责投递某个街区的邮件。 如何为他（她）设计一条最短的投递路线?,6,例5 旅行商问题（TSPtraveling salesman problem） 一名推销员准备前往若干城市推销产 品。如何为他（她）设计一条最短的旅行 路线?,7,例6 运输问题（transportation problem） 某种原材料有M个产地，现在需要将原 材料从产地运往N个使用这些原材料的工 厂。(假定M个产地的产量和N家工厂的需 要量已知，单位产品从任一产地到任一工 厂的运费已知),8,上述问题有两个共同的特点： 一是它们的目的
3、都是从若干可能的安排或方 案中寻求某种意义下的最优安排或方案，数学上 把这种问题称为最优化或优化(optimization）问 题； 二是它们都易于用图形的形式直观地描述和 表达，数学上把这种与 图相关的结构称为网络 （network）。,9,图论的应用： 图与网络是运筹学（Operations Research）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。可为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的的概念、理论和方法，可以对该模型求解,10,图论方法专题,最短路问题及其算法,E图与H图,四
4、,最小生成树问题,图的矩阵表示,11,一. 图的概念 一个图 G=, 其中 V(G): 是G的结点的非空集合. (V(G),简记成V. E(G): 是G的边的集合. 有时简记成E. 结点(Vertices): 用 表示, 旁边标上该结点的名称. 边(Edges): 有向边: 带箭头的弧线. 从u到v的边表示成 无向边:不带箭头的弧线. u和v间的边表示成 (u,v),12,在图中, 结点的相对位置不同, 边的曲直、长短无关紧要. 邻接点: 与一边关联的两个结点. u v a b,e2, ,邻接边: 关联同一个结点的两条边. ,e1,v,环:只关联一个结点的边. ,平行边:关联于同一对结点的若干
5、条边.,二. 有向图与无向图 有向图:只有有向边的图. 无向图:只有无向边的图. 三. 零图与平凡图 孤立结点:不与任何边关联的结点. u 零图:仅由一些孤立结点构成的图. 即此图的边的集合E=,G: a b c,平凡图:仅由一个孤立结点构成的零图. |V(G)|=1,|E(G)|=0,13,四. 简单图与多重图 简单图:不含有环和平行边的图. 多重图: 含有平行边的图. 五. 无向图结点v的度(degree): 1.定义:G是个无向图, vV(G), 结点v所关 联边数,称之为结点v的度. 记作 deg(v).(或d(v). deg(a)=3 deg(b)=5 deg(c)=4 deg(d)
6、=2 一个环给结点的度是2. 2.无向图的结点度序列: 令G=是无向图, V=v1,v2,v3,vn, 则称: (deg(v1), deg(v2),deg(v3), ,deg(vn) 为图G的结点度序列. 例如上图的结点度序列为:(3,5,4,2) 3.图的最大度(G)与最小度(G) :G=是无向图, (G) =maxdeg(v)|vG (G) =mindeg(v)|vG,14,右图中(G)=5 (G)=2 4. 定理 每个无向图所有结点度总 和等于边数的2倍.即,定理(握手定理)每个无向图中,奇数度的结点必为偶 数个.(在一次集会中,与奇数个人握手的人,共有偶数个.),六. k-正则图:一个
7、无向简单图G中,如(G)=(G)=k 则称G为k-正则图.,15,课堂练习: 1.下面哪些数的序列,可能是一个图的度数序列? 如果可能,请试画出它的图. 哪些可能不是简单图? a) (1,2,3,4,5) b) (2,2,2,2,2) c) (1,2,3,2,4) d) (1,1,1,1,4) e) (1,2, 2,4,5) 2.已知无向简单图G中,有10条边,4个3度结点,其余结点的 度均小于或等于2,问G中至少有多少个结点?为什么?,16,a) (1,2,3,4,5) b) (2,2,2,2,2) c) (1,2,3,2,4) d) (1,1,1,1,4) e) (1,2, 2,4,5)
8、解:a)不是, 因为有三个数字是奇数. b) c) d)是. e) 不是简单图,因为它有5个结点, 有一个结点度为5, 必然有环或平行边.,2.解:已知边数|E|=10, deg(v)=2|E|=20 其中有4个3度结点, 余下结点度之和为: 20-34=8 因为G是简单图, 其余每个结点度数2, 所以至少还有4 个结点. 所以G中至少有8个结点.,17,七. 有向图结点的出度和入度:(in degree out degree) G=是有向图,vV v的出度: 从结点v射出的边数. 记作deg+(v) 或 dego(v) v的入度: 射入结点v的边数. 记作deg-(v) 或 degi(v)
9、一个结点v的出度与入度之和，称之为结点v的度。 degi(a)=2 degi(b)=2 degi(c)=1 degi(d)=1 dego(a)=2 dego(b)=3 dego(c)=1 dego(d)=0 定理G=是有向图, 则G的所有结点的出度之和 等于入度之和.,18,八. 完全图 1.无向完全图 定义:G是个简单图, 如果每对不同结点之间都有边相连 则称G是个无向完全图. 如果G有n个结点, 则记作Kn.,定理 无向完全图Kn, 有边数,19,定理 有n个结点的有向简单完全图有边数为n(n-1). 2).有向完全图(有向全图) (它与完全关系图一致) G是个有向图如果任何两个结点之间都
10、有相互可达的边, 则称它是有向完全图. 其图形如下:,2. 有向图的完全图 1).有向简单完全图:G是个有向简单图,如果任何两个不 同结点之间都有相互可达的边,则称它是有向简单完全图. 例如:,20,所以有n个结点的有向完全图, 有边数 n2. 九.子图和生成子图 1.子图:设G=是图,如果G=且VV, V, EE, 则称G是G的子图.,可见G1,G2,G3都是K5的子图.,21,2. 生成子图（支撑子图） 设G=是图, G=, G是G的子图,如果V=V, 则称G是G的生成子图。 上例中, G1是K5的生成子图。,22,*十一.相对补图 设G1=是图G=的子图,如果有G2= 使得E2=E-E1
11、且V2中仅包含E2中的边所关联的结点,则称 G2是G1相对G的补图.,可见G2是G3相对G的补图. G3也是G2相对G的补图. 而G1不是G3相对G的补图(多了一个结点). 但是G3是G1相对G的补图. 可见: 相对补图无相互性.,23,十二. 图的同构 设G=和G=是图,如果存在双射f:VV 且 任何vi,vjV,若边(vi,vj)E,当且仅当 边(f(vi),f(vj)E, (或若边E,当且仅当 边E),则称G与 G同构,记作GG. (同构图要保持边的“关联”关系) 例如:右边所示的两个图: G= G=,构造映射f:VV,两个图同构的必要条件: 1.结点个数相等. 2.边数相等. 3.度数
12、相同的结点数相等. 4. 对应的结点的度数相等.,24,下面是同构的图:,右面两个图不同构: 左图中四个3度结点 构成四边形,而右图, 则不然.,课堂练习:请画出K4的所有不同构的生成子图.,25,练习:请画出K4的所有不同构的生成子图.,本节要求:准确掌握如下基本概念和定理: 1.有向边,无向边,孤立结点,平行边,环. 2.有向图,无向图,零图,平凡图,简单图,多重图,完全图,子图,生成子图,补图,相对补图 3.四个定理(关于结点度,以及结点度与边数关系) 4.图的同构 (会判断).,26,2. 路与回路,在实际应用中,比如在市内乘出租车去参观一个博览会, 一定要司机选一条最短的路. 到博览
13、会后, 最好选一条这 样到路径,使得每个展台都参观一次后,再回到原来存包 处. 这就是路与回路的问题. 一. 路的概念 1.路的定义: 给定图G= 设v0 ,v1,v2,vnV, e1,e2,enE 其中ei是关联vi-1 ,vi的边, 则称结点和边的交叉序列 v0 e1v1 e2v2envn是连接v0到vn的路. v0是此路的起点,vn是此路的终点. 路中含有的边数 n称之为路的长度.,例如上图中: v0 e2v3 e6v2是一条长度为2的路.,27,如果图是个简单图, 则路可以只用结点序列表示. 如右图中, 路:abcad 如果图是个有向图, 则路可以 只用边序列表示. 如有向图中 e1
14、e5e2e3 e6 是一条路. 2. 回路:如果一条路的起点和终点是一个结点,则称此路是 一个回路. 如右图中的 L1=v0 e1v1 e5v3 e6v2e4v0 L2= v0 e1v1 e5v3e2v0 3. 迹与闭迹 如果一条路中,所有边都不同,则称此路为迹. 如果一条回路中,所有边都不同,则称此回路为闭迹.,28,4. 通路与圈 如果一条路中,所有结点都不同,则称此路为通路. 如果一条回路中,除起点和终点外,其余结点都不同,则称此回路为圈. 例如右图中: L1=v0 e1v1 e5v3 e6v2e4v0 L2= v0 e1v1 e5v3e2v0 L3=v0 e1v1 e5v3 e2v0
15、e3v3 e6v2e4v0 L1和L2是闭迹, 也是圈. L3是闭迹,而不是圈.,29,定理 在一个有n个结点的图中,如果从结点vi到vj存在 一条路,则从vi到vj必存在一条长度不多于n-1的路.,30,应用:摆渡人Ferryman,狼Wolf,羊Sheep,干草Hay过河问 题 . 如何摆渡使得它们不能互相伤害. 实际上,这是个在图上 找一条路的问题.,31,二. 无向图的连通性 1.两个结点是连通的: 在无向图中,结点u和v之间如果存在一条路, 则称u与v是连通的. 我们规定: 对任何结点u, u与u是连通的. 2.结点之间的连通关系是个等价关系. 令G=是无向图, R是V上连通关系,
16、即 R=|u和v是连通的 显然R具有自反、对称和传递性. 于是可以求商集V/R. 例1. 给定图G1如右上图所示:,V/R=a,b,g,c,d,e,f,h 例2.给定图G2如右下图所示:,V/R=1,3,5,2,4,6,32,3.连通分支:令G=是无向图, R是V上连通关系, 设R 对V的商集中有等价类V1,V2,V3, Vn ,这n个等价类构成 的n个子图分别记作G(V1),G(V2),G(V3), G(Vn),并称它 们为G的连通分支. 并用W(G)表示G中连通分支数. 下边例中,G2,G3,W(G1)=3 W(G2)=2 W(G3)=1 4.连通图: 如果一个图G只有一个连通分支(W(G)=1),则称G是连通图. W(G3)=1 , G3是连通图,33,定理: 图G=是连通的,当且仅当 对V的任何分 成V1、V2的划分,恒存在一条边, 使得
