Có người đề nghị hợp nhất bài viết này vào ma trận kề. (Thảo luận)

Bài viết hoặc đoạn này cần người am hiểu về chủ đề này trợ giúp biên tập mở rộng hoặc cải thiện. Bạn có thể giúp cải thiện trang này nếu có thể. Xem trang thảo luận để biết thêm chi tiết.

Bài viết này cần thêm chú thích nguồn gốc để kiểm chứng thông tin. Mời bạn giúp hoàn thiện bài viết này bằng cách bổ sung chú thích tới các nguồn đáng tin cậy. Các nội dung không có nguồn có thể bị nghi ngờ và xóa bỏ.

• 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[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=(${\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[sửa | sửa mã nguồn]

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 => ${\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ề:

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

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 => ${\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ề:

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

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

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]

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

Bài viết liên quan đến toán học này vẫn còn sơ khai. Bạn có thể giúp Wikipedia mở rộng nội dung để bài được hoàn chỉnh hơn. x t s