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={}, tập U gồm n cạnh và được sắp thứ tự U={}
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=( ) 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
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 =>
- 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ề:
Ví dụ đồ thị có hướng
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 =>
- 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ề:
Xem thêm
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
🔥 Top keywords: Đài Truyền hình Kỹ thuật số VTCTrang ChínhGiỗ Tổ Hùng VươngTrương Mỹ LanĐặc biệt:Tìm kiếmHùng VươngVương Đình HuệUEFA Champions LeagueKuwaitChiến dịch Điện Biên PhủFacebookĐài Truyền hình Việt NamTrần Cẩm TúĐội tuyển bóng đá quốc gia KuwaitGoogle DịchViệt NamCúp bóng đá U-23 châu ÁCúp bóng đá U-23 châu Á 2024Real Madrid CFBảng xếp hạng bóng đá nam FIFACleopatra VIITô LâmTim CookNguyễn Phú TrọngHồ Chí MinhHai Bà TrưngManchester City F.C.VnExpressChủ tịch nước Cộng hòa xã hội chủ nghĩa Việt NamNguyễn Ngọc ThắngĐền HùngCúp bóng đá trong nhà châu Á 2024Võ Văn ThưởngOne PieceLịch sử Việt NamCuộc đua xe đạp toàn quốc tranh Cúp truyền hình Thành phố Hồ Chí Minh 2024Phạm Minh ChínhTikTokĐinh Tiên Hoàng