Ma trận kề

Bách khoa toàn thư mở Wikipedia

Trong Toán học và Khoa học máy tính, ma trận kề (tiếng Anh: adjacency matrix) cho một đồ thị hữu hạn G gồm n đỉnh là một ma trận n × n, trong đó, các ô không nằm trên đường chéo chính a_ij là số cạnh nối hai đỉnh i và j, còn ô nằm trên đường chéo chính a_ii là hai lần số khuyên tại đỉnh i, hoặc chỉ là số khuyên tại đỉnh đó (bài này chọn cách thứ nhất, các đồ thị có hướng luôn theo cách thứ hai). Mỗi đồ thị có duy nhất một ma trận kề, các đồ thị khác nhau có các ma trận kề khác nhau. Trong trường hợp đặc biệt của đồ thị đơn hữu hạn, ma trận kề là một ma trận (0,1) với các giá trị 0 nằm trên đường chéo chính. Nếu đồ thị là vô hướng, ma trận kề là ma trận đối xứng.

Đối với đồ thị thưa, nghĩa là đồ thị có ít cạnh, người ta thường chọn dùng danh sách kề hơn do nó chiếm ít bộ nhớ hơn. Ma trận liên thuộc là một biểu diễn ma trận khác cho đồ thị.

Quan hệ giữa một đồ thị và ma trận kề của nó được nghiên cứu trong lý thuyết phổ đồ thị (spectral graph theory).

Mục lục 1 Ví dụ 2 Các tính chất 3 Các biến thể 4 Các thỏa hiệp trong vai trò cấu trúc dữ liệu 5 Tham khảo

[sửa] Ví dụ

Ma trận kề cho đồ thị có nhãn đỉnh sau

là

[sửa] Các tính chất

Ma trận kề của một đồ thị vô hướng có tính đối xứng, và do đó có một tập đầy đủ các giá trị riêng (eigenvalue) và cơ sở vector riêng (eigenvector) trực giao. Tập các giá trị riêng của đồ thị là phổ của đồ thị.

Giả sử cho trước hai đồ thị có hướng hoặc vô hướng G₁ và G₂ với các ma trận kề A₁ và A₂. G₁ và G₂ đẳng cấu (isomorphic) khi và chỉ khi tồn tại một ma trận hoán vị (permutation matrix) P sao cho

PA₁P ⁻¹ = A₂.

Cụ thể là A₁ và A₂ là các ma trận đồng dạng và do đó có cùng đa thức cực tiểu (minimal polynomial), đa thức đặc trưng (characteristic polynomial), các giá trị riêng, định thức (determinant) và vết của ma trận (trace). Do đó chúng có thể được dùng như các bất biến đẳng cấu của đồ thị. Cho trước hai ma trận kề, có thể xây dựng lại ma trận hoán vị đã được sử dụng: xem chi tiết tại Ma trận hoán vị.

Tuy nhiên, cần lưu ý rằng điều ngược lại không đúng: hai đồ thị có thể có bộ giá trị riêng giống nhau nhưng chúng không đẳng cấu. Phép nhân với ma trận hoán vị có thể được coi là việc gắn nhãn mới cho các cạnh.

Nếu A là ma trận kề của đồ thị có hướng hoặc vô hướng G, thì ma trận Aⁿ (ma trận tích của n lần A) có một ý nghĩa thú vị: ô tại hàng i và cột j cho biết số đường đi (có hướng hoặc vô hướng) có độ dài n từ đỉnh i tới đỉnh j.

Ma trận I − A (trong đó I ký hiệu ma trận đơn vị n×n) là nghịch đảo được khi và chỉ khi đồ thị G không có chu trình có hướng. Khi đó, ma trận nghịch đảo (I − A)⁻¹ có ý nghĩa sau: ô tại hàng i và cột j cho biết số đường đi có hướng từ đỉnh i tới đỉnh j (giá trị này luôn hữu hạn nếu đồ thị không có chu trình có hướng). Điều này có thể được giải thích bằng cấp số nhân (geometric series) của các ma trận:

(I − A)⁻¹ = I + A + A² + A³ + ...

tương ứng với thực tế rằng số đường đi từ i tới j bằng số đường đi độ dài 0 cộng với số đường đi độ dài 1 cộng với số đường đi độ dài 2 v.v... Đường chéo chính của mọi ma trận kề tương ứng của đồ thị không có khuyên gồm toàn các ô chứa giá trị 0.

[sửa] Các biến thể

Ma trận kề (0,−1,1) của một đồ thị đơn có a_ii = 0 và a_ij = −1 nếu ij là một cạnh và bằng 1 nếu không phải là cạnh. Đồ thị này được dùng trong nghiên cứu các đồ thị chính quy mạnh (strongly regular graph) và các two-graph (đồ thị đôi???).

[sửa] Các thỏa hiệp trong vai trò cấu trúc dữ liệu

Khi được sử dụng với vai trò cấu trúc dữ liệu, đối thủ chính của ma trận kề là danh sách kề. Do mỗi ô trong ma trận kề chỉ đòi hỏi một bit, nên chúng có thể được biểu diễn bằng một cách rất gọn, chỉ chiếm n²/8 byte bộ nhớ liên tục, trong đó n là số đỉnh. Ngoài việc tiết kiệm bộ nhớ, lưu trữ gọn gàng này còn khuyến khích locality of reference (tính địa phương của các truy nhập đến bộ nhớ).

Mặt khác, khi dùng cho đồ thị thưa, danh sách kề lại thắng thế, do chúng không lưu trữ các cạnh không tồn tại. Sử dụng cài đặt danh sách liên kết đơn giản trên một máy tính 32-bit, một danh sách kề cho một đồ thị vô hướng cần khoảng 16e byte, trong đó e là số cạnh của đồ thị.

Lưu ý rằng một đồ thị có thể có nhiều nhất n² cạnh (kể cả các khuyên). Giả sử d = e/n² ký hiệu mật độ của đồ thị. Ta có: 16e > n²/8, có nghĩa là danh sách kề chiếm nhiều không gian hơn khi d > 1/128. Do đó, chỉ nên dùng danh sách kề với đồ thị thưa.

Bên cạnh thỏa hiệp về không gian bộ nhớ, các cấu trúc dữ liệu khác nhau còn tạo thuận lợi cho các thao tác dữ liệu khác nhau. Với một danh sách kề, ta dễ dàng tìm mọi đỉnh kề với một đỉnh cho trước; ta chỉ cần đọc danh sách kề của đỉnh đó. Với một ma trận kề, ta phải duyệt toàn bộ một hàng, việc đó cần thời gian O(n). Còn nếu ta lại muốn biết giữa hai đỉnh cho trước có cạnh nối hay không, điều này có thể được xác định ngay lập tức với một ma trận kề, trong khi đó với một danh sách kề, việc này đòi hỏi thời gian tỷ lệ thuận với bậc nhỏ nhất của các đỉnh trong đồ thị.

[sửa] Tham khảo

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 22.1: Representations of graphs, pp.527–531.

Các chủ đề chính trong toán học
Nền tảng toán học | Đại số | Giải tích | Hình học | Lý thuyết số | Toán học rời rạc | Toán học ứng dụng | Toán học giải trí | Toán học tô pô | Xác suất thống kê

Các chủ đề chính trong đại số tuyến tính
Định thức | Độc lập tuyến tính | Hệ phương trình tuyến tính | Lý thuyết Lie | Ma trận | Nền tảng đại số tuyển tính | Vĩnh thức