Giáo án điện tử chuyên đề Khoa học máy tính 12 cánh diều Bài 3: Thực hành các thao tác cơ bản với đồ thị trên máy tính

CHÀO CẢ LỚP! CHÀO MỪNG

CÁC EM TỚI BUỔI HỌC NÀY!

KHỞI ĐỘNG

Em hãy dùng ma trận kề và danh sách kề biểu diễn đồ thị sau:

KHỞI ĐỘNG

Ma trận kề:

Danh sách kề:

BÀI 3: THỰC HÀNH

CÁC THAO TÁC CƠ BẢN

VỚI ĐỒ THỊ TRÊN MÁY TÍNH

NỘI DUNG BÀI HỌC

Thực hành: Bài toán Giao hữu bóng đá

Luyện tập

Vận dụng

THỰC HÀNH: BÀI TOÁN GIAO HỮU BÓNG ĐÁ

Có 6 đội bóng (các đội được đánh số từ 0 đến 5) tham gia đá giao hữu, theo thể thức mỗi cặp đội thi đấu với nhau không quá một trận và với mỗi trận sẽ luôn phân định thắng thua, không có hòa. Hình 1 là một đồ thị biểu diễn thông tin các trận đấu đã diễn ra tính đến thời điểm hiện tại, trong đó mỗi đội tương ứng với một đỉnh của đồ thị, nếu có một cạnh nối từ đỉnh i tới đỉnh j thì cho biết hai đội i, j đã đấu với nhau và đội i giành chiến thắng (0 ≤ i, j ≤ 5).

a) Em hãy cho biết đến thời điểm hiện tại có bao nhiêu trận đấu đã diễn ra; liệt kê tất cả các trận, mỗi trận được mô tả bằng cặp số i, j có ý nghĩa là đội i đấu với đội j và đội i giành chiến thắng.

Hình 1. Đồ thị biểu diễn thông tin các trận đấu đã diễn ra ở thời điểm hiện tại

b) Xây dựng ma trận kề biểu diễn đồ thị.

c) Xây dựng danh sách kề biểu diễn đồ thị.

d) Em hãy cho biết đội số 2 đã thi đấu bao nhiêu trận, trong đó có bao nhiêu trận thắng, bao nhiêu trận thua.

a) Xét lần lượt từng đội, với mỗi đội i (0 ≤ i ≤ 5) liệt kê các trận thắng của đội đó.

b) Coi mỗi đội là một đỉnh của đồ thị, mỗi trận đấu là một cạnh của đồ thị. Xây dựng ma trận gồm 6 hàng và 6 cột (các hàng đánh số từ 0 đến 5 và từ trên xuống dưới; các cột đánh số từ 0 đến 5 và từ trái sang phải). Điền lần lượt cho từng hàng; Nếu đội i thắng đội j thì trên hàng i, cột j ghi số 1; ngược lại ghi số 0.

Hướng dẫn

c) Dựa vào ma trận đã xây dựng ở yêu cầu b) để liệt kê các đỉnh kề của mỗi đỉnh.

d) Số trận thắng của đội i (0 ≤ i ≤ 5) là số các số 1 trên hàng i của ma trận đã xây dựng ở yêu cầu b), còn số trận thua của đội i (0 ≤ i ≤ 5) là số các số 1 trên cột i của ma trận.

Hướng dẫn

d) Đội số 2 đã thi đấu 3 trận, trong đó có 2 trận thắng và 1 trận thua.

b) Ma trận kề biểu diễn đồ thị:

c) Danh sách kề biểu diễn đồ thị:

a) Đến thời điểm hiện tại có 8 trận đấu đã diễn ra (chính là số cạnh của đồ thị): (0, 1), (0, 2), (0, 5), (2, 1), (2, 3), (3, 4), (3, 5), (4, 5).

--------------------------------------

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