Giáo án điện tử chuyên đề Khoa học máy tính 12 kết nối Bài 13: Thực hành thiết lập đồ thị

THÂN MẾN CHÀO CÁC EM HỌC SINH ĐẾN VỚI BÀI HỌC MỚI!

TIN HỌC 12

KHỞI ĐỘNG

- Nếu đồ thị là vô hướng thì ma trận kề có đặc điểm gì?

- Phân biệt sự giống nhau và khác nhau giữa ma trận kề và danh sách kề?

- Khái niệm bậc của các đỉnh có gì khác nhau trong trường hợp đồ thị là vô hướng, có hướng?

Khái niệm bậc của các đỉnh:

Đối với đồ thị vô hướng

Bậc của đỉnh u (deg(u)) là số lượng các đỉnh kề với u.

Ta có:

- Số cạnh của đồ thị là 6.

- deg(0) + deg(1) + deg(2) + deg(3) + deg(4)

= 2 + 2 + 4 + 2 + 2 = 12 = 6 × 2.

⇒ Tổng số bậc của tất cả các đỉnh bằng hai lần số cạnh.

Đối với đồ thị có hướng

Ta có:

deg+(0) + deg+(1) + deg+(2) + deg+(3) + deg+(4)

= 1 + 3 + 1 + 2 + 0 = 7.

deg-(0) + deg-(1) + deg-(2) + deg-(3) + deg-(4)

= 3 + 0 + 1 + 1 + 2 = 7.

⇒ Tổng số bậc ra của tất cả các đỉnh bằng tổng số bậc vào của tất cả các đỉnh.

• Bậc ra của đỉnh u (deg+(u)) là số lượng các đỉnh kề với u.

• Bậc vào của đỉnh u (deg-(u)) là số các đỉnh có cạnh nối đến u.

CHUYÊN ĐỀ 3: TÌM HIỂU KĨ THUẬT DUYỆT ĐỒ THỊ VÀ ỨNG DỤNG

BÀI 13: THỰC HÀNH THIẾT LẬP ĐỒ THỊ

Nhiệm vụ 1. Viết chương trình hiển thị danh sách kề

Đơn đồ thị vô hướng G = (V,E) được cho bởi ma trận kề A. Ma trận A được cho trong tệp văn bản có dạng như hình dưới. Và xác định danh sách kề của nó.

Hướng dẫn:

+ Tạo tệp Data.inp.

+ Thiết lập hàm BuildGraph(fname) lấy dữ liệu từ tệp ma trận kề và trả về cặp dữ liệu V, A là danh sách đỉnh và ma trận kề của đồ thị.

+ Hãy viết hàm thể hiện danh sách kề trên màn hình theo đúng yêu cầu trên với tham số đầu vào là ma trận kề A.

Hình 13.1. Tệp ma trận kề

Hàm hiển thị danh sách kề

• Chương trình đầy đủ:
• Kết quả thể hiện ra màn hình:

Nhiệm vụ 2. Viết chương trình hiển thị ma trận kề, danh sách kề và bậc của đồ thị

Đơn đồ thị vô hướng G = (V,E) được cho bởi danh sách các cạnh. Danh sách các cạnh được cho trong tệp văn bản, trong đó dòng đầu tiên là số các đỉnh của đồ thị, các dòng tiếp theo mỗi dòng mô tả một cạnh của đồ thị. Hãy tính ma trận kề, danh sách kề và bậc của tất cả các đỉnh của đồ thị G.

Hình 13.2. Tệp danh sách các cạnh

• Hàm AdjacencyMatrix(Adj):
• Hàm show(A,op):
• Hàm show_deg(Adj):
• Phần chương trình chính:

• Chương trình đầy đủ:

• Kết quả thể hiện ra màn hình:

LUYỆN TẬP

Câu 1. Trong Nhiệm vụ 1, hàm In_danh_sach_dinh_ke() lấy thông tin từ ma trận kề A. Có thể sử dụng hàm này với dữ liệu là danh sách kề Adj được không? Nếu có thì viết lại hàm này với dữ liệu đầu vào là danh sách kề Adj.

Có thể sử dụng hàm In_danh_sach_dinh_ke()với dữ liệu là danh sách kề Adj:

Câu 2. Trong Nhiệm vụ 2, chúng ta có thể thấy các đỉnh kề không được in ra theo thứ tự tăng dần của chỉ số trong biểu diễn danh sách kề. Em hãy giải thích tại sao. Có thể chỉnh sửa chương trình để in ra các đỉnh kề theo thứ tự chỉ số tăng dần được không?

Muốn in ra danh sách các đỉnh kề theo thứ tự tăng dần của số thứ tự các đỉnh của đồ thị, cần thực hiện việc sắp xếp từng phần tử của Adj ngay từ khi nhập dữ liệu gốc.

VẬN DỤNG

--------------- Còn tiếp ---------------