七章图的基本概念.ppt
《七章图的基本概念.ppt》由会员分享,可在线阅读,更多相关《七章图的基本概念.ppt(39页珍藏版)》请在三一文库上搜索。
1、第七章 图的基本概念,7.1 无向图及有向图 7.2 通路、回路、图的连通性 7.3 图的矩阵表示,作 业,7.1 无向图及有向图,设A,B为两集合,称 a,baAbB 为A与B的无序积,记作AB 将无序对a,b记作(a,b).,无向图,一个无向图G是一个二元组,即G,其中, (1)V是一个非空的集合,称为G的顶点集,V中元素称为顶点或结点; (2)E是无序积VV的一个多重子集,称E为G的边集,E中元素称为无向边或简称边.,有向图,一个有向图D是一个二元组,即D,其中, (1)V同无向图中的顶点集; (2)E是卡氏积的多重子图,其元素称为有向边,也简称边.,给每条边赋与权的图G=称为加权图,
2、记为G=,其中W表示各边权的集合。,2,3.5,7.8,设ek(vi,vj)为无向图G中的一条边,称vi,vj为ek的端点, ek与vi(或vj)是彼此关联的. 无边关联的顶点称为孤立点.若一条边所关联的两个顶点重合,则称此边为环.,ek与vi(或vj)的关联次数,1,vivj,2,vi vj,0,vi(vj)不是ek的端点,b,a,v,V,设G为一无向图或有向图 (1)若V,E都是有穷集合,则称G是有限图. (2)若Vn,则称G为n阶图 (3)若E,则称G为零图特别是,若此时又有V1,则称G为平凡图.,相邻,设无向图GV,E,vi, vjV, ek,elE. (1)若存在一条边e以vi, v
3、j为端点,即e(vi, vj),则称vi, vj是彼此相邻的,简称相邻的 (2)若ek, el至少有一个公共端点,则称ek, el是彼此相邻的,简称相邻的,始点 终点,以上两定义对有向图也是类似的 若ek vi, vj,除称vi, vj是ek的端点外,还称vi是ek的始点, vj是ek的终点,vi邻接到vj,vj邻接于vi.,度,设G为一无向图,vjV,称vj作为边的端点的次数之和为vi的度数,简称度,记作d(vj). 称度数为1的顶点为悬挂顶点,它所对应的边为悬挂边.,设D为一有向图,vjV, 称vj作为边的始点的次数之和,为vj的出度,记作d+(vj); 称vj作为边的终点的次数之和,为v
4、j的入度,记作d-(vj); 称vj作为边的端点的次数之和,为vj的度数,简称度,记作d(vj). 显然d(vj)d + (vj)d- (vj).,deg(v1)3,deg+(v1)2,deg-(v1)1; deg(v2)3,deg+(v2)2,deg-(v2)1; deg(v3)5,deg+(v3)2,deg-(v3)3; deg(v4)deg+(v4)deg-(v4)0; deg(v5)1,deg+(v5)0,deg-(v5)1; 其中,v5是悬挂结点,为悬挂边。,最大度和最小度,对于图G,记 (G)maxd(v)vV, (G)mind(v)vV,分别称为G的最大度和最小度.,若DV,E是
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 七章图 基本概念
链接地址:https://www.31doc.com/p-3182617.html