您所在位置: 网站首页 / 第七章图 习题答案.doc / 文档详情
第七章图 习题答案.doc 立即下载
2024-08-16
约2万字
约24页
0
116KB
举报 版权申诉
预览加载中,请您耐心等待几秒...

第七章图 习题答案.doc

第七章图习题答案.doc

预览

免费试读已结束,剩余 19 页请下载文档后查看

10 金币

下载文档

如果您无法下载资料,请参考说明:

1、部分资料下载需要金币,请确保您的账户上有足够的金币

2、已购买过的文档,再次下载不重复扣费

3、资料包下载后请先用软件解压,在使用对应软件打开

第七章图习题答案
基础知识:
7.1在图7.23所示的各无向图中:(1)找出所有的简单环。(2)哪些图是连通图?对非连通图给出其连通分量。(3)哪些图是自由树(或森林)?答:(1)所有的简单环:(同一个环可以任一顶点作为起点)(a)1231(b)无(c)1231、2342、12341(d)无(2)连通图:(a)、(c)、(d)是连通图,(b)不是连通图,因为从1到2没有路径。具体连通分量为:(3)自由树(森林):自由树是指没有确定根的树,无回路的连通图称为自由树:(a)不是自由树,因为有回路。(b)是自由森林,其两个连通分量为两棵自由树。(c)不是自由树。(d)是自由树。
7.2在图7.24(下图)所示的有向图中:(1)该图是强连通的吗?若不是,则给出其强连通分量。(2)请给出所有的简单路径及有向环。(3)请给出每个顶点的度,入度和出度。(4)请给出其邻接表、邻接矩阵及逆邻接表。答:(1)该图是强连通的,所谓强连通是指有向图中任意顶点都存在到其他各顶点的路径。(2)简单路径是指在一条路径上只有起点和终点可以相同的路径:有v1v2、v2v3、v3v1、v1v4、v4v3、v1v2v3、v2v3v1、v3v1v2、v1v4v3、v4v3v1、v3v1v4、另包括所有有向环,有向环如下:v1v2v3v1、v1v4v3v1(这两个有向环可以任一顶点作为起点和终点)(3)每个顶点的度、入度和出度:D(v1)=3ID(v1)=1OD(v1)=2D(v2)=2ID(v2)=1OD(v2)=1D(v3)=3ID(v3)=2OD(v3)=1D(v4)=2ID(v4)=1OD(v4)=1(4)邻接表:(注意边表中邻接点域的值是顶点的序号,这里顶点的序号是顶点的下标值-1)vertexfirstedgenext┌─┬─┐┌─┬─┐┌─┬─┐0│v1│─→│1│─→│3│∧│├─┼─┤├─┼─┤└─┴─┘1│v2│─→│2│∧│├─┼─┤├─┼─┤2│v3│─→│0│∧│├─┼─┤├─┼─┤3│v4│─→│2│∧│└─┴─┘└─┴─┘逆邻接表:┌─┬─┐┌─┬─┐0│v1│─→│2│∧│├─┼─┤├─┼─┤1│v2│─→│0│∧│├─┼─┤├─┼─┤┌─┬─┐2│v3│─→│1│─→│3│∧│├─┼─┤├─┼─┤└─┴─┘3│v4│─→│0│∧│└─┴─┘└─┴─┘邻接矩阵:0101001010000010
7.3假设图的顶点是A,B...,请根据下述的邻接矩阵画出相应的无向图或有向图。┌┓┌┓|01100||0111||00010||1011||00010||1101||10001||1110||01010|┕┙┕┙(a)(b)答:
7.4假设一棵完全二叉树包括A,B,C...等七个结点,写出其邻接表和邻接矩阵。解:邻接表如下:┌─┬─┐┌─┬─┐┌─┬─┐0│A│─→│1│─→│2│∧│├─┼─┤├─┼─┤├─┼─┤┌─┬─┐1│B│─→│0│─→│3│─→│4│∧│├─┼─┤├─┼─┤├─┼─┤├─┼─┤2│C│─→│0│─→│5│─→│6│∧│├─┼─┤├─┼─┤└─┴─┘└─┴─┘3│D│─→│1│∧│├─┼─┤├─┼─┤4│E│─→│1│∧│├─┼─┤├─┼─┤5│F│─→│2│∧│├─┼─┤├─┼─┤6│G│─→│2│∧│└─┴─┘└─┴─┘邻接矩阵如下:0110000100110010000110100000010000000100000010000
7.5对n个顶点的无向图和有向图,采用邻接矩阵和邻接表表示时,如何判别下列有关问题?(1)图中有多少条边?(2)任意两个顶点i和j是否有边相连?(3)任意一个顶点的度是多少?答:对于n个顶点的无向图和有向图,用邻接矩阵表示时:(1)设m为矩阵中非零元素的个数无向图的边数=m/2有向图的边数=m(2)无论是有向图还是无向图,在矩阵中第i行,第j列的元素若为非零值,则该两顶点有边相连。(3)对于无向图,任一顶点i的度为第i行中非零元素的个数。对于有向图,任一顶点i的入度为第i列中非零元素的个数,出度为第i行中非零元素的个数,度为入度出度之和。当用邻接表表示时:(1)对于无向图,图中的边数=边表中结点总数的一半。对于有向图,图中的边数=边表中结点总数。(2)对于无向图,任意两顶点间是否有边相连,可看其中一个顶点的邻接表,若表中的adjvex域有另一顶点位置的结点,则表示有边相连。对于有向图,则表示有出边相连。(3)对于无向图,任意一个顶点的度则由该顶点的边表中结点的个数来决定。对于有向图,任意一个顶点的出度由该顶点的边表中结点的个数来决定,入度则需遍历各顶点的边表。(用逆邻接表可容易地得到其入度。)
7.6n个顶点的连通图至少有几条边?强连通图呢?答:n个顶点的连通图至少有n-1条边,强连通图
查看更多
单篇购买
VIP会员(1亿+VIP文档免费下)

扫码即表示接受《下载须知》

第七章图 习题答案

文档大小:116KB

限时特价:扫码查看

• 请登录后再进行扫码购买
• 使用微信/支付宝扫码注册及付费下载,详阅 用户协议 隐私政策
• 如已在其他页面进行付款,请刷新当前页面重试
• 付费购买成功后,此文档可永久免费下载
全场最划算
12个月
199.0
¥360.0
限时特惠
3个月
69.9
¥90.0
新人专享
1个月
19.9
¥30.0
24个月
398.0
¥720.0
6个月会员
139.9
¥180.0

6亿VIP文档任选,共次下载特权。

已优惠

微信/支付宝扫码完成支付,可开具发票

VIP尽享专属权益

VIP文档免费下载

赠送VIP文档免费下载次数

阅读免打扰

去除文档详情页间广告

专属身份标识

尊贵的VIP专属身份标识

高级客服

一对一高级客服服务

多端互通

电脑端/手机端权益通用