设V1为无向连通图G的点割集，记G删除V1的连通分支个数为p（G- V1) = k，下列命题中一定为真的为A．k≥

设V'和E'分别为无向连通图G的点割集和边割集，下面的说法中正确的是()。

Ⅰ．G-E'的连通分支数p(G-E')=2

Ⅱ．G-V'的连通分支数p(G-V')一定等于G-E'的连通分支数p(G-E')

Ⅲ．G-V'的连通分支数p(G-V')≥2

A．Ⅰ和Ⅱ

B．Ⅰ和Ⅲ

C．Ⅱ

D．没有

设V'和E'分别为无向连通图G的点割集和边割集，下面的说法中正确的是

Ⅰ．G-E'的连通分支数p(G-E')=2。

Ⅱ．G-V'的连通分支数p(G-V')一定等于G-E'的连通分支数p(G-E')。

Ⅲ．G-V'的连通分支数p(G-V')≥2。

A．Ⅰ和Ⅱ

B．Ⅰ和Ⅲ

C．Ⅱ

D．没有

A.设 f 任意流, (A, B) 是任意s-t 割, 则流值不小于割的容量。

B.给定连通图G, BFS遍历得到层次图，如果同一层中的结点无边相连，则G是二分图。

C.设G是n阶无孤立点的图，则V*是G的顶点覆盖，当且仅当V-V*是G的独立集。

D.给定G = ＜V, E＞, G的匹配中任何两条边都没有公共顶点。

A.设 f 任意流, (A, B) 是任意s-t 割, 则流值不小于割的容量。

B.给定连通图G, BFS遍历得到层次图，如果同一层中的结点无边相连，则G是二分图。

C.设G是n阶无孤立点的图，则V*是G的顶点覆盖，当且仅当V-V*是G的独立集。

D.给定G = ＜V, E＞, G的匹配中任何两条边都没有公共顶点。

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