TAILIEUCHUNG - Giáo trình lý thuyết đồ thị - Bài 16

Tham khảo tài liệu 'giáo trình lý thuyết đồ thị - bài 16', 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ả | BÀI 16 . Một số ứng dụng của bài toán luồng lớn nhất Bài toán luồng lớn nhất có rất nhiều ứng dụng trong việc giải quyết các bài toán khác nhau của lý thuyết đồ thị. . Bài toán luồng nhỏ nhất Ngược lại với bài toán luồng lớn nhất chúng ta xét bài toán sau đây Bài toán Cho mạng G c . Tìm luồng t qua mạng có giá trị tz nhỏ nhất và thoả mãn điều kiện a thay cho điều kiện a như sau a V e G E t e c e . Thuật toán Tìm luồng bé nhất Ta dùng phương pháp cải tiến luồng giống như phương pháp giải bài toán luồng lớn nhất. Xuất phát từ một luồng t nào đó thoả mãn điều kiện c ta dùng phương pháp sau đây để giảm giá trị của luồng t. Bước 1 Đánh dấu các đỉnh Đầu tiên đánh dấu cho đỉnh thu z số 0. Nếu đỉnh y đã được đánh dấu có cạnh x y với đỉnh đầu chưa được đánh dấu và t x y c x y thì đánh dấu cho đỉnh x là y. Nếu đỉnh x đã được đánh dấu có cạnh x y thì đánh dấu cho đỉnh y là -x. Với cách đánh dấu này mà đi tới được đỉnh phát x0 thì ta đã tìm được một đường đi vô hướng từ z tới x0 được đánh dấu. Bước 2 Giảm luồng Bây giờ ta có thể giảm luồng đi 1 bằng cách chọn luồng mới t như sau Nếu cạnh e không thuộc đường đi trên thì giữ nguyên luồng nghĩa là t e t e Nếu cạnh e thuộc đường đi này và cùng chiều với chiều từ x0 tới z thì đặt t e t e - 1 vì trên cạnh đó t e c e còn nếu cạnh e ngược chiều thì đặt t e t e 1 . Lặp lại quá trình giảm luồng trên cho đến khi không đánh dấu được tới đỉnh phát x0. Khi đó luồng nhận được có giá trị nhỏ nhất. Ví dụ Xét mạng vận tải sau đây. Hình . Mạng vận tải và luồng đã giảm Luũng cũ cú giỏ trũ là tz 19. Luũng mũi sau khi cũi tiũn cú giỏ trũ là tz 18 và là luũng nhũ nhũt. . Bài toán luòng trên mạng có nhiều đỉnh phát và đỉnh thu Giả sử G c là một mạng vận tải với n đỉnh phát P1 p2 . pn và m đỉnh thu qi q2 . qm. Bài toán tìm luồng lớn nhất từ nhiều đỉnh phát tới nhiều đỉnh thu có thể đưa về bài toán luồng lớn nhất từ một đỉnh phát tới một đỉnh thu bằng cách thêm vào một đỉnh phát giả X0 một đỉnh thu giả Z các cạnh nối X0 với tất

• Toán học
• Chu trình Hamilton
• thuật toán
• đồ thị
• ứng dụng cây
• hàm trên đồ thị
• Lý thuyết đồ thị
• Đường đi Hamilton
• Đồ thị Hamilton
• Định nghĩa về chu trình Hamilton
• Định nghĩa về đường đi Hamilton
• Đường Hamilton
• bài toán mã đi tuần
• chu trình vô hướng hamilton
• Luận án Tiến sĩ Toán học
• Luận án Tiến sĩ
• Cơ sở toán học cho tin học
• Thuật toán đa thức xác định chu trình Hamilton
• Bài giảng Lý thuyết đồ thị
• Đồ thị Euler
• Kiểm tra đồ thị Hamilton
• Bài toán người du lịch
• Bài toán tối ưu tổ hợp
• Đường Hamilton
• Thuật toán nhánh cận giải TSP
• Bài toán người du lịch và thuật toán nhánh cận
• Bài toán tối ưu liên quan đến đường Hamilton
• Đồ thị tách cực
• Đồ thị tách cực phi Hamilton tối đại
• Bậc cực tiểu
• Chu trình euler
• thuật toán tìm chu trình
• đồ thị liên thông
• Bài toán lý thuyết đồ thị
• Bài toán luông
• toán rời rạc
• bài tập học phần
• Đường đi đồ thị
• Đồ thị phẳng
• Bài toán tô màu đồ thị
• Tài liệu Thực hành
• Đồ thị Chu trình
• Lý thuyết đồ thị chu trình
• Đường đi Euler
• Đồ thị ơ2= N
• Đồ thị đơn
• Bài toán HC
• Thuật toán đa thức
• Xây dựng thuật toán đa thức
• Đồ thị 2 phần
• Đồ thị đầy đủ
• Đồ thị rỗng
• tài liệu toán học
• phép toán hedetniemi
• bài giảng toán học
• các bài toán về đường đi
• Bài giảng Toán rời rạc
• Thuật toán Dijkstra
• giáo trình đồ thị
• tài liệu về đồ thị
• ứng dụng của đồ thị
• Đường đi trên đồ thị
• Bài toán đường đi tốt nhất
• Bài giảng Cấu trúc rời rạc
• Cấu trúc rời rạc
• Chu trình và đường đi Euler
• Chu trình và đường đi Hamilton