Ma trận trọng số

Ma trận trọng số được dùng để biểu diễn đồ thị. Xét đồ thị G=(X, U) (có hướng hay vô hướng) Giả sử tập X gồm n đỉnh và được sắp thứ tự X={ x 1 , x 2 , . . . , x n {\displaystyle x_{\text{1}},x_{\text{2}},...,x_{\text{n}}} }, tập U gồm n cạnh và được sắp thứ tự U={ u 1 , u 2 , . . . , u n {\displaystyle u_{\text{1}},u_{\text{2}},...,u_{\text{n}}} } Ma trận kề của đồ thị G, ký hiệu B(G), là một ma trận nhị phân cấp n x n được định nghĩa như sau: B=( B ij {\displaystyle B_{\text{ij}}} ) với: B=( B ij {\displaystyle B_{\text{ij}}} = trọng số của cạnh nối i và j nếu có cạnh nối x i {\displaystyle x_{\text{i}}} tới x j {\displaystyle x_{\text{j}}} B=( B ij {\displaystyle B_{\text{ij}}} = 0 nếu không có cạnh nối x i {\displaystyle x_{\text{i}}} tới x j {\displaystyle x_{\text{j}}} Nếu G là đồ thị vô hướng, ma trận liên thuộc của đồ thị G, ký hiệu A(G), là ma trận nhị phân cấp nxm được định nghĩa như sau: A=( A ij {\displaystyle A_{\text{ij}}} ) A=( A ij {\displaystyle A_{\text{ij}}} ) = trọng số của cạnh nối i và j nếu có cạnh nối x i {\displaystyle x_{\text{i}}} tới x j {\displaystyle x_{\text{j}}} A=( A ij {\displaystyle A_{\text{ij}}} ) = 0 nếu không có cạnh nối x i {\displaystyle x_{\text{i}}} tới x j {\displaystyle x_{\text{j}}} Cho đồ thị G vô hướng (4 đỉnh): Gọi A là ma trận kề biểu diễn đồ thị G. Từ đồ thị G, ta thấy: 1 và 2 có cạnh nối và trọng số = 7 => A 12 = A 21 = 7 {\displaystyle A_{\text{12}}=A_{\text{21}}=7} 1 và 3 có cạnh nối và trọng số = 2 => A 13 = A 31 = 2 {\displaystyle A_{\text{13}}=A_{\text{31}}=2} 1 và 4 có cạnh nối và trọng số = 1 => A 14 = A 41 = 1 {\displaystyle A_{\text{14}}=A_{\text{41}}=1} 2 và 3 có cạnh nối và trọng số = 5 => A 23 = A 32 = 5 {\displaystyle A_{\text{23}}=A_{\text{32}}=5} 2 và 4 có cạnh nối và trọng số = 2 => A 24 = A 42 = 2 {\displaystyle A_{\text{24}}=A_{\text{42}}=2} Còn lại các cặp đỉnh không có cạnh nối với nhau => A ij = A ji = 0 {\displaystyle A_{\text{ij}}=A_{\text{ji}}=0} Kết quả sau khi biểu diễn đồ thị G sang ma trận kề: Cho đồ thị G có hướng (4 đỉnh): Gọi A là ma trận kề biểu diễn đồ thị G. Từ đồ thị G, ta thấy: 1 và 2 có cạnh nối và trọng số = 4 và 1 đi vào 2 => A 12 = 4 {\displaystyle A_{\text{12}}=4} 2 và 3 có cạnh nối và trọng số = 3 và 2 đi vào 3 => A 23 = 3 {\displaystyle A_{\text{23}}=3} 3 và 1 có cạnh nối và trọng số = 2 và 3 đi vào 1 => A 31 = 2 {\displaystyle A_{\text{31}}=2} 4 và 1 có cạnh nối và trọng số = 5 và 4 đi vào 1 => A 41 = 5 {\displaystyle A_{\text{41}}=5} Còn lại các cặp đỉnh không có cạnh nối với nhau => A ij = 0 {\displaystyle A_{\text{ij}}=0} Kết quả sau khi biểu diễn đồ thị G sang ma trận kề: Ma trận kề Ma trận liên thuộc Ở cách biểu diễn ma trận này, ma trận sẽ không biểu diễn được: Đồ thị có cạnh song song Ở cách biểu diễn ma trận này, ma trận có thể biểu diễn được: Đồ thị có khuyên http://cs.middlesex.cc.nj.us/~schatz/csc236/handouts/WeightedGraph.html[liên kết hỏng] https://inst.eecs.berkeley.edu/~ee127a/book/login/exa_sym_weights_graph.html Lưu trữ 2015-01-29 tại Wayback Machine http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Graph/