设图G_i=<V,E>（i=1，2，…，6)，其中画出各图，试问：（1)哪些图是有向图？哪些图是无向图？（2)哪些

设f₁(x)，...，f_m(x)，g₁(x)，...，g_n(x)都是多项式，而且(f_i(x)，g_i(x))=1(i=1，2，...，m;j=1，2，...，n)。求证：(f₁(x)f₂(x)...f_m(x)，g₁(x)g₂(x)...，g_n(x))=1。

问题描述:给定有向图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行开始,每行输出一条路径.文件的最后一行是最少路径数.

设α₁，α₂，...，α_n是欧氏空间V的一组基，证明：

1)如果γ∈V使(γ，α_i)=0，i=1，2，...，n，那么γ=0;

2)如果γ₁-γ₂∈V使对任一α∈V有(γ₁，α)=(γ₂，α)，那么γ₁=γ₂。

已知一个图的顶点集V和边集E分别为：

V={1,2,3,4,5,6,7};

E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};

按照普里姆算法从顶点1出发得到最小生成树，试写出在最小生成树中依次得到的各条边。

A.1

B.2

C.3

D.4

A.1

B.2

C.3

D.4

问题描述:给定一个无向图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中.

设K的全部极点为x⁽¹⁾，x⁽²⁾，…，x^(u)，K的全部极射向为y⁽¹⁾，y⁽²⁾，…，y^(v)，则x∈K当且仅当存在α_i≥0(i=1．2，…，u)且和β_i≥0(i=1，2，…，v)，使得

(8.7)

设{α₁，α₂，···，α_n}和{β₁，β₂，···，β_n}是n维欧氏空间V的两个规范正交基。

(i)证明：存在V的一个正交变换σ，使σ(α_i)=β_i，i=1，2，...，n;

(ii)如果V的一个正交变换τ使得τ(α₁)=β₁，那么τ(α₂)，···，τ(α_n)所生成的子空间与由β₂，···，β_n所生成的子空间重合。