Trong lý thuyết đồ thị toán rời rạc, ma trận kề (adjacency matrix) chơi một vai trò quan trọng trong việc mô phỏng các thuật toán đồ thị, như thuật toán tìm đường đi ngắn nhất và thuật toán tìm cây bao trùm tối thiểu. Bài viết này sẽ giới thiệu về lý thuyết và cách biểu diễn đồ thị bằng ma trận kề thông qua các bài tập có lời giải. Bắt đầu thôi!
Contents
I. Ma trận kề là gì?
Ma trận kề là cách biểu diễn đồ thị G = {V,E} dưới dạng ma trận boolean có kích thước bằng số đỉnh của đồ thị.
Bạn đang xem: Ma trận kề – Biểu diễn đồ thị, danh sách kề và bài tập
Ví dụ ma trận kề:
II. Tính chất của ma trận kề
Tính chất của ma trận kề của đồ thị vô hướng:
- Tính đối xứng: a[i,j] = a[j,i], với i, j = 1, 2, …, n.
- Tổng các phần tử trên dòng i (hoặc cột j) bằng bậc của đỉnh i (hoặc đỉnh j).
Tính chất của ma trận kề của đồ thị có hướng:
- Không có tính đối xứng.
- Tổng các phần tử trên dòng i bằng bán bậc ra của đỉnh i (deg+(i)), và tổng các phần tử trên cột j bằng bán bậc vào của đỉnh j (deg-(j)).
III. Danh sách kề
Cách biểu diễn đồ thị dưới dạng danh sách kề thường được sử dụng. Trong biểu diễn này, với mỗi đỉnh v của đồ thị, ta lưu trữ danh sách các đỉnh kề với nó, ký hiệu là Ke(v). Mỗi đỉnh i của đồ thị sẽ tương ứng với một danh sách tất cả các đỉnh kề với nó, được ký hiệu là List(i). Ta có thể sử dụng các kiểu dữ liệu tập hợp, mảng hoặc danh sách liên kết để biểu diễn List(i).
Ví dụ:
Danh sách kề của đồ thị vô hướng được biểu diễn bằng danh sách kề như sau:
Bài tập ma trận kề
Xem thêm : Giải bài tập SGK Công nghệ lớp 12 bài 23: Mạch điện xoay chiều ba pha
Bài 1: Biểu diễn đồ thị bằng ma trận kề
Lời giải:
Bài 2: Biểu diễn đồ thị bằng ma trận kề
Lời giải:
Xem thêm : Tên Sarah có ý nghĩa gì? Nguồn gốc tên gọi này xuất hiện từ đâu?
Bài 3: Biểu diễn đồ thị bằng ma trận kề
Bài 4: Biểu diễn đồ thị bằng ma trận kề
V. Câu hỏi liên quan
Ưu điểm của ma trận kề
Ma trận kề có nhiều ưu điểm:
- Hiệu suất thời gian: Các phép toán cơ bản như thêm cạnh, xóa cạnh và kiểm tra sự tồn tại của cạnh giữa hai đỉnh i và j được thực hiện nhanh chóng.
- Khả năng xử lý đồ thị dày đặc: Khi đồ thị có nhiều cạnh, ma trận kề thường là lựa chọn tốt vì nó tiết kiệm bộ nhớ và thao tác nhanh chóng.
- Đa dạng về cấu trúc dữ liệu: Ngay cả khi đồ thị và ma trận kề thưa (ít cạnh), ta vẫn có thể sử dụng cấu trúc dữ liệu để biểu diễn ma trận thưa.
- Sử dụng hiệu quả phần cứng: Tiến bộ trong phần cứng, đặc biệt là GPU, giúp thực hiện các phép toán trên ma trận kề lớn một cách hiệu quả.
- Hiểu biết về đồ thị: Thực hiện các phép toán trên ma trận kề giúp hiểu rõ hơn về cấu trúc và mối quan hệ giữa các đỉnh trong đồ thị.
Nhược điểm của ma trận kề
Ma trận kề cũng có nhược điểm:
- Yêu cầu không gian lớn: Ma trận kề cần lưu trữ thông tin về tất cả các cạnh giữa các đỉnh, dẫn đến sự tiêu thụ bộ nhớ lớn. Kích thước của ma trận là VxV (với V là số lượng đỉnh), đặc biệt tải nặng với đồ thị lớn.
- Không hiệu quả với đồ thị thưa: Thường số lượng cạnh thực tế trong đồ thị ít hơn nhiều so với số lượng cạnh có thể có trong đồ thị đầy đủ. Điều này làm cho ma trận kề không hiệu quả về lưu trữ và thao tác, vì nhiều vị trí trong ma trận sẽ không có giá trị.
- Thao tác trên danh sách kề tốn kém: Các thao tác như truy vấn danh sách cạnh đi vào (inEdges) hoặc đi ra (outEdges) của một đỉnh cụ thể sẽ rất tốn kém khi sử dụng ma trận kề. Điều này phụ thuộc vào việc duyệt qua hàng hoặc cột tương ứng để trích xuất thông tin.
Ứng dụng của ma trận kề
Ma trận kề có nhiều ứng dụng, chẳng hạn như:
- Tạo bảng định tuyến trong mạng.
- Các bài toán về tìm hướng đi hoặc định vị.
Trên đây là một số lý thuyết và bài tập về biểu diễn đồ thị bằng ma trận kề và lời giải tương ứng. Hy vọng bạn đã tìm thấy thông tin hữu ích từ bài viết này trên ttnguyen.net.
Nguồn: https://ispacedanang.edu.vn
Danh mục: Học tập
