图论 —数学建模与系统仿真 主讲:王晓峰 E-mail:xfwang8280126.com
图 论 ——数学建模与系统仿真 主讲：王晓峰 E-mail:xfwang828@126.com
图论的基本概念 图的概念 1、图的定义 2、顶点的次数 3、子图 二、图的矩阵表示 1、关联矩阵 2、邻接矩阵 返回
图 论 的 基 本 概 念 一、 图 的 概 念 1、图的定义 2、顶点的次数 3、子图 二、 图 的 矩 阵 表 示 1、 关联矩阵 2、 邻接矩阵 返回
图的定义 定义有序三元组G=(V,E,Y称为一个图 1]V={v1,V2…,vn}是有穷非空集,称为顶点集, 其中的元素叫图G的顶点 2]E称为边集,其中的元素叫图G的边 [3]平是从边集E到顶点集V中的有序或无序的元素 偶对的集合的映射,称为关联函数 例1设G=(VE,平),其中 V={v1,v2,v3,v4}, Ee,e,eB, e, es) H(e1)=VV2,平(e2)=vV3,H(e3)=vv4,H(e4)=vv4,(e5)=v3 G的图解如图 2 g g 5
定义 有序三元组G=(V,E, ) 称为一个图. [1] V={ , , , } 1 2 n v v v 是有穷非空集，称为顶点集， 其中的元素叫图 G 的顶点. [2] E 称为边集，其中的元素叫图 G 的边. [3] 是从边集 E 到顶点集 V 中的有序或无序的元素 偶对的集合的映射，称为关联函数. 例1 设 G=(V,E, )，其中 V={v1 ,v2 , v3 , v4 }， E={e1 , e2 , e3 , e4 , e5 } , 1 1 2 2 1 3 3 1 4 4 1 4 5 3 3 (e ) = v v ,(e ) = v v ,(e ) = v v ,(e ) = v v ,(e ) = v v . G 的图解如图. 图的定义
定义在图G中,与V中的有序偶(,v对应的边e,称为图的有向 边(或弧),而与V中顶点的无序偶νν相对应的边e,称为图 的无向边每一条边都是无向边的图,叫无向图;每一条边都是 有向边的图,称为有向图;既有无向边又有有向边的图称为混 图 定义若将图G的每一条边e都对应一个实数w(e),称we)为边的权, 并称图G为赋权图 规定用记号v和E分别表示图的顶点数和边数
定义 在图 G 中，与 V 中的有序偶( vi， vj )对应的边 e，称为图的有向 边（或弧），而与 V 中顶点的无序偶 vi vj 相对应的边 e，称为图 的无向边.每一条边都是无向边的图，叫无向图；每一条边都是 有向边的图，称为有向图；既有无向边又有有向边的图称为混 合图. 定义 若将图 G 的每一条边 e 都对应一个实数 w(e)，称 w(e)为边的权， 并称图 G 为赋权图. 规定用记号 和 分别表示图的顶点数和边数
g 常用术语 (1)端点相同的边称为环. (2)若一对顶点之间有两条以上的边联结,则这些边称为重边 (3)有边联结的两个顶点称为相邻的顶点,有一个公共端点的边 称为相邻的边 (4)边和它的端点称为互相关联的 (5)既没有环也没有平行边的图,称为简单图 (6)任意两顶点都相邻的简单图,称为完备图,记为K,其中n 为顶点的数目 (7)若V=Y,XY=,X中任两顶点不相邻,Y中任两顶 点不相邻,称G为二元图;若Ⅹ中每一顶点皆与Y中一切顶点 相邻,称为完备二元图,记为Kn,其中m,n分别为X与Y的顶 点数目
常用术语： （１）端点相同的边称为环． （２）若一对顶点之间有两条以上的边联结，则这些边称为重边． （３）有边联结的两个顶点称为相邻的顶点，有一个公共端点的边 称为相邻的边． （４）边和它的端点称为互相关联的． （５）既没有环也没有平行边的图，称为简单图． （６）任意两顶点都相邻的简单图，称为完备图，记为 Kn，其中 n 为顶点的数目． ( 7)若 V=X Y，X Y= ，X 中任两顶点不相邻，Y 中任两顶 点不相邻，称 G 为二元图；若 X 中每一顶点皆与 Y 中一切顶点 相邻，称为完备二元图，记为 Km,n，其中 m,n 分别为 X 与 Y 的顶 点数目．
返回
返回
顶点的次数 定义(1)在无向图中,与顶点ⅴ关联的边的数目(环算两次) 称为v的次数,记为d(v) (2)在有向图中,从顶点ⅴ引出的边的数目称为v的出度, 记为d(y),从顶点ⅴ引入的边的数目称为的入度,记为d(y), d()=d(v)+d(y)称为v的次数. al(v4)=2 z(v4)=4 (4)=5
顶点的次数 定义 （１）在无向图中，与顶点 v 关联的边的数目（环算两次） 称为 v 的次 数，记为 d(v)． （２）在有向图中，从顶点 v 引出的边的数目称为 v 的出 度， 记为 d + (v)，从顶点 v 引入的边的数目称为的入度，记为 d - (v)， d(v)=d+ (v)+d- (v)称为 v 的次数． d(v4 ) = 4 ( ) 5 ( ) 3 ( ) 2 4 4 4 = = = − + d v d v d v
子 定义设图G(VEH)G1=(V1E,H1) (1)若V1sV,E1E,且当∈E1时,H(e)"(e),则称G1是G的子图 特别的,若V1=V,则G1称为G的生成子图 (2)设V1V,且V≠Φ,以V1为顶点集、两个端点都在V1中的 图G的边为边集的图G的子图,称为G的由Ⅴ导出的子图,记为GV1 (3)设E1E,且E≠Φ,以E1为边集E1的端点集为顶点集的图G的子图, 称为G的由E1导出的子图记为GE1 g v3e 5 e:2 了 G GRv,v,v5) l,2, 返回
子图 定义 设图 G=(V,E, ),G1 =(V1 ,E1 ,1 ) (1) 若 V1 V，E1 E,且当 e E1时，1 (e)= (e),则称 G1 是 G 的子图． 特别的，若 V1 =V，则 G1称为 G 的生成子图． (2) 设 V1 V，且 V1 ，以 V1为顶点集、两个端点都在 V1中的 图 G 的边为边集的图 G 的子图，称为 G 的由 V1导出的子图，记为 G[V1 ]. (3)设 E1E,且 E1 ,以 E1为边集,E1的端点集为顶点集的图 G 的子图, 称为 G 的由 E1导出的子图,记为 G[E1 ]. G G[{v1 ,v4 ,v5 }] G[{e1 ,e2 ,e3 }] 返回
兴联 对无向图G,其关联矩阵M=(mn)g,其中 若v与e相关联 =10若v与e不关联 注:假设图为简单图 1000 M=|11010v 00110|v 对有向图G,其关联矩阵M=(m1),其中 若v是e的起点 1若v是e的终点 若v与e,不关联 返回
关联矩阵 对无向图Ｇ，其关联矩阵Ｍ＝ ( ) mi j ，其中： 若 与 不关联 若 与 相关联 i j i j i j v e v e m = 0 1 M= 4 3 2 1 1 2 3 4 5 0 1 1 0 1 0 0 1 1 0 1 1 0 1 0 1 0 0 0 1 v v v v e e e e e 对有向图Ｇ，其关联矩阵Ｍ＝ ( ) mi j ，其中： = − 若 与 不关联 若 是 的终点 若 是 的起点 i j i j i j i j v e v e v e m 0 1 1 注：假设图为简单图 返回
接矩 对无向图G,其邻接矩阵A=(an),,其中: 若ν与ν,相邻 ay=10若v与不相邻 注:假设图为简单图 5 1110 对有向图G=(V,E),其邻接矩阵A=(an),其中: 若(v,,)∈E an=10若(,v)gE
邻接矩阵 对无向图Ｇ，其邻接矩阵 = ( ) A ai j ，其中： 若 与 不相邻 若 与 相邻 i j i j i j v v v v a = 0 1 注：假设图为简单图 A= 4 3 2 1 1 2 3 4 1 1 1 0 0 1 0 1 1 0 1 1 0 1 0 1 v v v v v v v v 对有向图Ｇ＝（Ｖ，Ｅ），其邻接矩阵 = ( ) A ai j ，其中： v v E v v E a i j i j i j = 若（ ， ） 若（ ， ） 0 1