《图的基本概念》PPT课件.ppt

05:08,1,1.图论与网络,本课程（BII）主要内容,3.排队论,4.存储论,5.决策论,2.统筹方法,（3）运输网络问题,随机服务系统（随机过程）,（1）基本知识,（2）常见模型,*排队最优化,确定性存储模型,随机存储模型,确定型决策,（1）图的基本概念,（2）网络规划问题,确定型统筹问题：,A）统筹图概念、规则,B）关键路线,C）时间参数及其计算,非确定型决策,风险型决策,05:08,2,第一部分 图与网络,第一章 图论基本知识,数学分支，可以解决线性规划等问题,05:08,3,第一节 图的定义,图论是近数十年来得到蓬勃发展的一个数学分支，它的理论与方法在许多领域中得到广泛的应用并取得了丰硕的成果成为运筹学一个重要分支。 线性规划、整数规划、运输问题等等，有时也可以用图论的方法来构造模型并求解，而且由于图的结构的直观性，更有助于我们分析问题和描述问题，何况有些研究对象，如交通网，它本身就是一个大网络，用图论的方法研究更方便。,本节主要介绍关于无向图和有向图的定义等基本概念,05:08,4,1.1 图,引例1：哥尼斯堡七桥问题,引例2：交通网络问题,北京,郑州,西安,成都,05:08,5,引例:若出发点x1可运送货物到接收点y1和y2，发送点x2可运送货物到接收点y1、y2、y3，用点和线表示发送点、接收点以及它们之间的关系，得到下图：,x1,x2,y3,y2,y1,对象,关系,直观描述：,语言描述：,表示具体事物的点（顶点）集合和表示事物之间关系的边集合组成图,对象,（1）G=V,E，V=v1,v2, vn,E=e1,e2, en,（2）G=(eij,(vi,vj)|i,j=1 n,数学描述：,05:08,6,1.1.1 无向图,1无向图 设V是一个有n个顶点的非空集合，V=v1 ,v2 ,vn ,E是一个有m条边的集合，E=e1 ,e2 ,em ，E中任一条边e 是V的一个无序元素对u,v（或vi,vj。i j）（这里uv），则V和E这两个集合组成了一个无向图，记G=（V，E）。 vi和vj称为边eij端点， eij称为vi,vj的关联边， vi与vj为相邻顶点。,一、无向图定义,根据边有没有方向，将图分为无向图和有向图，下面分别讲解：,v4,05:08,7,示例：,无向图G=(V,E)，其中V=v1,v2,v3,v4,v5，E=e1,e2,e3,e4,e5,e6,e7,G=(e12,(v1,v2), (e14,(v1,v4), (e15,(v1,v5), (e24,(v2,v4), (e34,(v3,v4), (e45,(v4,v5), (e51,(v5,v1),1.1.1 无向图,05:08,8,1.1.1 无向图,二、无向图术语,平行边（多重边）：两边有一样的端点，如e15和e51,简单图：图中无平行边,完备图：图中任意两个端点之间有且仅有一条边,链：两个端点之间的连接路径,一个链的起始端点不为同一个称为开链，否则为闭链（圈）,初等链：一个链中无重复的顶点。也称为路。,回路（初等圈）一个圈中除第一和最后顶点外各点均不相同。或者说闭合的路称为回路。,简单链：一个链中无重复的边。,05:08,9,1.1.2 有向图,设顶点的非空集合V=v1 ,v2 ,vn ,边的集合 E=e1 ,e2 ,em ，E中任一条边e 是V的一个有序元素对u,v（这里uv），则V和E这两个集合组成了一个有向图，记作有向图G=（V，E）。,u称为起点，v称为终点,有向图中，边e(u,v)称为连接顶点u和v的弧。,一、有向图定义,05:08,10,二、有向图术语,完备图：图中任意两个端点之间恰好有两条边（u,v）和（v，u）。,平行边：两边有一样的起终点,简单图：图中无平行边,基本图：去掉有向图方向就能得到一个无向图,初等链：顶点都不相同的链（和基本图中的初等链相同）。,1.1.2 有向图,e2,v4,05:08,11,1.1.3 其它术语,网络：如果图的边上带有数量指标（或称为权值），这样的图称为网络.,05:08,12,连通图：图（无向）中任意两点都连通称为连通图，否则称为分割图。 图的可达性（有向图）：若图G中从顶点u 到v之间存在单向路径，则称u可达v。 强连通图：若图G内任两点之间相互可达，则称图G为强连通图。,1.1.3 其它术语,05:08,13,欧拉链：连通无向图G中，如果存在经过G中每条边一次且仅一次的链，称为欧拉链。 欧拉图:起点和终点相同的欧拉链称为图G的欧拉环游。 如果图G中存在一条欧拉环游，称图G为欧拉图。,1.1.3 其它术语,05:08,14,子图：设G1=(V1，E1)，G=(V，E)，若V1V，E1 E，则称G1为G的子图，即G1 G。 生成子图：当V1=V，E1 E，则称G1为G的生成子图（支撑子图）。,1.1.3 其它术语,05:08,15,树：无圈的无向连通图G称为树。记为T=（V，E）。 树T的六个等价定义： 1、T连通且无回路。 2、T无回路且只有n-1条边。 3、T连通且有n-1条边 4、T无回路，但不相邻的两个顶点之间联一条边，恰得到一个回路。 5、T连通，但取掉任一条边后就不连通了。 6、T的任意两个顶点之间恰有一条初等链。,1.1.3 其它术语,05:08,16,生成树：如果树满足 称T为G的生成树（T为G的生成子图又是一棵树）。亦即图G中能将各顶点以最少边数连接起来的树。 一个无向图可有若干个生成树。,1.1.3 其它术语,05:08,17,图的同构：若图G=（V，E）与G=（V，E）的顶点集合V 和V以及边的集合E与E之间在保持关联关系的条件下一 一对应，则称图G和G为同构的。（简单说，若两个图顶点和边都能对应上称为同构图）,1.1.3 其它术语,05:08,18,图的顶点阶数：无向图G=（V，E）中与顶点v关联的边数称为顶点的阶数，记作(v)。 (v)为偶数，称v为偶阶顶点；(v)为奇数称为奇阶顶点。 两个常用定理： 定理1 任一图中所有顶点的阶数之和为偶数。 定理2 任一图中所有奇阶顶点的个数必为偶数。,1.1.3 其它术语,05:08,19,1.2 图的矩阵表示,一、无向图的矩阵表示,矩阵数值aij规则：,aij=,0，顶点vi与边eij不关联,1，顶点vi与边eij关联,1. 无向图的关联矩阵,无向图的关联矩阵形式：,顶点,边,e1 e2 ei en,v1 . vi . vn,aij,05:08,20,示例：,特点：,目的：,关联矩阵,无向图,1、矩阵第i行中1的个数就是与顶点vi相关的边的数量,2、矩阵中j列中1的个数恒为2，因为每边只有2个端点,05:08,21,2. 无向图的邻接矩阵,无向图的邻接矩阵形式：,顶点,顶点,v1 v2 vi vn,v1 . vi . vn,aij,矩阵数值aij规则：,aij表示顶点vi和vj之间边的数量,示例：,特点：,1、邻接矩阵是对称矩阵,2、邻接矩阵比关联矩阵小,05:08,22,二、有向图的矩阵表示,aij=,0， 顶点vi与边eij不关联,1， 顶点vi为边eij起点,1. 有向图的关联矩阵,与无向图的关联矩阵形式一样，但数值aij规则为：,-1，顶点vi为边eij终点,示例：,特点：矩阵中j列中的元素之和为0,05:08,23,2. 有向图的邻接矩阵,邻接矩阵形式以及矩阵数值aij规则与无向图一样,v1 v2 v3 v4 v5,v1 v2 v3 v4 v5,0,1,0,1,1,0,0,0,1,0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,0,示例：,特点：,1、矩阵第i行元素之和