Ma_trận liên_kết BULLET Là một trong những cách biểu_diễn đồ_thị biểu_diễn mối quan_hệ giữa các cạnh và các đỉnh của đồ_thị tạo ra ma_trận để biểu_diễn đồ_thị BULLET Còn được gọi là ma_trận liên thuộc BULLET Xét đồ_thị G X U có hướng hay vô hướng BULLET Giả_sử tập X gồm n đỉnh và được sắp thứ_tự X formula _ 1 tập U gồm n cạnh và được sắp thứ_tự U formula _ 2 Đồ_thị vô hướng BULLET Nếu G là đồ_thị vô hướng ma_trận liên_kết của đồ_thị G ký_hiệu A G là ma_trận nhị phân cấp n x m được định_nghĩa là formula _ 3 với BULLET formula _ 3 1 nếu formula _ 5 kề với cạnh formula _ 6 BULLET formula _ 3 0 nếu ngước lại Ví_dụ Cho đồ_thị G vô hướng 4 đỉnh sau BULLET Hãy biểu_diễn đồ_thị G với ma_trận liên_kết BULLET Gọi A là ma_trận biểu_diễn đồ_thị G BULLET Từ đồ_thị G ta thấy BULLET 1 kề với cạnh e1 formula _ 8 BULLET 1 kề với cạnh e2 formula _ 9 BULLET 1 kề với cạnh e4 formula _ 10 BULLET 1 kề với cạnh e5 formula _ 11 BULLET 2 kề với cạnh e3 formula _ 12 BULLET 2 kề với cạnh e4 formula _ 13 BULLET 2 kề với cạnh e6 formula _ 14 BULLET 3 kề với cạnh e1 formula _ 15 BULLET 3 kề với cạnh e2 formula _ 16 BULLET 3 kề với cạnh e3 formula _ 17 BULLET 4 kề với cạnh e5 formula _ 18 BULLET 4 kề với cạnh e6 formula _ 19 BULLET Còn lại nếu đỉnh formula _ 5 không có kề với cạnh formula _ 21 thì gán giá_trị 0 BULLET Kết_quả sau khi biểu_diễn đồ_thị G sang ma_trận liên_kết Lưu_ý Hàng đầu_tiên màu vàng là danh_sách tất_cả các cạnh trong đồ_thị G Đồ_thị có hướng BULLET Nếu G là đồ_thị có hướng không có khuyên ma_trận liên_kết của đồ_thị G ký_hiệu A G là ma_trận nhị phân cấp n x m được định_nghĩa là formula _ 3 với BULLET formula _ 3 1 nếu formula _ 6 hướng ra khỏi đỉnh formula _ 5 BULLET formula _ 3 1 nếu formula _ 6 hướng vào đỉnh formula _ 5 BULLET formula _ 3 0 nếu formula _ 6 không kề với đỉnh formula _ 5 Ví_dụ Cho đồ_thị G có hướng 4 đỉnh sau BULLET Hãy biểu_diễn đồ_thị G với ma_trận liên_kết BULLET Gọi A là ma_trận biểu_diễn đồ_thị G BULLET Từ đồ_thị G ta thấy BULLET 1 kề với cạnh e1 và e1 đi vào 1 formula _ 32 BULLET 1 kề với cạnh e2 và e2 đi vào 1 formula _ 33 BULLET 1 kề với cạnh e4 và e4 đi ra khỏi 1 formula _ 10 BULLET 1 kề với cạnh e5 và e5 đi vào 1 formula _ 35 BULLET 2 kề với cạnh e3 và e3 đi ra khỏi 2 formula _ 12 BULLET 2 kề với cạnh e4 và e4 đi vào 2 formula _ 13 BULLET 2 kề với cạnh e6 và e6 đi ra khỏi 2 formula _ 14 BULLET 3 kề với cạnh e1 và e1 đi ra khỏi 3 formula _ 15 BULLET 3 kề với cạnh e2 và e2 đi ra khỏi 3 formula _ 16 BULLET 3 kề với cạnh e3 và e3 đi vào 3 formula _ 41 BULLET 4 kề với cạnh e5 và e5 đi ra khỏi 4 formula _ 18 BULLET 4 kề với cạnh e6 và e6 đi vào 4 formula _ 43 BULLET Còn lại nếu đỉnh formula _ 5 không có kề với cạnh formula _ 21 thì gán giá_trị 0 BULLET Kết_quả sau khi biểu_diễn đồ_thị G sang ma_trận liên_kết Lưu_ý Hàng đầu_tiên màu vàng là danh_sách tất_cả các cạnh trong đồ_thị G Nhận_xét BULLET Trong ma_trận của đồ_thị có hướng tổng bậc ra của các đỉnh Tổng bậc vào của các đỉnh Đỉnh BULLET Trong ma_trận của đồ_thị vô hướng tổng bậc của tất_cả các đỉnh 2 lần số cạnh BULLET Ưu_điểm BULLET Đồ_thị có cạnh song_song BULLET Ma_trận liên thuộc đỉnh cạnh sẽ tiết_kiệm bộ_nhớ hơn khi đồ_thị có ít cạnh cung BULLET Khuyết_điểm BULLET Biểu_diễn phức_tạp Xem thêm BULLET Ma_trận kề BULLET Ma_trận trọng_số Tham_khảo BULLET Diestel_Reinhard 2005 Graph_Theory_Graduate_Texts in Mathematics 173 3rd ed Springer_Verlag_ISBN 3 540 26183 4 BULLET Coxeter_H_S_M Regular_Polytopes 3rd edition 1973 Dover edition ISBN 0 486 61480 8 Section 9 2 Incidence matrices pp 166 171 BULLET Jonathan_L_Gross_Jay Yellen_Graph_Theory and its applications second edition 2006 p 97 Incidence_Matrices for undirect graphs p 98 incidence matrices for digraphs BULLET Weisstein_Eric_W_Incidence matrix from MathWorld
Ma_trận liên_kết