第5章--图的基本概念.pptVIP

第5章 图的基本概念 教学要求1. 掌握图的基本概念2. 掌握图的矩阵表示3. 理解图的最短路径及关键路径概念和 求解 几个相关概念: 设G=V,E为一无向图或有向图 有限图：若V,E都是有穷集合 n阶图：若∣V∣=n 零图：若E=? 平凡图：若E=?，且∣V∣=1 5.3 图的矩阵表示 1.无向图的关联矩阵M（G）矩阵中的元素为顶点与边的关联次数mij,记为（mij）nxm。 Mij的值只可能为0（表示不关联），1（表示关联），2 （表示环），矩阵的行数为顶点数，列数为边数例：图5-11 3.有向图的邻接矩阵A（D）矩阵中的元素为顶点与顶点邻接的边的条数aij,记为（ aij ）nxn。 矩阵的行数为顶点数，列数也为顶点数例：图5-13 5.4 最短路径及关键路径 一 权的概念权指权重。 权重是一个相对的概念，是针对某一指标而言。某一指标的权重是指该指标在整体评价中的相对重要程度。 权重表示在评价过程中，对被评价对象的不同侧面的重要程度的定量分配，对各评价因子在总体评价中的作用进行区别对待。求权重就是求出每项指标在某事件中的重要性/比重/贡献度…… 二 边帯权图对于有向图或无向图的每条边附加一个实数，通常用w(e)表示，则称w(e) 为边上的权。有向图或无向图连同各边上的权称为边帯权图 三 最短路径问题 1. 什么是最短路径？一个顶点到另一个顶点所有通路中带权最小的通路 2. 标号算法（步骤见P129） 例： P129-130【例题5.3】 四 关键路径问题 1.什么是关键路径？关键路径是占用时间最长的关键活动组成的序列，在你按照事件的先后顺序画出网络图之后，计算出各个路径上所花费的时间，其中占用时间最长的即是关键路径。 2. 算法（步骤见P131） 小 结 握手定理的应用 图的矩阵表示 求解最短路径问题和关键路径问题 * * 引言 图论起源于一些智力游戏与难题的研究。如著名的哥尼斯堡七桥问题：既不重复又不遗漏地一次相继走遍这七座桥？ 大数学家欧拉将原来的七桥问题抽象概括成了如下的关系图： 人们将类似这样的抽象图形应用于更加广泛的领域，点可以泛化为某个客观对象，边泛化为两个客观对象之间的关系，这样，图就为某种二元关系提供了数学模型 预备知识 卡氏积：A×B=｛＜x,y＞|x∈A∧y∈B｝ 有序对: ＜x,y＞≠ ＜ y, x ＞ 无序积：A＆B=｛(x,y)|x∈A∧y∈B｝ 无序对: (x,y)= ( y, x ) 多重集: ｛a,a,a,b,b,c｝ ≠ ｛a,b,c｝ 5.1 无向图和有向图 1.无向图的定义: P118 定义5.1 例: G=V,E V=｛v1,v2,v3,v4,v5｝ E=｛(v1,v2),(v2,v2),(v2 ),(v1,v3),(v1,v3 ), (v1,v4) ｝ 2.有向图的定义: P118 定义5.2 例: G=V,E V=｛v1,v2,v3,v4,v5｝ E=｛v1,v1,v3,v2, v3,v2 ,v3,v4,v2,v4 , v4,v5, v1,v2 ｝ 3.无向图的关联和相邻定义: P119 定义5.3 4.有向图的关联和相邻定义: P119 定义5.4 5.度数(端点的度数)定义: P119 定义5.5 注意： 对于无向图,每个端点只有一种度数，对于有向 图,每个端点的度数分为出度和入度度数两种 最大度:△(G)=max ｛ d(v)|v∈V｝ 最小度:δ(G)=min ｛ d(v)|v∈V｝ 最大出度:△+(D)=max ｛ d+(v)|v∈V｝ 最大入度:△-(D)=max ｛ d-(v)|v∈V｝ 最小出度: δ+(D)=min ｛ d+(v)|v∈V｝ 最小入度: δ-(D)=m in｛ d-(v)|v∈V｝ 6.握手定理: P120 定理5.1,5.2 ∑d(vi)=2m ∑d+(vi)+ ∑d-(vi) =m n i=1 n n i=1 i=1 推论:任何图中,度为奇数的顶点个数为偶数 相关概念:度数序列(一般并不按大小排列，以点集中顶点顺序排列) 例:P120 例5.1 7.平行边和重数: P121定义5.6 注意:有向图中的平行边是始点相同,终点相同的边 几个相关概念:多重图,简单图 8.完全图: P120定义5.7 注意:对有向图， 存在既有有向边u,v,又有有向边 v , u 例:P121 图5-2 9. 子图与母图 P121定义5.8 几个相关概念:真子图,生成子图,导出子图 例:P121 图5-3 10.补