Ma trận liên kết là gì? Khái niệm, tính chất và ứng dụng

Ma trận liên kết (tiếng Anh: incidence matrix, còn gọi là ma trận liên thuộc) là một ma trận toán học biểu diễn mối quan hệ liên thuộc giữa tập hợp các đỉnh và tập hợp các cạnh trong một đồ thị. Trong lý thuyết đồ thị đại số, ma trận liên kết đóng vai trò cầu nối cơ bản chuyển hóa các đặc tính hình học tổ hợp rời rạc của đồ thị thành các đối tượng đại số tuyến tính liên tục, tạo tiền đề để xây dựng các ma trận quan trọng như ma trận Laplacian và phân tích không gian chu trình cũng như không gian lát cắt.

Ma trận liên kết của đồ thị vô hướng

Xét một đồ thị vô hướng đơn $G = (V, E)$ với tập đỉnh gồm $n$ phần tử $V = \{v_1, v_2, \dots, v_n\}$ và tập cạnh gồm $m$ phần tử $E = \{e_1, e_2, \dots, e_m\}$. Theo chuyên khảo của Godsil và Royle (2001), ma trận liên thuộc vô hướng của đồ thị là một ma trận nhị phân $M = (m_{ij})$ có kích thước $n \times m$, trong đó hàng thứ $i$ tương ứng với đỉnh $v_i$ và cột thứ $j$ tương ứng với cạnh $e_j$.

Đối với đồ thị đơn không chứa khuyên, các phần tử của ma trận liên thuộc vô hướng được xác định theo quy tắc liên thuộc hình học:

Vì mỗi cạnh trong đồ thị đơn là đoạn nối trực tiếp giữa đúng hai đỉnh phân biệt, mỗi cột của ma trận liên thuộc vô hướng chứa đúng 2 phần tử nhận giá trị bằng 1, trong khi tất cả các phần tử còn lại trên cột đó đều nhận giá trị bằng 0 theo phân tích của Godsil và Royle (2001). Tổng các phần tử trên hàng thứ $i$ của ma trận đúng bằng bậc của đỉnh $v_i$, tức số lượng các cạnh liên thuộc với đỉnh đó. Trong trường hợp mở rộng cho giả đồ thị xuất hiện khuyên (cạnh nối một đỉnh với chính nó), phần tử tương ứng được quy ước nhận giá trị bằng 2 để bảo toàn bậc của đỉnh theo Bapat (2014), dù quy ước này làm mất đi tính nhị phân thuần túy của ma trận.

Xét ví dụ minh họa về đồ thị chu trình tam giác gồm 3 đỉnh và 3 cạnh. Ma trận liên thuộc vô hướng của đồ thị này có kích thước 3 nhân 3 với đúng 6 phần tử bằng 1 và 3 phần tử bằng 0. Mỗi đỉnh liên kết với 2 cạnh nên tổng mỗi hàng đều bằng 2, và mỗi cạnh nối 2 đỉnh nên tổng mỗi cột cũng bằng 2.

Ma trận liên kết định hướng và cấu trúc đại số

Đối với đồ thị có hướng hoặc một đồ thị vô hướng đã được gán một phép định hướng tùy ý trên các cạnh, cấu trúc liên thuộc được mô tả thông qua ma trận liên thuộc định hướng (oriented incidence matrix). Giả sử mỗi cạnh $e_j$ được gán một hướng đi từ đỉnh xuất phát (đỉnh đuôi) đến đỉnh kết thúc (đỉnh đầu). Theo Bondy và Murty (2008), ma trận liên thuộc định hướng $B = (b_{ij})$ kích thước $n \times m$ có các phần tử được định nghĩa như sau:

Dấu âm và dương thể hiện sự đối xứng bảo toàn dòng chảy trên đồ thị. Vì mỗi cạnh định hướng chỉ có đúng một đỉnh xuất phát và đúng một đỉnh kết thúc, mỗi cột của ma trận liên thuộc định hướng chứa đúng một phần tử nhận giá trị trừ 1, một phần tử nhận giá trị 1 và tất cả các vị trí còn lại đều bằng 0. Hệ quả trực tiếp là tổng các phần tử trên mỗi cột của ma trận định hướng luôn triệt tiêu về giá trị bằng 0 theo định lý của Godsil và Royle (2001):

Tính chất triệt tiêu cột này phản ánh rằng không gian hạch bên trái của ma trận liên thuộc định hướng chứa vector toàn số 1. Do đó, các hàng của ma trận luôn phụ thuộc tuyến tính, dẫn đến hạng của ma trận không bao giờ đạt giá trị tối đa $n$.

Hạng của ma trận liên kết

Hạng đại số của ma trận liên thuộc phản ánh cấu trúc liên thông của đồ thị. Cho một đồ thị $G$ có $n$ đỉnh và $k$ thành phần liên thông. Theo chuyên khảo của Bapat (2014), hạng của ma trận liên thuộc định hướng $B$ được xác định chính xác theo công thức:

Đặc biệt, nếu đồ thị là liên thông (tức $k = 1$), hạng của ma trận liên thuộc định hướng đúng bằng $n - 1$ theo Godsil và Royle (2001). Nếu ta xóa đi một hàng bất kỳ tương ứng với một đỉnh tùy ý, ma trận thu được gọi là ma trận liên kết thu gọn (reduced incidence matrix), ký hiệu là $B_0$, sẽ có kích thước $(n - 1) \times m$ và đạt hạng đủ hàng bằng $n - 1$. Đỉnh bị loại bỏ được gọi là đỉnh gốc hay đỉnh chuẩn mốc (reference node), giữ vai trò tương tự như điểm nối đất chuẩn trong các mạng mạch điện.

Đối với ma trận liên thuộc vô hướng $M$ trên trường số thực, hạng của ma trận phụ thuộc vào việc đồ thị có chứa các thành phần liên thông hai phía hay không. Theo Godsil và Royle (2001), nếu một thành phần liên thông chứa ít nhất một chu trình có độ dài lẻ, các hàng tương ứng trong ma trận vô hướng sẽ độc lập tuyến tính, giúp hạng của khối đó đạt đúng số đỉnh của thành phần.

Mối quan hệ với ma trận kề và ma trận Laplacian

Một trong những kết quả sâu sắc nhất của lý thuyết đồ thị đại số là mối liên hệ giữa ma trận liên thuộc và các toán tử ma trận cơ bản khác. Gọi $D$ là ma trận đường chéo bậc chứa các bậc của từng đỉnh trên đường chéo chính, và $A$ là ma trận kề của đồ thị. Khi nhân ma trận liên thuộc với chuyển vị của chính nó, ta nhận được những cấu trúc ma trận đối xứng đặc biệt:

Đối với ma trận liên thuộc vô hướng $M$, tích giữa ma trận và chuyển vị của nó tạo ra ma trận Laplacian không dấu, ký hiệu là $Q$, theo khẳng định của Bapat (2014):

Đối với ma trận liên thuộc định hướng $B$, tích giữa ma trận và chuyển vị của nó triệt tiêu phần dấu dương của ma trận kề để tạo ra ma trận Laplacian chuẩn, ký hiệu là $L$, theo định lý nền tảng của Godsil và Royle (2001):

Biểu diễn phân tích nhân tử $L = B B^T$ chứng minh rằng ma trận Laplacian là một ma trận nửa xác định dương. Hơn nữa, dạng toàn phương gắn với ma trận Laplacian cho bất kỳ vector thế đỉnh $x$ nào có thể biểu diễn tường minh thành tổng bình phương hiệu thế trên từng cạnh:

Công thức này là cơ sở trực tiếp cho khái niệm năng lượng Dirichlet trên đồ thị và các giải thuật phân cụm phổ.

Định lý cây ma trận Kirchhoff

Định lý cây ma trận được nhà vật lý Gustav Kirchhoff phát hiện lần đầu tiên vào năm 1847 khi nghiên cứu dòng điện trong mạng dây dẫn phức tạp theo lịch sử tổng thuật của Moon (1994). Định lý này thiết lập mối liên hệ giữa các định thức con của ma trận Laplacian và số lượng cây khung của đồ thị.

Gọi $\tau(G)$ là số lượng cây khung của một đồ thị vô hướng liên thông $G$. Theo Moon (1994), mọi phần bù đại số của ma trận Laplacian $L$ đều có giá trị bằng nhau và bằng chính xác số lượng cây khung của đồ thị:

Trong đó $L_{ii}$ là ma trận nhận được từ $L$ bằng cách xóa đi hàng thứ $i$ và cột thứ $i$, tương đương với tích $B_0 B_0^T$ của ma trận liên kết thu gọn. Bằng cách áp dụng công thức khai triển định thức Cauchy-Binet cho tích của hai ma trận hình chữ nhật $B_0$ và $B_0^T$, ta có:

Trong đó tổng được lấy trên tất cả các tập con $S \subset E$ gồm đúng $n - 1$ cạnh, và $B_0[S]$ là ma trận con vuông kích thước $(n - 1) \times (n - 1)$ gồm các cột tương ứng với tập cạnh $S$. Nếu tập cạnh $S$ tạo thành một cây khung, định thức con $\det(B_0[S])$ nhận giá trị bằng 1 hoặc trừ 1, do đó bình phương định thức bằng 1. Ngược lại, nếu $S$ chứa ít nhất một chu trình, các cột của $B_0[S]$ phụ thuộc tuyến tính và định thức con triệt tiêu về 0. Do đó, tổng các bình phương định thức con đúng bằng số lượng cây khung của đồ thị.

Xét ví dụ đồ thị đầy đủ gồm 4 đỉnh và 6 cạnh. Theo công thức Cayley, số lượng cây khung của đồ thị này bằng 4 lũy thừa 2, tức bằng 16 cây khung theo phân tích của Bapat (2014). Định thức của tích ma trận liên kết thu gọn $\det(B_0 B_0^T)$, tức ma trận Laplacian thu gọn $L_{ii}$ có kích thước 3 nhân 3, kiểm chứng chính xác con số 16 cây khung này.

Tính chất toàn đơn mô đun và tối ưu hóa mạng

Một tính chất đại số then chốt của ma trận liên thuộc định hướng là tính toàn đơn mô đun. Theo Bondy và Murty (2008), một ma trận được gọi là toàn đơn mô đun nếu mọi định thức con vuông ở mọi kích thước của nó đều nhận giá trị nằm trong tập hợp gồm ba số là 0, 1 hoặc trừ 1. Ma trận liên thuộc định hướng của bất kỳ đồ thị có hướng nào luôn là một ma trận toàn đơn mô đun.

Năm 1956, hai nhà toán học Alan Hoffman và Joseph Kruskal đã công bố định lý nền tảng chứng minh rằng một ma trận nguyên là toàn đơn mô đun khi và chỉ khi đa diện nghiệm của bài toán quy hoạch tuyến tính tương ứng có các đỉnh cực biên hoàn toàn nguyên với mọi vector vế phải nguyên theo tổng kết của Bondy và Murty (2008). Trong tối ưu hóa mạng, hệ phương trình bảo toàn dòng tại các nút có dạng:

Vì ma trận liên thuộc định hướng $B$ có tính toàn đơn mô đun, các bài toán tối ưu dòng chảy mạng kinh điển như bài toán luồng cực đại, bài toán lưu chuyển chi phí cực tiểu và bài toán tìm đường đi ngắn nhất luôn có nghiệm tối ưu nhận giá trị nguyên khi các vector biên là nguyên. Đối với bài toán ghép cặp cực đại trên đồ thị hai phía, bài toán có thể quy đổi trực tiếp về bài toán luồng cực đại nên cũng thừa hưởng tính nguyên hoàn toàn. Tuy nhiên, trên đồ thị tổng quát có chứa chu trình lẻ, ma trận liên thuộc vô hướng không còn là toàn đơn mô đun; đa diện nghiệm cơ bản sẽ xuất hiện các đỉnh phân số, đòi hỏi thuật toán Blossom của Jack Edmonds phát triển năm 1965 với các bất đẳng thức blossom bổ sung để tìm nghiệm tối ưu nguyên theo Bondy và Murty (2008).

Ứng dụng trong kỹ thuật mạng điện và lý thuyết mở rộng

Từ nguồn gốc nghiên cứu của Kirchhoff năm 1847, ma trận liên kết định hướng là ngôn ngữ hình thức chuẩn mực để thiết lập hệ phương trình trạng thái của mạch điện tập trung. Định luật 1 dòng điện Kirchhoff phát biểu rằng tổng đại số các dòng điện đi vào và đi ra tại mỗi nút mạng phải bằng 0. Khi biểu diễn qua ma trận liên thuộc định hướng $B$ và vector dòng điện trên các nhánh $i$, định luật dòng điện được viết gọn gàng dưới dạng tích ma trận bằng 0 theo Bondy và Murty (2008):

Đồng thời, định luật 2 điện áp Kirchhoff liên hệ giữa hiệu điện thế trên các nhánh $v$ và vector thế tại các nút $u$ thông qua ma trận chuyển vị:

Nghiên cứu hiện đại tiếp tục mở rộng các tính chất phổ của ma trận liên kết. Năm 2023, Sudipta Mallik công bố công trình trên tạp chí Linear and Multilinear Algebra phát triển định lý cây ma trận cho ma trận net Laplacian trên đồ thị có dấu, trong đó ma trận liên kết định hướng được mở rộng để tích hợp các dấu liên kết âm và dương trên từng cạnh, thiết lập công thức đại số mới xác định số lượng cây khung có dấu của đồ thị phức tạp.

Ranh giới hạn chế và điều kiện áp dụng

Mặc dù là công cụ đại số mạnh mẽ, việc sử dụng ma trận liên kết trong phân tích toán học và tính toán số đòi hỏi nhận thức rõ ràng về các ranh giới và hạn chế cấu trúc:

Thứ nhất là ranh giới về chi phí lưu trữ bộ nhớ và độ thưa thuật toán. Ma trận liên kết có kích thước $n \times m$. Đối với các đồ thị dày khi số lượng cạnh tăng nhanh theo bình phương số đỉnh, việc lưu trữ ma trận liên kết đòi hỏi bộ nhớ lớn hơn đáng kể so với ma trận kề có kích thước vuông $n \times n$. Vì mỗi cột của ma trận liên kết chỉ chứa đúng 2 phần tử khác 0, đây là một ma trận cực kỳ thưa; trong khoa học máy tính thực tế, ma trận này thường được nén dưới dạng danh sách liên kết thưa thay vì cấp phát mảng 2 chiều dày đặc.

Thứ hai là hạn chế trong việc biểu diễn khuyên và cạnh song song. Trong ma trận liên thuộc định hướng, một khuyên nối đỉnh $v_i$ với chính nó có đỉnh đầu và đỉnh đuôi trùng nhau, dẫn đến giá trị trên hàng đó bị triệt tiêu bằng 0. Hệ quả là cột tương ứng với khuyên biến thành cột toàn số 0, khiến ma trận định hướng không thể phân biệt được giữa sự xuất hiện của một khuyên và một cột rỗng. Đối với ma trận vô hướng, quy ước gán giá trị bằng 2 cho khuyên là một giải pháp nhân tạo làm phá vỡ cấu trúc nhị phân của ma trận theo phân tích của Bapat (2014).

Thứ ba là điều kiện chặt chẽ về tính toàn đơn mô đun. Ma trận liên thuộc định hướng luôn là toàn đơn mô đun trên mọi đồ thị có hướng. Trái lại, ma trận liên thuộc vô hướng chỉ toàn đơn mô đun khi và chỉ khi đồ thị ban đầu là đồ thị hai phía theo khẳng định của Bondy và Murty (2008). Sự xuất hiện của bất kỳ chu trình lẻ nào (chẳng hạn như tam giác gồm 3 đỉnh) sẽ phá hủy hoàn toàn tính toàn đơn mô đun, khiến các thuật toán quy hoạch tuyến tính trực tiếp không còn bảo đảm sinh ra nghiệm nguyên.

Thứ tư là sự phân biệt cấu trúc khi mở rộng sang siêu đồ thị. Trong siêu đồ thị, mỗi cạnh siêu có thể kết nối đồng thời nhiều hơn 2 đỉnh. Ma trận liên thuộc của siêu đồ thị vẫn là một ma trận hai chiều có kích thước số đỉnh nhân số cạnh siêu, nhưng mỗi cột có thể chứa nhiều hơn 2 phần tử bằng 1. Cần phân biệt ma trận liên thuộc hai chiều này với các cấu trúc tensor kề đa chiều vốn chỉ áp dụng cho siêu đồ thị đều có số đỉnh trên mỗi cạnh siêu bằng nhau.