图论 王树禾 答案.pdf_第1页
图论 王树禾 答案.pdf_第2页
图论 王树禾 答案.pdf_第3页
图论 王树禾 答案.pdf_第4页
图论 王树禾 答案.pdf_第5页
已阅读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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论