✨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$\text{1}, x\text{2},..., x\text{n}}, tập U gồm n cạnh và được sắp thứ tự U={$u$\text{1}, u\text{2},..., u\text{n}}

Khái niệm

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$\text{ij}) với: *B=($B$\text{ij} = trọng số của cạnh nối i và j nếu có cạnh nối $x$\text{i} tới $x$\text{j} *B=($B$\text{ij} = 0 nếu không có cạnh nối $x$\text{i} tới $x\_\backslash 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\_\backslash text\{ij\}$)

• A=($A$\text{ij}) = trọng số của cạnh nối i và j nếu có cạnh nối $x$\text{i} tới $x\_\backslash text\{j\}$
• A=($A$\text{ij}) = 0 nếu không có cạnh nối $x$\text{i} tới $x\_\backslash text\{j\}$

Ví dụ đồ thị vô hướng

Cho đồ thị G vô hướng (4 đỉnh): Đồ thị G

• 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$\text{12} = A\text{21} = 7 1 và 3 có cạnh nối và trọng số = 2 => $A$\text{13} = A\text{31} = 2 1 và 4 có cạnh nối và trọng số = 1 => $A$\text{14} = A\text{41} = 1 2 và 3 có cạnh nối và trọng số = 5 => $A$\text{23} = A\text{32} = 5 2 và 4 có cạnh nối và trọng số = 2 => $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$\text{ij} = A\text{ji} = 0 *Kết quả sau khi biểu diễn đồ thị G sang ma trận kề: Đồ thị G

Ví dụ đồ thị có hướng

Cho đồ thị G có hướng (4 đỉnh): Đồ thị G

• 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\_\backslash text\{12\}\; =\; 4$ 2 và 3 có cạnh nối và trọng số = 3 và 2 đi vào 3 => $A$\text{23} = 3 ** 3 và 1 có cạnh nối và trọng số = 2 và 3 đi vào 1 => $A$\text{31} = 2 4 và 1 có cạnh nối và trọng số = 5 và 4 đi vào 1 => $A\_\backslash text\{41\}\; =\; 5$ Còn lại các cặp đỉnh không có cạnh nối với nhau => $A\_\backslash text\{ij\}\; =\; 0$ *Kết quả sau khi biểu diễn đồ thị G sang ma trận kề: Đồ thị G