设有向图G有16条边，则所有顶点的出度之和为 。
下列有向图中是强连通图的是
A． B． C． D．
4个顶的不同竞赛图共有 A．6个 B．16个 C．32个 D．64个
把单星妖怪定向成强连通有向图。
若一个有向图G是单向连通的，则它必是弱连通图的。 若一个有向图G是单向连通的，则它必是强连通图的。 每个竞赛图都有有向Hamilton轨。
竞赛图G中v为惟一王的充要条件是v得分为|V(G)?1|。 强连通竞赛图是有向Hamilton图。
有向Hamilton图是强连通图。
若有向图的底图为G，则此有向图中有长?(G)的轨。
在任何有向图中，所有顶点的入度之和等于所有顶点的出度之和。 若竞赛图不是有向Hamilton图，则它有惟一的王。 作一个5个顶的竞赛图，使它的王不惟一。
写出下面竞赛图中的王： 。v1,v2,v3,v5
v1 v5v2 v3v4
求下图中的最大流，其中s是源，t是汇，并指出此网络的一个最小截。（括弧旁第一个数字
表示容量，第二个数字表示当前弧中的流量） v1v3(6,3) (5,3)(7,4) (4,1)st(6,1)
(8,5)(3,1)(8,4)
v2(7,6)v4
求下图中的最大流，其中s是源，t是汇，并指出此网络的一个最小截。（括弧旁第一个数字表示容量，第二个数字表示当前弧中的流量）
v1v3(4,3)
(5,3)(3,3)
(1,1)st(3,0) (1,1) (5,1)(2,1) v2(2,2)v4
在如下网络N中，每条弧旁边的数对(x,y)分别表示该弧的容量为x、一个可行流f在相应弧的流量为y。（1）写出该网络中一条从源s到汇t的可改进流量最大的路P；（2）基于P，构造流f的修改流；（3）继续修改，求出从s到t的最大流。
v1v2(1,1) (7,6)(4,3)(3,2)(4,3) (3,2)t(2,2)sv3(5,3)
(3,2)(8,3)(10,4)
(4,2)v4v5
求下图中从s到t的最大流。
v1(1,1)v2 (4,3)(3,2)(7,6)(4,3)
sv3(2,2)t(3,2)
(5,3)(10,4)(8,3) (3,2)v1(1,1)v2
v4(4,2)v5 (4,4)(3,3)(7,7)(4,4)
sv3(2,2)t
(3,3) (5,5)(10,7)(8,7) (3,3)
v4(4,4)v5
v4v1v635
求下图中从s到t的最大流。
72698 2
4sv2v7t4v31531537v84v5
v1(9,2)s(4,4)(1,0)(3,0)(7,2)(6,2)v2v4(5,0)(2,2)v7(5,4)v6(8,2)t(7,4)v8(4,4)(2,2)(4,0)(1,0)(3,0)v3(5,4)v5(3,0)
存在割顶的连通图其顶连通度必为
1。
有桥的连通图其边连通度必为1。
下图的点连通度等于 ，边连通度等于_________。
?(Kn)=
A．n
B．n?1
C．2
D．1
?'(Kn)=
A．n B．n?1 C．2 D．1
图G如右，ef边不是图G的桥是因为 A．e的次数是3 baB．ef边平行于cd边
gefC．G是3次正则图
dcD．G??ef是连通图
下图中的顶连通度为 。下图中的边连通度为 。 3 3
相关推荐：
loading