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 Pru¨fer 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

MSSV: . . . . . . . . . . . . . . . . . . . . .

Họ tên SV: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Số thứ tự

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

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.

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

c

e

f

b

d

A

B

C

D

E

F

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

1

E

F

G

H

1

4

2

6

1

8

6

A

B

C

D

1

2

1

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?

4

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

G

D

A

H

I

E

F

C

B

7. (a) Xác định Pru¨fer code của cây sau:

2

3

1

0

4

5

(b) Xây dựng cây với Pru¨fer code là (0, 0, 0, 4, 2, 0, 1, 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

Công ty

A D E C

D B A C

Công ty

Sinh viên

a b d

b d a

a

b

c

d

e

B

A

B

C

D

E

e

c

e

a

b

a

E

B

E

C

D A

B

b c

d

e

c

A D C

E

a

d

e d

b e

B

D A E C

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?

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

d

1

3

2

10

3

s

t

b

c

1

4

5

e

10. Cho một tập các biến x₁, x₂, ... , x_n, và một tập các ràng buộc bằng nhau x_i= x_jhoặc khác

nhau x_i= 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₁= x₂, x₂= x₃, x₃= x₄, x₁= x₄là không thể thỏa mãn.