给定一个数据结构G＝（V，E），V＝｛V1，V2，V3，V4，V5，V6，V7，V8｝，E＝｛<V1,V2>, <V3,V4>, <V5,V8>, <V5,V6>, <V1,V3>, <V4,V7>, <V4,V5>, <V2,V4>, <V4,V6>｝。则G是（）

给定数据结构(V，E)，V为结点的有限集合，V＝{V1，V2，V3，V4，V5，V6，V7，V8)，E是V上关系的集合。E＝{＜V1，V2＞，＜V3，V4＞，＜V5，V8＞，＜V5，V6＞，＜V1，V3＞，＜V4，V7＞，＜V4，V5＞，＜V2，V4＞，＜V4，V6＞)，它所对应的图形是(44)，这是(45)。

图的存储结构主要有邻接表和(46)，若用邻接表来存储一个图，则需要保存一个(47)存储的结点表和若干个(48)上存储的关系表(又称边表)。

A．

B．

C．

D．

给定数据结构(V，E)，y为节点的有限集合，V={V1，V2，V3，V4，V5，V6，V7，V8)，E是V上关系的集合。

E={＜V1，V2＞，＜V3，V4)，＜V5，V6＞，＜V5，V6＞，＜V1，V3＞，＜V4，V7＞，＜V4，V5＞，＜V2，V4＞，＜V4，V6＞)，它所对应的图形是(42)，这是(43)。

图的存储结构主要有邻接表和(44)，若用邻接表来存储一个图，则需要保存一个(45)存储的节点表和若干个(46)存储的关系表(又称边表)。

A．

B．

C．

D．

问题描述:给定一个赋权无向图G=(V,E),每个顶点都有权值w(v).如果,且对任意(u,V)∈E有u∈U或v∈U,就称U为图G的一个顶点覆盖.G的最小权顶点覆盖是指G中所含顶点权之和最小的顶点覆盖.

算法设计:对于给定的无向图G,设计一个优先队列式分支限界法,计算G的最小权顶点覆盖.

数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m,表示给定的图G有n个顶点和m条边,顶点编号为1,2,...,n.第2行有n个正整数表示n个顶点的权.接下来的m行中,每行有2个正整数u和v,表示图G的一条边(u,v).

结果输出:将计算的最小权顶点覆盖的顶点权值和以及最优解输出到文件output.txt.文件的第1行是最小权顶点覆盖顶点权之和;第2行是最优解xi(1≤i≤n),xi=0表示顶点i不在最小权顶点覆盖中,xi=1表示顶点i在最小权顶点覆盖中.

给定一个有向线图G=＜ V,E＞,用A表示G的邻接矩阵、可把图的距离矩阵定义成：

(a)求出图8.36给出的有向图的距离矩阵。

(b)如何从一个距离矩阵求可达性矩阵。

(c)说明如果图G的距离矩阵的元素除对角线元素外都不是零用不是∞，那么图G是强连通的。

给定二元完全树G=＜V，E＞，试证明：|E|=2(n-1)，其中n是树叶数．

给定平面图G，且G是自对偶的。证明|E|=2(V|-1)。