组合数学答案9-14
- 格式：pdf
- 大小：857.57 KB
- 文档页数：15
6) The vertex x3 are labeled (*).
7) Scan the vertex x3, and label y5 with (x3).
8) Scan the vertex y5, and find that no new labels are possible. So, we get a breakthrough. We find the M2-augmenting path r2=y5x3 using the labels as a guide. Then m3 = {(x3,y5),(x1,y1),(x2,y2),(x4,y4)} is a matching of four edges.
we assume that the black square is located in ith row and jth column. Then the first block must a black one, so i and j are all odd or even. We can divide chessboard into 5 parts: A1(the distribution of i*(j-1)), A2(the distribution of (m-i)*j), A3(the distribution of (i-1)*(n-j+1)), A4(the distribution of (m-i+1)*(n-j)) and the black square. We can get i and j have all odd or even, it always has even edges, so it has a perfect cover.
15 0
1 1
15=15*1+0 d=1
Since the GCD is 1 we conclude that 15 has a multiplicative inverse in Z46. The resulting equations yield: 1=46-3*15 Thus, we get the multiplicative inverse of 15 in Z46: 15-1=-3=43 21.Determine the complementary design of the BIBD with parameters b=v=7, k=r=3, =1 in Section 10.2 Solution: Parameters of the BIBD: 1) b: the number of blocks; 2) v: the number of varieties; 3) k: the number of varieties in each block; 4) r: the number of blocks containing each variety 5) : the number of blocks containing each pair of varieties. Here, we get that b=v=7, k=r=3, =1:
1) r= 2) 3) 4) 5)
6)
. Thus, we can design
such a complementary. b’ = b =7 v’ = v =7 k’ = v-k = 4 r’ = b-r = 4 = b-2r + = 7-2 3+1 = 2
28. Show that B = {0, 1, 3, 9} is a difference set in Z13 , and use this difference set as a starter block to construct an SBIBD. Identify the parameters of the block design. Solution: We find that non-zero integers in Z13 occur exactly once as a difference, hence B = {0, 1, 3, 9} is a difference set in Z13. 0 1 3 9
5) A->b; b rejects B. 6) B->c; c rejects C. 7) C->a; a rejects D. 8) D->b; b rejects A. 9) A->c; c rejects B. 10) B->d; there are no rejections. Hence, (A,c), (B,d),(C,a),(D,b).
组合数学第 9 次作业（第十章，第三版）
16. Apply the algorithm for the GCD in Section 10.1 to 15 and 46, and then use the results to determine the multiplicative inverse of 15 in Z46. Solution: A B 15 46 46=3*15+1
Solution:
①Determine the max-matching and the min-cover of the right graph by applying
the matching algorithm. We choose the red edges and obtain a matching M1. First, we get that M1 = {(x2,y1),(x4,y4)} of size 2 and U={x1,x3} 1) The vertices x1,x3 are labeled (*).
We get a max-matching M={(x3,y5),(x1,y1),(x2,y2),(x4,y4)}, but we can found the vertex y3 is still uncovered. And we should construct a subgraph composed of edges incident to the vertex y3, Then we find the max-matching of the subgraph, and add it to the max-matching of M, then we get a minimum edge cover. The max-matching of the subgraph is {(x1,y3)}, so we get the minimum cover: minimum cover={(x1,y3)}M={(x1,y3),(x3,y5),(x1,y1),(x2,y2),(x4,s x2 and x4, and label y2 with (x2).
5) Scan the vertices y2, and find that no new labels are possible. So, we get a breakthrough. We find the M1-augmenting path r1=y2x2y1x1 using the labels as a guide. Then M2 = {(x1,y1),(x2,y2),(x4,y4)} and U2={x3}.
13. Let A={A1,A2,A3,A4,A5,A6} where A1={1,2} A2={2,3} A3={3,4} A4={4,5} A5={5,6} A6={6,1} Determine the number of different SDR’s that A has. Generalize to n sets. Solutions: A has 2 different SDR’s. Suppose that we choose 1 in from A1, and choose 3 from A2, then we can just choose 4 from A3, choose 5 from A4, choose 6 from A5, and choose 1 from A1, but it contract with the 1 from A1. So, we only have two different SDR’s. ① Choose 1 from A1, choose 2 from A2,…,choose 6 from A6. So, SDR1={1,2,3,4,5,6}. ② Choose 2 from A1, Choose 3 from A2,…, choose 1 from A6. So, SDR2={2,3,4,5,6,1}. Generalize to n sets, there are only two SDR’s in n-sets the same: SDR1={1,2,3,4,…,n} SDR2={2,3,4,…,n,1} 26. Apply the deferred acceptance algorithm to obtain a stable complete marriage for the preferential ranking matrix. a b c d A B C D Solutions: We apply the deferred acceptance to the preferential ranking matrix, the result of the algorithm are (here we use women–optimal ): 1) A->a, B->a, C->b, D->c; a rejects B. 2) B->b; b rejects C. 3) C->c; c rejects D. 4) D->a; a rejects A.
Here, we get that the max-matching M = {(x3,y5),(x1,y1),(x2,y2),(x4,y4)}, and the min-cover = {y1,y2,y3,y4,y5}.
