BÀi tập và thực hành môn học lý thuyết đồ thị



tải về 257.57 Kb.
trang1/5
Chuyển đổi dữ liệu09.09.2017
Kích257.57 Kb.
  1   2   3   4   5
BÀI TẬP VÀ THỰC HÀNH

MÔN HỌC

Lý thuyết đồ thị

MỤC LỤC

CHƯƠNG 1: ĐẠI CƯƠNG VỀ ĐỒ THỊ 3

1Xét ví dụ thực tế 3

2Các thuật ngữ đồ thị 4

3Biểu diễn các đồ thị và sự đẳng cấu đồ thị 5

4Tính liên thông 6

CHƯƠNG 2: ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON 10

CHƯƠNG 3
ĐỒ THỊ CÓ TRỌNG SỐ VÀ ĐƯỜNG ĐI NGẮN NHẤT 14


15

CHƯƠNG 4: CÂY 20

Viết tiểu luận 28

ĐỀ TÀI 1: 28

SỬ DỤNG PHƯƠNG PHÁP ĐỒ THỊ ĐỂ THỂ HIỆN VIỆC BỐ TRÍ LỊCH THI CHO SINH VIÊN KHOA TOÁN – TIN HỌC. 28

ĐỀ TÀI 2: 28

SỬ DỤNG PHƯƠNG PHÁP ĐỒ THỊ ĐỂ GIẢI BÀI TOÁN DÂN GIAN (BÀI TOÁN 1). 28

ĐỀ TÀI 3: 29

SỬ DỤNG PHƯƠNG PHÁP ĐỒ THỊ ĐỂ GIẢI BÀI TOÁN DÂN GIAN (BÀI TOÁN 2). 29

ĐỀ TÀI 4: 30

CÁC THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN ĐỒ THỊ 30

ĐỀ TÀI 5: CÁC GIẢI THUẬT TÌM CÂY PHỦ TỐI TIỂU 30

ĐỀ TÀI 6: BÀI TOÁN TỔ CHỨC THI CÔNG 31

ĐỀ TÀI 7: BÀI TOÁN QUẢN LÝ DỰ ÁN 32

ĐỀ TÀI 8: BÀI TOÁN “8 QUÂN HẬU” 32

ĐỀ TÀI 9: BÀI TOÁN “QUÂN MÃ ĐI TUẦN” 33

ĐỀ TÀI 10: 34

BÀI TOÁN PHÂN BỐ KÊNH TRUYỀN HÌNH TẠI ĐBSCL 34

DÙNG THUẬT TOÁN TÔ MÀU ĐỒ THỊ 34

ĐỀ TÀI 11: 34

BÀI TOÁN PHÂN BỐ KÊNH TRUYỀN HÌNH TẠI MIỀN ĐÔNG NAM BỘ 34

DÙNG THUẬT TOÁN TÔ MÀU ĐỒ THỊ 34

ĐỀ TÀI 12: 35

XÂY DỰNG BẢN ĐỒ TRỰC TUYẾN NHỮNG CON ĐƯỜNG LỚN TRONG NỘI THÀNH TP.HỒ CHÍ MINH VỚI VIỆC TÍNH CHI PHÍ THẤP NHẤT ĐỂ DI CHUYỂN GIỮA TRUNG TÂM CÁC QUẬN. 35

ĐỀ TÀI 13: 35

XÂY DỰNG HỆ THỐNG KẾT NỐI MẠNG CỦA CÁC TRƯỜNG ĐẠI HỌC TRONG THÀNH PHỐ VỚI CHI PHÍ THẤP NHẤT 35

ĐỀ TÀI 14: BÀI TOÁN ĐƯỜNG ĐI NGƯỜI GIAO HÀNG 36

ĐỀ TÀI 15: BÀI TOÁN ĐƯỜNG ĐI NGƯỜI ĐƯA THƯ 36

CHƯƠNG 1: ĐẠI CƯƠNG VỀ ĐỒ THỊ

1Xét ví dụ thực tế


Bài 1.1. Với mỗi trường hợp sau, vẽ các mô hình đồ thị biểu diễn các đường bay và nói rõ về loại đồ thị được dùng. Trong đó lịch bay mỗi ngày như sau:

- Từ TP.HCM: có một chuyến đến Hà Nội, một chuyến đến Đà Nẵng, một chuyến đến Phú Quốc, một chuyến đến Nghệ An, một chuyến đến Hải Phòng;

- Từ Hà Nội: có hai chuyến đến TP.HCM, một chuyến đến Đà Nẵng, một chuyến đến Nghệ An, một chuyến đến Hải Phòng;

- Từ Đà Nẵng: có một chuyến đến Hải Phòng, hai chuyến bay đến TP.HCM; một chuyến đến Hà Nội;

- Từ Nghệ An: có một chuyến đến Hà Nội, một chuyến đến TP.HCM;

- Từ Hải Phòng: có một chuyến đến Hà Nội, một chuyến đến TP.HCM, và một chuyến đến Đà Nẵng;

- Từ Phú Quốc: có một chuyến đến TP.HCM.

a) Đồ thị biểu diễn các thành phố có chuyến bay giữa chúng.

b) Đồ thị biểu diễn số chuyến bay hoạt động giữa các thành phố, cộng với một khuyên biểu thị chuyến du lịch đặc biệt ngắm cảnh thành phố, cất và hạ cánh tại Phú Quốc.

c) Đồ thị biểu diễn đầy đủ thông tin về hướng bay và số chuyến bay giữa các thành phố.



Phần hướng dẫn

a) Đồ thị vô hướng



b) Đa đồ thị vô hướng



c) Đa đồ thị có hướng





Bài 1.2. Xác định xem đồ thị nào sau đây là đồ thị đơn, đa đồ thị, đồ thị có hướng.




Bài 1.3. Trong trận đấu vòng tròn, đội H thắng đội G, đội C, và đội A; đội G thắng đội A và đội C; đội C thắng đội A. Hãy mô hình hóa kết quả này bằng một đồ thị có hướng…

2Các thuật ngữ đồ thị


Bài 2.1. Xác định số lượng các đỉnh, số lượng các cạnh, và bậc của các đỉnh trong các đồ thị sau. Cho biết đỉnh nào là đỉnh cô lập, đỉnh nào là đỉnh treo.





Bài 2.2. Tìm tổng các bậc của các đỉnh trong các đồ thị ở các Bài 2.1, và kiểm chứng rằng nó bằng hai lần số các cạnh trong đồ thị.

Bài 2.3. Có thể tồn tại một đồ thị đơn có 15 đỉnh, mỗi đỉnh có bậc bằng 5 không? Tại sao?

Bài 2.4. Trong một buổi chiêu đãi, mọi người đều bắt tay nhau. Chứng tỏ rằng tổng số người được bắt tay là một số chẵn. Giả sử không ai tự bắt tay mình.

Bài 2.5. Xác định số đỉnh, số cạnh, số bậc vào và số bậc ra của mỗi đỉnh đối với đồ thị có hướng sau.

Bài 2.6. Hãy xác định tổng các bậc vào và tổng các bậc ra các đỉnh của đồ thị trong bài 2.5 một cách trực tiếp. Chứng tỏ rằng chúng đều bằng tổng các cạnh của đồ thị.

Bài 2.7. Đồ thị sẽ có bao nhiêu cạnh nếu nó có các đỉnh bậc 4, 3, 3, 2, 2. Vẽ một đồ thị như vậy.

Bài 2.8. Có tồn tại đồ thị đơn chứa năm đỉnh với các bậc sau đây? Nếu có hãy vẽ đồ thị đó.

a) 3, 3, 3, 3, 2. b) 1, 2, 3, 4, 5.

c) 1, 2, 3, 4, 4.

Bài 2.9. Vẽ tất cả các đồ thị con của đồ thị sau.

Bài 2.10. Tìm hợp của các cặp đồ thị đơn sau

3Biểu diễn các đồ thị và sự đẳng cấu đồ thị


Bài 3.1. Dùng danh sách kề biểu diễn các đồ thị sau.



Bài 3.2. Biểu diễn các đồ thị trong bài 3.1 bằng ma trận kề.

Bài 3.3. Vẽ các đồ thị ứng với ma trận kề được cho như sau.

a) b) c)



Bài 3.4. Dùng ma trận liên kết để biểu diễn các đồ thị trong Bài 3.1.

Bài 3.5. Xác định xem các cặp đồ thị đã cho có là đẳng cấu không.







  1   2   3   4   5


Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2019
được sử dụng cho việc quản lý

    Quê hương