已阅读5页，还剩10页未读， 继续免费阅读
版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
文档简介
1、图的连通性G1G2在无向图中，如果从顶点V到V有路径，则称V和V是连通的。在有向图中，如果从顶点V到V有路径，并且从V到V有路径，则称V和V是强连通的。如果对于图中任意两个顶点Vi,Vj,Vi和Vj都是连通的，则称连通图。G4G3连通分量=无向图中的极大连通子图G1G1的三个连通分量有向图中，极大强连通子图=强连通分量G1G1的两个强连通分量 V是连通图G的一个顶点子集。在G中删去V及与V相关联的边后图不连通，则称V是G的割顶集。最小割顶集中顶点的个数，记成K(G)，叫做G的连通度。规定：K(完全图)顶点数-1K(不连通图)K(平凡图)0K(G)l时，割顶集中的那个顶点叫做割顶。没有割顶的图叫
2、做块，G中成块的极大子图叫做G的块。G1G2K(G1)=0K(G2)=1G4G3K(G3)=3K(G4)=5-1=4威廉王迷宫前向边（实线部分）后向边（虚线部分）Dfn(x):顶点x被首次访问的次序。Dfn(x)=I表示x是第I个首次被访问的节点称为深度优先搜索序数。Dfs树 如U不是根，U成为割顶当且仅当存在U的某一个儿子顶点S，从S或S的后代点到U的祖先点之间不存在后向边如r被选为根，则r成为割顶当且仅当它有不止一个儿子点。顶点U的标号函数LOW(U):LOW(U)=mindfn(),LOW(s),dfn(W)其中：S是U的一个儿子，（U，W）是后向边LOW(U)是U或U的后代所能追溯到的最早（序号小）的祖先结点序号。顶点Ur作为图的割顶当且仅当U有一个儿子，使得LO
温馨提示
- 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年人教新课标九年级科学上册阶段测试试卷含答案
- 2025年苏人新版八年级地理下册月考试卷
- 2025年人教B版拓展型课程化学下册月考试卷含答案
- 二零二五版企业员工宿舍租赁管理规范合同2篇
- 2025年度企业安全生产培训合作协议合同范本4篇
- 二零二五版新能源项目暖通系统设计咨询合同4篇
- 2025年二零二五农业机械化项目设备采购及安装合同4篇
- 二零二五版借贷房屋买卖合同违约责任免除合同4篇
- 2025年农业信息化建设旧房购置合同书4篇
- 二零二五版影视配音合同范本集4篇
- 幼儿园学习使用人民币教案教案
- 2023年浙江省绍兴市中考科学真题（解析版）
- 语言学概论全套教学课件
- 大数据与人工智能概论
- 《史记》上册注音版
- 2018年湖北省武汉市中考数学试卷含解析
- 测绘工程产品价格表汇编
- 《肾脏的结构和功能》课件
- 装饰图案设计-装饰图案的形式课件
- 护理学基础教案导尿术catheterization
- ICU护理工作流程
评论
0/150
提交评论