已阅读5页，还剩2页未读， 继续免费阅读
版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
文档简介
图论第一次作业 By byh |E(G)|, 2 |E(G)| 2 G 1.1 举出两个可以化成图论模型的实际问题 略 1.2 证明其中 是单图 证明：（思路）根据单图无环无重边的特点，所以 最大的情形为任意两个顶点间有一条边相连，即极 端情况为。 1.4 画出不同构的一切四顶单图 0条边：1条边： 2条边：3条边： 4条边：5条边： 6条边： 1.10G 当且仅当存在可逆映射: ，使得 ，其中和是单图。（证明充分性和必要性） 必要性 若 ，由定义可得，存在可逆映射: : () 当且仅当 = 时， = ()，所以 充分性 定义: ()，使得 和 ()一一对应，于 是可逆，且 = 的充要条件是 = ，得 1.12求证(a) , = ，(b)是完全二分图，则 1 4 2 (a)对于, ，将顶集分为和，使得 = , ， = ， = ， = ，对于中的每一顶点，都和中所有顶点 相连，所以 , = (b)设的顶划分为,， = , = ，则 , - = 2 4 证明： (a)第一个序列考虑度数7,第二个序列考虑6,6,1 (b)将顶点v分成两部分v和v v = v|v = vi, 1 i k, v = v|v = vi, k i n 以v点为顶的原图的导出子图度数之和小于 然后考虑剩下的点贡献给这k个点的度数之和最大可能为 1.37：证明无环图含二分生成子图，使得 1 2 对每 个 ()成立。 证明： 任取X, Y满足X UY = V(G)， X Y = ，且令X,Y中的顶两两不相邻，所得的 图是H且是二分子图，令H是G边数最多的二分生成子图，若存在v V(G)， 使得dH(v) dG(v)，不妨设v X，则将v所连的边取消，换成dG(v) - dH(v) 条边，且将v加入Y中，于是H的边数增
温馨提示
- 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025-2030中国骑行服装透气速干技术比较研究报告
- 塑料厨房置物架创新创业项目商业计划书
- 家电租赁业务平台创新创业项目商业计划书
- 掌上学习证书颁发器创新创业项目商业计划书
- 复古波点邮差包创新创业项目商业计划书
- 复古皮质+木质混搭沙发创新创业项目商业计划书
- 家用音频设备语音控制家电创新创业项目商业计划书
- 2025至2030全球及中国实心充气轮胎行业发展趋势分析与未来投资战略咨询研究报告
- 2026届安徽省安庆市怀宁二中化学高二上期末监测模拟试题含答案
- 河北省邢台市清河县清河中学2026届高一化学第一学期期末联考模拟试题含解析
- 2025年湖南长沙水业集团有限公司春季校园招聘24人笔试参考题库附带答案详解
- 水稻病虫害防治课件
- 湖北省武汉市部分学校2026届高三上学期九月调研考试英语（含答案）
- 2025-2030食品舆情监测体系分析及危机公关与品牌声誉管理战略研究
- 【核心素养目标】Unit 3 My School Section B (1a-1d)公开课一等奖创新教学设计 人教英语七年级上册
- 家政服务员清洁家居课件
- 第二十一课 让身体保持最佳状态说课稿-2025-2026学年初中心理健康北师大版2013九年级下册-北师大版2013
- 2025年校服双送检实施方案
- 制造业质量检测流程及异常处理
- 学堂在线 临床中成药应用 章节测试答案
- 四年级道德与法治上册：第十课我们所了解的环境污染 第1课时课件
评论
0/150
提交评论