ImageVerifierCode 换一换
格式:PPT , 页数:23 ,大小:472KB ,
资源ID:1585654      下载积分:12 文钱
快捷下载
登录下载
邮箱/手机:
温馨提示:
快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。 如填写123,账号就是123,密码也是123。
特别说明:
请自助下载,系统不会自动发送文件的哦; 如果您已付费,想二次下载,请登录后访问:我的下载记录
支付方式: 支付宝    微信支付   
验证码:   换一换

加入VIP,省得不是一点点
 

温馨提示:由于个人手机设置不同,如果发现不能下载,请复制以下地址【https://www.wenke99.com/d-1585654.html】到电脑端继续下载(重复下载不扣费)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: QQ登录   微博登录 

下载须知

1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。
2: 试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。
3: 文件的所有权益归上传用户所有。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 本站仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

版权提示 | 免责声明

本文(离散数学第7章-图论-习题.ppt)为本站会员(99****p)主动上传,文客久久仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知文客久久(发送邮件至hr@wenke99.com或直接QQ联系客服),我们立即给予删除!

离散数学第7章-图论-习题.ppt

1、第 7章 习题课练习 7-1( 6)简单图的最大度小于结点数。证明:设简单图 G中有 n个结点。任取一个结点 v, 由已知 G是简单图没有环和重边, v至多和 n-1个结点相邻, 也即 deg(v) n-1, 而 (G) max deg(v) n-1, 因此 最大度小于结点数。练习 7-2( 2):若无向图 G中恰有两个奇数度的结点,则这两个结点之间必有一条路。证明:设无向图 G中两个奇数度的结点为 u和 v。从 u开始构造一条迹,即从 u出发经关联于结点 u的边 e1到达结点u1,若 deg(u1)为偶数 ,则必可由 u1再经关联于结点 u1的边 e2到达结点 u2,如此继续下去 ,每边只取

2、一次 ,直到另一个奇数度结点停止 ,由于图 G中只有两个奇数度结点 ,故该结点或是 u或是 v。 如果是 v,那么从 u到 v的一条路就构造好了。如果仍是结点 u,此路是闭迹。闭迹上每个结点都是关联偶数条边 ,而 deg(u)为奇数 ,所以至少还有一条关联于结点 u的边不在此闭迹上。继续从 u出发 ,沿着该边到达另一个结点 u1,依次下去直到另一个奇数度结点停下。这样经过有限次后必可到达结点 v,这就是一条从 u到 v的路。练习 7-2( 3):若图 G是不连通的,则 G的补图 G是连通的。证明:若 G=是不连通的,可设图 G的连通分支为GV1,GV2,GV m(m2)。由于任意两个连通分支

3、GVi,GVj不连通,因此 Vi与 Vj之间的连线在补图中,在 G中任取两个结点 u和 v,则 u和 v的位置有两种情况:1)若 u和 v均在同一个连通分支 GVi中 ,根据上面的分析,可在另一个连通分支 GVj( ij)中取一个结点 w,使得u与 w, v 与 w在 G中连通,故有 u w v,即 u与 v在 G中连通2)若 u与 v分别属于两个不同的连通分支 GVi与 GVj,由上面的分析可知, u与 v在 G中连通。故当图 G不连通时,则补图 G是连通的7-2( 4) :当且仅当 G的一条边 e不包含在 G的回路中时, e才是 G的割边。证明:必要性。( e是 G的割边)设 e是连通图

4、G的割边, e关联的两个结点是 u和 v。 如果 e包含在G的一个回路中,那么除边 e=(u,v)外还有另一条分别以 u和 v为端点的路,所以删去边 e后, G仍为连通图,这与 e是割边相矛盾。充分性。如果边 e不包含在 G的任一条回路中,那么连接结点 u和 v的边只有 e, 而不会有其它连接 u和 v的任何路。因为如果连接 u和 v还有不同于边 e的路,此路与边 e就组成一条包含边 e的回路,从而导致矛盾。所以删去边 e后, u和 v就不连通,故边 e是割边。300页( 2) 如果 u可达 v, 它们之间可能不止一条路,在所有这些路中,最短路的长度称为 u和 v之间的距离(或短程线),记作

5、d, 如果从 u到 v是不可达的,则通常写成 d =距离矩阵为0 1 2 1 0 1 1 1 0 1 1 2 0dij=1表示存在边 。300页( 3)用 Warshall算法求可达性矩阵。邻接矩阵为0 0 0 0 01 0 1 1 01 0 0 0 00 0 1 0 00 0 0 0 0A=i=1时,因为 A的第一行全为 0,所以 A不变。i=2时,因为 A的第 2列全为 0,所以 A不变。i=3时,因为 A2, 3=A4, 3=1,将第 3行加到第 2行和第 4行。0 0 0 0 01 0 1 1 01 0 0 0 01 0 1 0 00 0 0 0 0A=i=4时,因为 A4,2=1,将

6、第四行加到第 2行, A不变。i=5时,因为 A的第 5列全为 0,所以 A不变。 0 0 0 0 01 0 1 1 01 0 0 0 01 0 1 0 00 0 0 0 0P=故 A的可达性矩阵为:距离矩阵为0 1 0 1 1 1 0 2 1 0 0300页( 4):写出如图 7-3.11所示的图 G的完全关联矩阵,并验证其秩如定理 7-3.2所述。e1 e2 e3 e4 e5 e6 e7 e8 e9A 1 0 0 0 0 1 0 1 0B 0 1 1 0 0 0 1 0 0C 0 0 0 1 1 0 0 1 0D 1 1 0 0 0 0 0 0 1E 0 0 0 0 1 1 1 0 0F 0 0 1 1 0 0 0 0 1完全关联矩阵为 :此图为连通图,由定理7-3.2,其秩为 5。311页( 2)构造一个欧拉图,其结点数 v和 边数 e满足下述条件a)v, e的奇偶性一样。b) v, e的奇偶性相反。如果不可能,说明原因。v=3,e=3v=5,e=5v=4,e=4 v=4,e=6v=7,e=8v=6,e=7无向图 G具有一条欧拉回路,当且仅当 G是连通的,并且所有结点度数全为偶数。下面的图中所有结点度数全为偶数,所以都是欧拉图。

Copyright © 2018-2021 Wenke99.com All rights reserved

工信部备案号浙ICP备20026746号-2  

公安局备案号:浙公网安备33038302330469号

本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。