Ma_trận trọng_số BULLET Ma_trận trọng_số được dùng để biểu_diễn đồ_thị BULLET Xét đồ_thị G X U có hướng hay vô hướng BULLET Giả_sử tập X gồm n đỉnh và được sắp thứ_tự X formula _ 1 tập U gồm n cạnh và được sắp thứ_tự U formula _ 2 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 formula _ 3 với BULLET B formula _ 3 trọng_số của cạnh nối i và j nếu có cạnh nối formula _ 5 tới formula _ 6 BULLET B formula _ 3 0 nếu không có cạnh nối formula _ 5 tới formula _ 6 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 formula _ 10 BULLET A formula _ 10 trọng_số của cạnh nối i và j nếu có cạnh nối formula _ 5 tới formula _ 6 BULLET A formula _ 10 0 nếu không có cạnh nối formula _ 5 tới formula _ 6 Ví_dụ đồ_thị vô hướng Cho đồ_thị G vô hướng 4 đỉnh BULLET Gọi A là ma_trận kề biểu_diễn đồ_thị G BULLET Từ đồ_thị G ta thấy BULLET 1 và 2 có cạnh nối và trọng_số 7 formula _ 17 BULLET 1 và 3 có cạnh nối và trọng_số 2 formula _ 18 BULLET 1 và 4 có cạnh nối và trọng_số 1 formula _ 19 BULLET 2 và 3 có cạnh nối và trọng_số 5 formula _ 20 BULLET 2 và 4 có cạnh nối và trọng_số 2 formula _ 21 BULLET Còn lại các cặp đỉnh không có cạnh nối với nhau formula _ 22 BULLET Kết_quả sau khi biểu_diễn đồ_thị G sang ma_trận kề Ví_dụ đồ_thị có hướng Cho đồ_thị G có hướng 4 đỉnh BULLET Gọi A là ma_trận kề biểu_diễn đồ_thị G BULLET Từ đồ_thị G ta thấy BULLET 1 và 2 có cạnh nối và trọng_số 4 và 1 đi vào 2 formula _ 23 BULLET 2 và 3 có cạnh nối và trọng_số 3 và 2 đi vào 3 formula _ 24 BULLET 3 và 1 có cạnh nối và trọng_số 2 và 3 đi vào 1 formula _ 25 BULLET 4 và 1 có cạnh nối và trọng_số 5 và 4 đi vào 1 formula _ 26 BULLET Còn lại các cặp đỉnh không có cạnh nối với nhau formula _ 27 BULLET Kết_quả sau khi biểu_diễn đồ_thị G sang ma_trận kề Xem thêm BULLET Ma_trận kề BULLET Ma_trận liên thuộc Nhận_xét BULLET Ở cách biểu_diễn ma_trận này ma_trận sẽ không biểu_diễn được BULLET Đồ_thị có cạnh song_song BULLET Ở cách biểu_diễn ma_trận này ma_trận có_thể biểu_diễn được BULLET Đồ_thị có khuyên Liên_kết ngoài BULLET http cs middlesex cc nj us schatz csc236 handouts WeightedGraph html BULLET https inst eecs berkeley edu ee127a book login exa _ sym _ weights _ graph html BULLET http www csse monash edu au lloyd tildeAlgDS Graph
Ma_trận trọng_số