Đề giữa kỳ TRR 2019 [PDF]

Zitiervorschau

Cấu trúc đề thi giữa kỳ môn Toán Rời Rạc Mỗi bài 01 điểm. Làm bài luôn vào đề. Yêu cầu: Viết sáng sủa và ngắn gọn; Không nháp vào bài thi. Bài 1. Chứng minh một số tính chất đơn giản về đồ thị và cây. Bài 2. Tìm cặp ghép hoặc tìm đường đi (chu trình) Hamilton. Bài 3. Thuật toán Dijkstra hoặc Prim. Bài 4. Thuật toán Kruskal hoặc cấu trúc dữ liệu Disjoint Set. Bài 5. Tô màu đồ thị. Bài 6. Tìm thành phần liên thông mạnh. Bài 7. Tính toán Pr¨ ufer code của cây. Bài 8. Bài toán Hôn nhân bền vững. Bài 9. Luồng cực đại và lát cắt cực tiểu. Bài 10. Bài tập sáng tạo.

1

2

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI Họ và tên:...................................................... MSSV:.................. VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG Họ tên SV: . . MAI . . . . . .TRƯỜNG . . . . . . . . . . . .SƠN .................

MSSV: . . . . . .20183620 ...............

Học phần: Toán Rời Rạc . . . . . . . . . . . . . . . . . . . . . . . .

Mã HP: . . . . . . . . . . . . . . . . . . . .

Số thứ tự

Bài thi [ ] giữa kỳ [X] cuối kỳ . . . . . . . . . . . . Ngày thi: . . . . . . . . . . . . . . . . . Điểm của bài thi

Chữ ký của (các) cán bộ chấm thi

Chữ ký của cán bộ coi thi

Đề mẫu thi giữa kỳ môn Toán Rời Rạc Thời gian 90 phút. Không sử dụng tài liệu. 1. Một cây có 2n đỉnh bậc 1, 3n đỉnh bậc 2, n đỉnh bậc 3 và không có đỉnh bậc khác. Hãy xác định xem n bằng bao nhiêu, từ đó tìm số đỉnh và số cạnh trong cây. |V| = 2n + 3n + n = 6n |E| = 1/2 * (2n + 2*3n + 3*n) = 11n/2 |V| - 1 = |E| -> 6n - 1 = 11n/2 -> n = 2 |V| = 12, |E| = 11.

2. Liệu ta có thể ghép cặp đầy đủ cho đồ thị hai phần dưới đây không? Nếu có tô đậm một ghép cặp như vậy. Nếu không hãy chứng minh. a

b

c

d

e

f

A

B

C

D

E

F

Không do tồn tại tắc nghẽn: tập {a, c, e, f} và tập {A, B, D}.

3

3. Hãy dùng thuật toán Dijkstra để xây dựng cây mô tả đường đi ngắn nhất từ đỉnh A tới tất cả các đỉnh khác của đồ thị sau: 5

E

4

A

1

F

6

8

1

Thời gian 0 1 3 4 5 6

A B 0 1 1

0

C

2

1

C 3 3

3

D

H 1

2

6

B

1

G

1

D

1

F 8 7 7 7 6 6

G

H

4 4

E 4 4 4 4

7 5 5 5

5 5

4

4

6

5

5

4. Hãy dùng thuật toán Kruskal để tìm cây bao trùm nhỏ nhất cho đồ thị trong Bài tập 3.

5. Xét đồ thị G thu được từ đồ thị trong Bài 3 sau khi bỏ đi trọng số trên cạnh. Hãy tìm cách tô màu đồ thị này dùng ít màu nhất có thể. Tại sao số màu bạn dùng lại là ít nhất?

Đỉnh A, G: màu 1 Đỉnh B, D, E: màu 2 Đỉnh C, F, H: màu 3 3 màu là ít nhất do đồ thị G chứa đồ thị đầy đủ K(3)

4

6. Hãy tìm các thành phần liên thông mạnh của đồ thị sau.

7.

G

H

I

D

E

F

A

B

C

(a) Xác định Pr¨ ufer code của cây sau: 0 1 1 2 3

2

0

1 4

5

(b) Xây dựng cây với Pr¨ ufer code là (0, 0, 0, 4, 2, 0, 1, 0).

3 5 6 7 4 2 8 1 9 0 0 0 4 2 0 1 0 0

8. Có năm sinh viên a, b, c, d, e muốn thực tập tại năm công ty A, B, C, D, E. Sau đây là danh sách xếp hạng mức độ ưa thích của các sinh viên và của các công ty (trái nhất là thích nhất): Sinh viên a b c d e

Công ty B A D E D B A C B E C D A D C B B D A E

C E A E C

Công ty Sinh viên A e a b d B c b d a C b c d e D a e d c E d b e c

c e a b a

Hãy dùng thuật toán kén chồng để tìm một cặp ghép ổn định. Cặp ghép ổn định này có phải là duy nhất không? Tại sao?

a b c d e

D C B E A

A B C D E

a c b e d

,

5

9. Hãy tìm luồng cực đại và lát cắt cực tiểu của mạng sau đây. 2

a 3

s

1

10 3

d 2

b

t

1

1

4

5

c

5

e

10. Cho một tập các biến x 1 , x 2 , . . . , x n , và một tập các ràng buộc bằng nhau x i = x j hoặc khác nhau x i 6= x j . Bạn hãy thiết kế thuật toán kiểm tra liệu các biến có thể thỏa mãn mọi ràng buộc. Ví dụ, các ràng buộc x 1 = x 2 , x 2 = x 3 , x 3 = x 4 , x 1 6= x 4 là không thể thỏa mãn.