第一节 图与子图 .ppt
《第一节 图与子图 .ppt》由会员分享,可在线阅读,更多相关《第一节 图与子图 .ppt(14页珍藏版)》请在文库网上搜索。
1、 第一节 图与子图图与网络无向图的基本概念有向图和网络关联矩阵和邻接矩阵关联矩阵邻接矩阵主要结论子图 无向图的基本概念无向图G:一个有序二元组(N,E),记为G=(N,E)G的点集合:N=n1,n2, ,nnG的边集合:E=eij,且eij是一个无序二元组ni,nj,记为eij= ni,njeij的端点:若eij= ni,nj,则称eij连接ni和nj ,点ni和nj称为eij的端点环:两个端点重合为一点的边孤立点:不与任何边关联的点例无向图的基本概念关联:一条边的端点称为与这条边关联邻接:与同一条边关联的端点称为是邻接的,同时如果有两条边有一个公共端点,则称这两条边是邻接的有限图:任何图G=
2、(N,E)若N和E都是有限集合,则称G为有限图空图:没有任何边的图平凡图:只有一个点的图简单图:一个图,即没有环,也没有重边。例如(a)是简单图,但(b)就不是简单图。续一无向图的基本概念完全图:每一对点之间均有一条边相连的图(如图一)二分图G=(S,T,E) :存在一个二分划(S,T),使得G的每一条边有一个端点在S中,另一个端点在T中完全二分图:S中的每一个点和T中的每一个点都相连的简单二分图(如图二)简单图G的补图 :与G有相同顶点集合的简单图,且补图中的两个点邻接当且仅当它们在G中不邻接(如图三)续二图二图一 图三有向图有向图G:一个有序二元组(N,A),记为G=(N,A)G的点集合:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第一节