Question

数学 大二离散数学题目 求解答

1，设V＝｛a,v,c,d｝能与V构成强连通图的边集 E=( )
A:{<a,b>,<a,c>,<b,d>,<c,d>,<d,a>}
B:{<a,d>,<b,a>,<b,c>,<b,d>,<d,c>}
C:{<a,c>,<b,a>,<b,c>,<d,a>,<d,c>}
D:{<a,d>,<b,a>,<b,d>,<c,d>,<d,c>}
2,下列不能构成简单连通无向图的度数列是
A.1,2,2,3
B.2,2,2,2,2
C.1,2,3,4,4,5
D.2,3,3,3,3
3.图G有18条边，3个四度结点，其余均为3度结点，则G有几个结点？

Answer 1

答：（1）选D
(2) 选C
(3) 设G有n各结点，则由握手定理3*4+(n-3)*3=2*18
解得n=11
另外，N阶有向完全图Kn中的边数为n（n-1）/2.

Answer 2

3根据握手定理：顶点度数之和是边数的两倍
设3度结点x个
18*2=3*4+x*3解出
x=8

追问

N阶有向完全图Kn中的边数有多少个呢

追答

任意两顶点之间都有两条边，所以共有C(2,n)*2=n(n-1)条边

Answer 3

1,D
2,C