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={${\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={${\displaystyle 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=(${\displaystyle B_{\text{ij}}}$) với:

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

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

Đồ thị G

Xem thêm

• Ma trận kề
• Ma trận liên thuộc

Nhận xét

• Ở 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

Tham khảo

Liên kết ngoài

• 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/