Ma trận kề - Danh sách kề là gì | Cách biểu diễn đồ thị

Trong lý thuyết đồ thị toán rời rạc, ma trận kề giúp biểu diễn và xử lý các bài toán đồ thị như: tìm đường đi ngắn nhất hoặc thuật toán tìm cây bao trùm tối thiểu. Bài viết dưới đây, TTnguyen sẽ giới thiệu về lý thuyết, cách biểu diễn đồ thị bằng ma trận kề qua một số bài tập có lời giải. Bắt đầu thôi!

Xem thêm:

lý thuyết đồ thị toán rời rạc: Đường đi, chu trình, đồ thị liên thông

Đường đi và chu trình euler

bài tập toán rời rạc chương 1 có lời giải

Nội dung

I. Ma trận kề là gì?

Ma trận kề hay còn gọi là ma trận liền kề (adjacency matrix) là cách biểu diễn đồ thị G = {V,E} dưới dạng ma trận vuông kích thước n x n, với n là số lượng đỉnh của đồ thị. Phần tử tại hàng i, cột j trong ma trận kề sẽ có giá trị:

a[i][j] = 1 nếu tồn tại cạnh nối giữa hai đỉnh i và j
a[i][j] = 0 nếu không có cạnh nối

Ví dụ ma trận kề:

II. Biểu diễn đồ thị bằng ma trận kề

Đồ thị vô hướng: Ma trận kề của đồ thị vô hướng là ma trận đối xứng, tức là a[i][j] = a[j][i]
Đồ thị có hướng: Ma trận kề của đồ thị có hướng không đối xứng, các phần tử thể hiện mối quan hệ theo hướng cụ thể giữa hai đỉnh.

III.Tính chất của ma trận kề

Ma trận kề của đồ thị vô hướng:

Tính đối xứng: a[i][j] = a[j][i]
Tổng các phần từ trên hàng i (cột j) bằng bậc của đỉnh i (đỉnh j)

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))
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))

IV. Danh sách kề là gì?

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ị chúng ta lưu trữ danh sách các đỉnh kề với nó mà ta ký hiệu là Ke(v), nghĩa là:

\(Ke(v) = { u \in V: (u, v) \in E} \)

Với cách biểu diễn này, mỗi đỉnh i của đồ thị, ta làm tương ứng với một danh sách tất cả các
đỉnh kề với nó và được ký hiệu là List(i). Để biểu diễn List(i), ta có thể dùng các kiểu dữ liệu kiểu tập hợp, mảng hoặc danh sách liên kết.

Ví dụ danh sách kề: Danh sách kề của đồ thị vô hướng được biểu diễn bằng danh sách kề như sau:

V. Ưu điểm và nhược điểm của ma trận kề

Ư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 hiệu quả về mặt thời gian.
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ó giúp tiết kiệm bộ nhớ và thực hiện các 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: Những tiến bộ trong phần cứng, đặc biệt là GPU, cho phé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 chúng ta 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:

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 việc tiêu thụ một lượng lớn bộ nhớ. Kích thước của ma trận là VxV (với V là số lượng đỉnh), dẫn đến một tải nặng về mặt bộ nhớ đặc biệt khi đồ thị lớn.
Không hiệu quả với đồ thị thưa: Trong hầu hết các trường hợp, 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ề trở nên không hiệu quả về mặt 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ác cạnh đi vào (inEdges) hoặc cạnh đ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 do cần phải duyệt qua toàn bộ hàng hoặc cột tương ứng để trích xuất thông tin.