Giải chuyên đề Tin 12 KNTT Bài 12: Biểu diễn đồ thị có đáp án

Quan sát đồ thị Hình 12.1 và cho biết mỗi tệp dữ liệu sau  có ý nghĩa gì?

Tìm hiểu, thảo luận về các cách biểu diễn dữ liệu của một đồ thị G.

Vẽ đồ thị có tệp dữ liệu ma trận kề Hình 12.5

Có thể có hai tệp dữ liệu dạng danh sách kề nhau nhưng biểu diễn hai đồ thị hoàn toàn giống nhau không?

Tìm hiểu, thảo luận cách thiết lập đồ thị (dữ liệu của đồ thị) trong trường hợp tập dữ liệu biểu diễn là ma trận kề hoặc danh sách kề.

Khẳng định dãy Adj[i] có số lượng phần tử bằng số các phần tử có giá trị 1 của hàng thứ i của ma trận kề A là đúng hay sai?

Khi nào ma trận kề A chỉ gồm toàn số 0?

Tìm hiểu, thảo luận cách thiết lập dữ liệu của đồ thị trong trường hợp tệp dữ liệu biểu diễn danh sách các cạnh.

Một đơn đồ thị, vô hướng có n đỉnh, có thể có số cạnh lớn nhất là bao nhiêu?

Khi nào thì tất cả các phần tử của Adj đều rỗng?

Bổ sung thêm đoạn chương trình kiểm tra khi đọc dữ liệu danh sách các cạnh đồ thị của Hoạt động 3 như sau: Với mỗi dòng dữ liệu, nếu hai chỉ số i = j thì bỏ qua dòng này.

Từ ma trận kề A của đồ thị G có thể tính được số các cạnh của đồ thị không? Nếu được thì tính bằng cách nào?

Cho ma trận kề A của đồ thị vô hướng G. Viết hàm GraphEdge(A) trả lại danh sách E các cạnh của đồ thị G.

Cho danh sách kề Adj của đồ thị G. Viết hàm GraphEdge(Adj) trả lại danh sách E các cạnh của đồ thị G. Viết chương trình cho hai trường hợp riêng biệt, G là đồ thị vô hướng và G là đồ thị có hướng.