Ma trận trọng số

Bách khoa toàn thư mở Wikipedia
  • 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={}, tập U gồm n cạnh và được sắp thứ tự U={}

Khái niệm[sửa | sửa mã nguồ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=() với:

  • B=( = trọng số của cạnh nối i và j nếu có cạnh nối tới
  • B=( = 0 nếu không có cạnh nối tới

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=() = trọng số của cạnh nối i và j nếu có cạnh nối tới
  • A=() = 0 nếu không có cạnh nối tới

Ví dụ đồ thị vô hướng[sửa | sửa mã nguồn]

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 =>
    • 1 và 3 có cạnh nối và trọng số = 2 =>
    • 1 và 4 có cạnh nối và trọng số = 1 =>
    • 2 và 3 có cạnh nối và trọng số = 5 =>
    • 2 và 4 có cạnh nối và trọng số = 2 =>
    • Còn lại các cặp đỉnh không có cạnh nối với nhau =>
  • Kết quả sau khi biểu diễn đồ thị G sang ma trận kề:
Đồ thị G

Ví dụ đồ thị có hướng[sửa | sửa mã nguồn]

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

Xem thêm[sửa | sửa mã nguồn]

Nhận xét[sửa | sửa mã nguồn]

  • Ở 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[sửa | sửa mã nguồn]

Liên kết ngoài[sửa | sửa mã nguồn]