网友您好, 请在下方输入框内输入要搜索的题目:
下面关于图的存储的叙述中正确的是()。
A.用邻接表法存储图,占用的存储空间大小只与图中边数有关,而与顶点个数无关
B.用邻接表法存储图,占用的存储空间大小与图中边数和顶点个数都有关
C.用邻接矩阵法存储图,占用的存储空间大小与图中顶点个数和边数无关
D.用邻接矩阵存储图,占用的存储空间大小只与图中边数有关,而与顶点个数无关
图论部分习题参考答案(二)8.2 路径与回路第5题证明:(1) 设w为分图个数。由公式m(n-w)(n-w+1)/2可得,w=3时,m(6-3)(6-3+1)/2。所以分图个数w2时,边数不能超过6条。今有7条边,所以分图个数不能超过2。(2). 任意由一个孤立顶点和一个Kn-1组成的图都满足条件。第12题解:强分图集为:v1,v2,v3,v4,v5,v6,v7,v8,v9,v10。弱分图集:v1,v2,v3,v4,v5,v6,v7,v8,v9,v10。单向分图集:v1,v2,v3,v4,v5,v6,v7,v8,v9,v10。第13题解答参见课件。第16题解答参见课件。第18题解:(a)图中a到z的最短路径为8。(b)图中a到z的最短路径为14。解答过程略,不清楚的个别解答。第19题解:(a)图的欧拉路径为:v1,v2,v3,v4,v6,v5,v3,v6,v7,v2,v8,v7,v1,v8。(b)图的欧拉回路为:v1,v2,v3,v4,v5,v2,v6,v4,v1第29题解:(1) 根据最邻近算法,起始于a点的哈密尔顿回路为:acbdea。(2) 起始于d点的哈密尔顿回路为:deacbd。(3) 最短的哈密尔顿回路为:adebca。解答过程不清楚的,个别解答。8.3 图的矩阵表示第1题解:(1).图的邻接矩阵为:(2).,由此可知,从v1到v4长度为1,2,3和4的路径分别为1,1,2,3条。(3). ,由于AAT中第(2,3)个元素为1,说明从v2和v3引出的边能共同终止于同一个结点的只有一个,即v4。AAT中第(2,2)个元素为2,说明v2的引出次数为2。由于ATA中第(2,3)个元素为0,说明没有结点引出的边同时终止于v2和v3。ATA中第(2,2)个元素为3,说明v2的引入次数为3。(4).,(5).,所以强分图的顶点集为:v1,v2,v3,v4第3题解:该图的邻接矩阵为:可达矩阵为:,8.5 二部图第1题解:图a,图b是二部图,图c不是二部图。第4题:解:由题构造一个二部图G=,其中X=P1,P2,P3,P4,.,P10。Y=a1,a2,3,.,10,表示合格工作岗位的关系,图略。可求一个最大匹配:M(P1,9),(P2,2),(P3,6),(P4,3),(P5,4),(P6,1),(P7,5)根据该匹配分配工作能使无工作的人最少。
用邻接矩阵表示图时,矩阵元素的个数与顶点个数是否相关?与边数是否相关?
正确答案:用邻接矩阵表示图时,矩阵元素的个数与顶点个数无关;但和边数有关。
用邻接矩阵存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小只与图中顶点个数有关,而与图的边数无关。
正确答案:正确
在顶点个数为n的无向图G中,若对于任意一对顶点都存在邻接关系,则无向图G共有()条边。
正确答案:n(n-1)/2
用邻接矩阵表示图时,矩阵元素的个数与顶点个数是否相关?与边数是否相关?
正确答案:用邻接矩阵表示图时,矩阵元素的个数与顶点个数无关;但和边数有关。
存储图的邻接矩阵中,邻接矩阵的大小不但与图的顶点个数有关,而且与图的边数也有关。
正确答案:正确
更多 “图论习题参考答案(二)” 相关考题
- 组成颈白线的肌肉有()。A、胸骨甲状肌B、胸骨舌骨肌C、甲状舌腹肌D、二腹肌E、肩胛舌骨肌
- 单选题以下哪项是有关虚拟机的正确术语?()A Hypervisor(系统管理程序)B Guest OS(客户机操作系统)C Virtual Center(虚拟中心)D HostOS(主机操作系统)
- 麻醉药品
- 硬膜外麻醉行控制性降压时,患者对降压药的反应是()。A、与全身麻醉相同B、比全身麻醉反应敏感C、比全身麻醉反应迟钝D、有时比全身麻醉反应迟钝,有时比全身麻醉反应敏感E、不确定
- 前庭水管的外口位于颞骨岩部()。A、前面B、下面C、后面D、底面E、尖端
- 药师可以分为:药房药师、生产企业药师、经营企业药师、药物科研单位药师、药检所药师、临床药师、药品监督管理药师。
- 下列选项中,属于八里河自然保护区的主要保护对象的是()。A.白鹳B.白头鹤C.大鸨D.琵琶E.鸳鸯
- 简述野生药材资源保护的范围及分级要满足的具体条件。
- 男,61岁,患有高血压,同时伴有2型糖尿病,尿蛋白(+)。选择最佳降压药物为()。A、利尿剂B、钙拮抗剂C、ACEID、α受体阻滞剂E、β受体阻滞剂
- 单选题A server contains a 3 disk RAID 5 array. The red LED is illuminated on one of the drives. Which of the following should the server administrator perform?()A Replace the driveB Restore the drive from backupC Reboot the serverD Reconfigure RAID 5 to RAID 10