设G是一个有n个顶点的有向图,从顶点i发出的边的最大费用记为max（i).（1)证明旅行售货员回路的费

设G是一个有n个顶点的有向图,从顶点i发出的边的最小费用记为min(i).

(1)证明图G的所有前缀为x[1,i]的旅行售货员问路的费用至少为:

式中,a(u,v)是边(u,v)的费用.

(2)利用上述结论设计一个高效的上界函数,重写旅行售货员问题的回溯法,并与主教材中的算法进行比较.

设无向图G有n个顶点和e条边，每个顶点Vi的度为di(1≤i≤n>，则e=__________。【福州大学1998二、2(2分)】

问题描述:给定有向图G=(V,E).设P是G的一个简单路(顶点不相交)的集合.如果V中每个顶点恰好在P的条路上,则称P是G的一个路径覆盖.P中路径可以从V的任何一个项点开始,长度也是任意的,特别地,可以为0.G的最小路径覆盖是G的所含路径条数最少的路径覆盖.

设计一个有效算法求一个有向无环图G的最小路径覆盖.

[设V={1,2,...,n},如下构造网络G₁=(V1,E₁):

每条边的容量均为1.求网络G₁的(x₀,y₀)最大流.]

算法设计:对于给定的有向无环图G,找出G的一个最小路径覆盖.

数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数n和m.n是给定有向无环图G的顶点数,m是G的边数.接下来的m行,每行有2个正整数i和j,表示一条有向边(i,j).

结果输出:将最小路径覆盖输出到文件output.txt.从第1行开始,每行输出一条路径.文件的最后一行是最少路径数.

问题描述:给定一个无向图G=(V.E),设是G的顶点集.对任意,若u∈U且v∈V-U,就称(u,1)为关于顶点集U的条割边.顶点集U的所有割边构成图G的一个割.G的最大割是指G中所含边数最多的割.

算法设计:对于给定的无向图G,设计一个优先队列式分支限界法,计算G的最大割.

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

结果输出:将计算的最大割的边数和顶点集U输出到文件output.txt.文件的第1行是最大割的边数;第2行是表示顶点集U的向量x(1≤i≤n),x=0表示顶点i不在项点集U中,x=1表示顶点i在顶点集U中.

问题描述:给定一个赋权无向图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在最小权顶点覆盖中.

阅读下列函数说明和c代码，将应填入(n)处的字句写在答题纸的对应栏内。

【说明】

函数int Toplogical(Linded WDipaph G)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE-网，图中顶点从1～n依次编号，图G的存储结构采用邻接表表示，其数据类型定义如下：

typedefstruct Gnode{ /* 邻接表的表结点类型*/

iht adjvex; /* 邻接顶点编号*/

iht weight; /* 弧上的权值*/

street Gnode *nextarc; /* 指示下一个弧的结点*/

}Gnode;

typedef struct Adjlist{ /* 邻接表的头结点类型*/

char vdata; /*顶点的数据信息*/

struct Gnode *Firstadj; /* 指向邻接表的第一个表结点*/

}Adjlist;

typedef street LinkedWDigraph{ /* 图的类型*/

int n, e; /* 图中顶点个数和边数*/

struct Adjlist *head; /*指向图中第一个顶点的邻接表的头结点 */

} LinkedWDigraph;

例如，某AOE-网如图5-1所示，其邻接表存储结构如图5-2所示。

【函数】

iht Toplogical(LinkedWDigraph G)

{ Gnode *p;

intj, w, top = 0;

iht *Stack, *ye, *indegree;

ye = (int *)malloe((G.n+1) * sizeof(int));

indegree = (int *)malloc((G.n+1)*sizeof(int)); /* 存储网中各顶点的入度*/

Stack = (int *)malloe((G.n+1)*sizeof(int)); /* 存储入度为0的顶点的编号*/

if(!ve||!indegree || !Stack) exit(0);

for (j = 1;j ＜= G.n;j++) {

ve[j] = 0; indegree[j]= 0;

}/*for*/

for(j= 1;j<=G.n;j++) { /* 求网中各顶点的入度*/

p = G.head[j].Firstadj;

while (p) {

(1); p = p→nextarc;

}/*while*/

}/*for*/

for (j = 1; j ＜= G.n; j++) /*求网中入度为0的顶点并保存其编号*/

if (!indegree[j]) Stack[++top] =j;

while (top ＞ 0) {

w=(2);

printf("%e ", G.head[w].vdata);

p = G.head[w].Firstadj;

while (p) {

(3);

if ( !indegree [p→adjvex])

Staek[++top] = p→adjvex;

if( (4))

ve[p→adjvex] = ve[w] + p→weight;

p = p→nextarc;

}/* while */

}/* while */ return (5); }/*Toplogieal*/

阅读下列C程序和程序说明，将应填入(n)处的字句写在对应栏内。

【说明】设某城市有n个车站，并有m条公交线路连接这些车站，设这些公交车都是单向的，这n个车站被顺序编号为0至n-1。本程序，输入该城市的公交线路数、车站个数，以及各公交线路上的各站编号，求得从站0出发乘公交车至站n-1的最少换车次数。

程序利用输入信息构建一张有向图G(用邻接矩阵g表示)，有向图的顶点是车站，若有某条公交线路经i站到达j站，就在顶点i到顶点j之间设置一条权为1的有向边＜i,j＞。如果这样，从站点x至站点y的最少上车次数便对应图G中从点x到点y的最短路径长度。而程序要求的换车次数就是上车次数减1。

include ＜stdio.h＞

define M 20

define N 50

int a[N+1]； /*用于存放一条线路上的各站编号*/

int g[N][N]； /*严存储对应的邻接矩阵*/

int dist[N]； /*严存储站0到各站的最短路径*/

int m, n；

void buildG()

{ int i, j, k, sc, dd

printf(“输入公交线路数，公交站数\n”)；

scanf("%d%d"，&m，＆n)；

for (i=0；i＜n；i++) /*邻接矩阵清0*/

for(j=0；j＜n；j++)

g[i][j]=0；

for(i=0；i＜m；i++)

{ printf("沿第%d条公交线路的各站编号(0＜=编号＜=%d，-1结束)：\n)"，i+1，n-1)；

sc=0； /* 当前线路站计数器*/

while(1)

{ scanf("%d"，&dd)；

if(dd＝-1)break；

if(dd＞=0 && dd＜n) (1)；

}

a[sc]=-1；

for(k=1；a[k]＞=0；k++) /*处理第i+1条公交线路*/

for(j=0；j＜k；j++)

g (2)=1；

}

}

int minLen()

{ int j，k；

for(j=0；j＜n；j++)

dist[j]=g[0][j]；

dist[0]=1；

do{

for(k=-1，j=0；j＜n；j++) /*找下一个最少上车次数的站*/

if(dist[j]＞0 &&(k==-1｜｜dist[j]＜dist[k]))

k=j；

if(k＜0｜｜k＝=n-1)

break；

dist[k]=-dist[k]； /*设置k站已求得上车次数的标记*/

for (j=1；j＜n；j++) /*调整经过k站能到达的其余各站的上车次数*/

if((3)&& (dist[j]＝0｜｜-dist[k]+1＜dist[j]))

dist[j]=(4)；

}while(1)；

j=dist[n-1]；

return (5)；

}

void main()

{ int t；

buildG()；

if((t=minLen())＜0)

printf("无解!\n")；

else

printf(“从0号站到%d站需换车%d次\n”，n-1，t)；

}

阅读下列程序说明和C代码，将应填入(n)处的字句写在对应栏内。

【说明】

设某城市有n个车站，并有m条公交线路连接这些车站，设这些公交车都是单向的，这n个车站被顺序编号为0至n-1。输入该城市的公交线路数、车站个数，以及各公交线路上的各站编号，求得从站0出发乘公交车至站n-1的最少换车次数。

程序利用输入信息构建一张有向图G(用邻接矩阵g表示)，有向图的顶点是车站，若有某条公交线路经i站能到达j站，就在顶点i到顶点j之间设置一条权为1的有向边＜i,j＞。如是这样，从站点x至站点y的最少上车次数便对应图G中从点x至点y的最短路径长度。而程序要求的换车次数就是上车次数减1。

【函数5-9】

include ＜stdio.h＞

define M 20

define N 50

int a[N+1]; /*用于存放一条线路上的各站编号*/

iht g[N][N]; /*存储对应的邻接矩阵*/

int dist[N]; /*存储站0到各站的最短路径*/

int m,n;

void buildG()

{

int i,j,k,sc,dd;

printf ("输入公交线路数，公交站数\n");

scanf("%d%d", &m, &n);

for(i=0; i＜n; i++) /*邻接矩阵清0*/

for(j = 0; j ＜ n; j++)g[i][j] = 0;

for(i=0; i＜m; i++){

printf("沿第%d条公交车线路前进方向的各站编号(O＜=编号＜=%d,-1结束):\n",

i+1, n-1);

sc=0;/* 当前线路站计数器 */

while(1){

scanf("%d",&dd);

if(dd==-1)break;

if(dd＞=0 && dd＜n) (1);

}

a[sc]=-1;

for(k=1;a[k]＞=0; k++) /* 处理第i+1条公交线路 */

for(j=0; j＜k; j++)

g(2)=1;

}

}

int minLen()

{

int j, k;

for(j=0;j＜n;j++)dist[j]=g[0][j];

dist[0]=1;

do{

for(k=-1,j=0;j＜n;j++) /* 找下一个最少上车次数的站*/

if(dist[j]＞0&&(k==-1 || dist[j]＜dist[k]))k=j;

if (k＜0 || k==n-1) break;

dist[k]=-dist[k]; /* 设置k站已求得上车次数的标记 */

for(j=1;j＜n;j++) /* 调整经过k站能到达的其余各站的上车次数 */

if ((3) && (dist[j]==0 || -dist[k]+1＜dist[j]))

dist[j]=(4);

}while(1);

j=dist[n-1];

return (5);

}

void main()

{

int t；

buildG();

if((t=minLen()＜0)printf("无解!\n");

else pdnff("从0号站到%d站需换车%d次\n”，n-1，t)；

}

阅读下列函数说明和C函数，将应填入(n)处的字句写在对应栏内。

[说明]

Kruskal算法是一种构造图的最小生成树的方法。设G为一无向连通图，令T是由G的顶点构成的于图，Kmskal算法的基本思想是为T添加适当的边使之成为最小生成树：初始时，T中的点互相不连通；考察G的边集E中的每条边，若它的两个顶点在T中不连通，则将此边添加到T中，同时合并其两顶点所在的连通分量，如此下去，当添加了n-1条边时，T的连通分量个数为1，T便是G的一棵最小生成树。

下面的函数void Kruskal(EdgeType edges[],int n)利用Kruskal算法，构造了有n个顶点的图 edges的最小生成树。其中数组father[]用于记录T中顶点的连通性质：其初值为father[i]=-1 (i=0,1,…,n-1)，表示各个顶点在不同的连通分量上；若有father[i]=j，j＞-1，则顶点i，j连通；函数int Find(int father[],int v)用于返回顶点v所在树形连通分支的根结点。

[函数]

define MAXEDGE 1000

typedef struct

{ int v1;

int v2;

}EdgeType;

void Kruskal(EdgeType edges[],int n)

{ int father[MAXEDGE];

int i,j,vf1,vt2;

for(i=0;i＜n;i+ +) father[i]=-1;

i=0;

j=0;

while(i＜MAXEDGE && j＜(1))

{ vf1=Find(father,edges[i].v1);

vf2=Find(father,edges[i].v2);

if((2))

{(3)=vf1;

(4);

printf("%3d%3d\n",edges[i].v1,edges[i].v2);

}

(5);

}

}

int Find(int father[],int v)

{ int t;

t=v;

while(father[t]＞=0) t=father[t];

return(t);

}

阅读以下说明和代码，填补代码中的空缺，将解答填入答题纸的对应栏内。 【说明】 图是很多领域中的数据模型，遍历是图的一种基本运算。从图中某顶点v出发进行广度优先遍历的过程是： ①访问顶点v； ②访问V的所有未被访问的邻接顶点W1 ,W2 ,..,Wk； ③依次从这些邻接顶点W1 ,W2 ,..,Wk出发，访问其所有未被访问的邻接顶点；依此类推，直到图中所有访问过的顶点的邻接顶点都得到访问。 显然，上述过程可以访问到从顶点V出发且有路径可达的所有顶点。对于从v出发不可达的顶点u，可从顶点u出发再次重复以上过程,直到图中所有顶点都被访问到。 例如，对于图4-1所示的有向图G，从a出发进行广度优先遍历，访问顶点的一种顺序为a、b、c、e、f、d。设图G采用数组表示法（即用邻接矩阵arcs存储），元素arcs[i][j]定义如下：图4-1的邻接矩阵如图4-2所示，顶点a~f对应的编号依次为0~5.因此，访问顶点a的邻接顶点的顺序为b，c，e。 函数BFSTraverse(Graph G)利用队列实现图G的广度优先遍历。 相关的符号和类型定义如下： define MaxN 50 ／*图中最多顶点数*／ typedef int AdjMatrix[MaxN][MaxN]； typedef struct{ int vexnum, edgenum; ／*图中实际顶点数和边（弧）数*／ AdjMatrix arcs; ／*邻接矩阵*／ )Graph; typedef int QElemType； enum {ERROR=0;OK=1}; 代码中用到的队列运算的函数原型如表4-1所述，队列类型名为QUEUE。 表4-1 实现队列运算的函数原型及说明

【代码】 int BFSTraverse(Graph G) {//对图G进行广度优先遍历，图采用邻接矩阵存储 unsigned char*visited； //visited[]用于存储图G中各顶点的访问标志，0表示未访问 int v, w, u; QUEUEQ Q; ∥申请存储顶点访问标志的空间，成功时将所申请空间初始化为0 visited=(char*)calloc(G.vexnum, sizeof(char)); If( （1） ) retum ERROR; （2） ； //初始化Q为空队列 for( v=0; v<G.vexnum; v++){ if(!visited[v]){ //从顶点v出发进行广度优先遍历 printf("%d”，v)； //访问顶点v并将其加入队列 visited[v]=1； （3） ； while(！isEmpty(Q)){ （4） ； //出队列并用u表示出队的元素 for(w=0;v<G.vexnum; w++){ if（G.arcs[u][w]!=0&& （5） ){ //w是u的邻接顶点且未访问过 printf("%d”, w)； //访问顶点w visited[w]=1； EnQueue(&Q, w); } } } } free(visited); return OK; )//BFSTraverse