版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、第三章连接性问题,3.1连接性3.2块3.3建立可靠通信网络,链路,链路,3.1连接性,BE(G)为图G的k边缘切口B=k。图g中的“边连接”(edgeconnectivity)=将g设为非连接或普通图所需的最小边数。(如果G是非规则连接图形,则=G的关键点数下限。),示例:=0G是普通的或不连接的。=包含1G连接和切割边。(Kn)=n-1(n0)。如果g是简单图形=-1GK。图G为k边连接(k-edgeconnected)(G)k移除至少k条边以使G成为非连接或普通图。例如,所有不重要的连接图都是单边连接。顶点子集V称为G的“顶点切削”(vertexcut)G-V未连接。顶点子集V为g的k-
2、(顶部)“点切削”(vertexcut)V为g,V=k。显然,如果g是非环连接图,则v为g的1点切削v是g的切削点。完全图案化。图g的“connectivity(连接性)”(=g为非连接性或常规图必须删除的最小顶点数)。)在范例: 3中,=1G连接在一起,有1点切削。(K)=-1。(G)=-1G的预设简单图片是完整图片。图G必须至少移除k-连接(k-connected)(G)k的顶点,才能使G不连接或成为常规图。例如,所有不重要的连接图都是1-连接。整理3.1。证明:第一个证据:当g是普通图时,0,结论成立。如果在g是非规则图形的情况下选取v=d(v)=,则E=是g的边切削,因此结论成立。另一
3、个证据:可以将g设置为简单、连接、不完整的图。任一方面-边切削b和b的任一方面e=xy。现在,在B-e的每个边上选择x和y以外的端点。使这些端点的集合成为s。很容易,S-1。记录H=G-S。(I)如果h未连接,则S是g的点切削,因此S-1。(ii)如果h已连接,则e=xy为h的切割边。但是,(H)=(G)-S-(-1)3,因此x和y至少有一个H的切削点,且设定为x。Sx是g的点切削。S 1 .练习,3.1.1(a)证明:如果G是k边连接,并且k0和E是G的随机k边集合,则(G-E)2。(b)对于k0,求k-连通图G和G的k-顶点集s (G-S)2。3.1.2证明:如果g连接到k边缘,则为k/2。3.1.3(a)证明:如果g是简单图形且-2,则=。(b)找到简单的图片g,然后创建=-3。3.1.4(a)证明:如果g是简单图形和/2,则=。找到简单的图g,如(b)=(/2)-1所示。3.1.5证明:如果g是简单图形,并且(k-2)/
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 原地双手胸前传接球(教学设计)人教版体育六年级上册
- Python课程第三阶段第23课:函数版-信息管理系统-Python教学设计
- Lesson141-142(教学设计)-2023-2024学年新概念英语第一册
- 小学校园欺凌辅导技巧
- 02《济南的冬天》-2024-2025学年七年级语文上册精美拓展教学教学设计(统编版2024)
- Module 1 Unit 1 Do you use chopsticks in the UK (教案)-2024-2025学年外研版(一起)英语三年级上册
- 4《古诗三首》教学设计-2024-2025学年统编版语文三年级上册
- Unit 1 Making friends Part B Lets learn(教学设计)-2024-2025学年人教PEP版(2024)英语三年级上册
- 《7 小导游》(教案)-2023-2024学年五年级下册综合实践活动粤教版
- 1《a o e》 教学设计-2024-2025学年语文一年级上册统编版
- 2024至2030年成都市酒店市场前景调查及投资策略分析报告
- 2024年全民健康生活方式宣传月专题讲座课件
- 2024-2025学年江苏省南京市语文小学五年级上学期自测试卷及解答参考
- 人教版2024-2025学年七年级地理上册 第一章 地球【单元测试卷】
- 医疗保障基金相关制度、政策培训通知、总结、简报整改报告
- 2024年四川能投高县电力限公司招聘(高频重点提升专题训练)共500题附带答案详解
- “农业经理人”职业技能大赛考试题库-下(多选、判断题)
- 排粪造影临床应用参考幻灯片
- 2024年山东港口职业技能大赛(集装箱装卸工)理论考试题库(含答案)
- 2024年天津市专业技术人员继续教育网公需课答案
- 小学生自我介绍竖版
评论
0/150
提交评论