TAILIEUCHUNG - lý thuyết đồ thị phần 7

Tham khảo tài liệu 'lý thuyết đồ thị phần 7', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 6 17 7 7 5 7 w w 10 13 2 2 3 2 6 p p4 4 4 3 4 .4 18 7 J 12 2 2 Giải thuật Floyd cũng có thểedùng để tìm quan hệ khả liên reachability relation của một đồ thị có hướng G chỉ cần đặt trọng số mỗi cạnh đều là 1 khi đó ma trận w tìm được sè cho tá biết có đường nối giữa 2 đỉnh hay không w iJ cc có đường nôi từ Vj đến Vj Đặc biệt w i i 00 z có chu trình trong G chứa Vị. 2 3 3 2 3 2 3 3 2 1 2 3 3 2 2 2 3 3 2 2 Như vậy ta cũng có thể kiểm tra xem đồ thị có hướng G có chu trình hay không bằng giải thuật Floyd. . THÍ DỤ 4 Áp dụng giải thuật Floyd vào đồ thị 4 2 4 2 . 2 4 2 . 129 6 10 2 7 13 Chú ý w w5 2 4 8 1 8 2 4 5 3 5 11 9 5 2 8 9 6 9 2 7 12 3 9 7 4 2 8 3 7 2 5 16 3 9 5 10 4 9 5 4 1 4 6 2 7 w w6 9 6 9 2 7 12 3 7 3 5 1 6 7 4 7 9 5 3 7 4 7 9 5 10 2 6 2 4 7 5 4 1 4 6 2 7 i Giải thuật Flod có thể áp dụng cho dồ thị vô hưới củng như dồ thị có hướng ta chi cần thay mỗi cạnh tè 126 hưởng uv bằng 1 cặp cạnh có hướng uv và vu với c uv c vu c uv . Tuy nhiên trong trường hợp này các phấn tử trễn đường chéo của ma trận w cần dặt bằng 0. ii Đồ thị có hướng G là liên thông mạnh nếu và chỉ nếu mọi phần tủ không nằm trên đường chéo trong ma trận khoảng cách ngắn nhất đều hữu hạn. GIẢI THUẬT FLOYD MỞ RỘNG Bằng cách đặt P ij Vj nếu có cạnh nối Vị với Vj và po ij không xác định nếu không và xem giải thuật Floyd mở rộng sau Xác định wk và pk dựa vào wk_ và pk_i như sau Với i 1 đến n Với j 1 đến n Nếu WlUij wk_i i k wk_i kj thì đặt wk ij Ww i k WUkj và Pk iJ Pk-j i k Nếu không wk ij và Pk iJ Pk-i ij Dế thấy rằng khi giải thuật này kết thúc ngoài ma trận khoảng cách ngắn nhất w Wn cho ta biết chiều dài đường ngắn nhất nối 2 đỉnh của đồ thị ta còn có thêm ma trận p pn cho ta xác định đường ngắn nhất này đường ngắn nhất đi từ Vị đến Vj xác định bởi dây i p ijl P P ij j PÌP P ij THÍ DỤ 3 Xét đồ thị 127 theo giá thiết qui nạp fl Wk. ijJ chiều dài Ỵ wvi i k wk. kjl fl Do đó theo định nghĩa cúa wk thì wk ijj wk_i ij fl ĩi Mọi đường chiều dài ngắn nhất nối Vi với Vj và đi qu. .

• Toán học
• lý thuyết đồ thị
• toán đồ thị
• toán tin học
• tài liệu đồ thị
• hướng dẫn toán đồ thị
• Bài giảng Lý thuyết đồ thị
• Giới thiệu Lý thuyết đồ thị
• Môn học Lý thuyết đồ thị
• Đại cương Lý thuyết đồ thị
• Hình thức thi Lý thuyết đồ thị
• tài liệu về lý thuyết đồ thị
• học lý thuyết đồ thị tốt
• phương pháp học lý thuyết đồ thị
• hàm trên đồ thị
• Đại cương về đồ thị
• Các mô hình đồ thị
• Thuật ngữ cơ bản của đồ thị
• Đường đi của đồ thị
• Sự liên thông đồ thị
• Biểu diễn đồ thị trên máy tính
• Sự đẳng cấu của đồ thị
• Phương pháp biểu diễn đồ thị
• Biểu diễn đồ thị bằng ma trận kề
• Đồ thị Euler
• Đồ thị Hamilton
• Chu trình Hamilton
• Kiểm tra đồ thị Hamilton
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị