TAILIEUCHUNG - Giáo trình Lý thuyết đồ thị: Phần 2 - PGS. Nguyễn Cam, PTS. Chu Đức Khánh

Giáo trình Lý thuyết đồ thị được biên soạn nhằm đáp ứng nhu cầu tham khảo sách bằng tiếng Việt của các bạn về lý thuyết đồ thị. Đây là giáo trình Toán dành cho sinh viên chuyên ngành Tin học, do đó hầu hết các vấn đề được trình bày bằng ngôn ngữ giải thuật, mặc dù vậy phần chứng minh vẫn chặt chẽ và rõ ràng. Mời các bạn tham khảo phần 2 sau đây để nắm bắt nội dung chi tiết.  | VI MỘT SỐ ÁP DỤNG . Bài toán mạng . Định nghĩa Mạng Network là một đơn đồ thị có hướng có trọng số G V E trên đó đà chọn 1 đỉnh a gọi là đỉnh phát Source vertex và một đính z gọi là định thu sink vertex . Xét một mạng G V E với đỉnh phát a và đinh thu z. Gọi c e là trọng số cúa cạnh e c e e N . Với mỗi đính X đặt In X le e E I e tới trong x Out x le e E I e tới ngoài x Một hàm tải flow funtion trên G một hàm p E - N Thỏa các điều kiện sau i p e c e Ve e E. ii p e 0 Ve e In a uOut z iii p e ọ e Vx G V a zl o ln x oeln x Một phép cắt cut xác định bởi 1 tập hợp con p của V kí hiệu P P là tập hợp P P xy X e p và y 6 P Trong đó p v p. Phép cắt P p gọi là 1 phép cắt a - z nếu a e p và z E p . Định lí Gọi ọ là 1 hàm tải trên mạng G và Pc V A Z Thì ọ e p e oe M Chứng minh Ta có E P e z E p e eeP eeln x eeP eeOut x 98 Nếu cạnh e có 2 đỉnh cùng nằm trong p thì sô hạng p e xuất hiện ở cả hai vế của bất đẳng thức trên. Đơn giản các hạng p e như thế đi ta còn lại đẳng thức p e V p e . Định lí Với mọi hàm tải p trên mạng G lượng tải khỏi a bằng lượng tải vài z nghĩa là y p e ọ e ecOutia eelnfzl Chứng minh Không mất tính tổng quát có thể giả sử G không chứa cạnh az. Đạt p v a z thi p e p e p e p e eeOuttal eelnlel Ta định nghĩa tài trọng value I ọ I của hàm tãi ọ là lượng tải khỏi a và cùng là lượng tải vào z . Ta sẽ khảo sát bài toán đi tìm hàm tải có tải trọng lớn nhất. Hiển nhiên I p I c a y c e ecOut a Với mồi phép cắt P P ta định nghĩa trọng số capacity của phép cắt này là c P P y c e . Định lí Với mọi hàm tải p và với mọi phép cắt a - z P P trong mạng G ta có I p I c P P Chứng minh Thêm vào G đỉnh mới a0 và cạnh mới aoã với c aoà 00 thành mạng G với đỉnh phát ao và đỉnh thu z . Trong G đặt p aoã I p I và p e p e Ve e E. 99 Ta có 11 í I I p1 p e p e 2L p e 2Z c e a ee ee c P P Suy ra ngay kết quả sau . Hệ luận Với mọi hàm tải ọ và mọi phép cắt a - z P P trong mạng G 11 p I c P

TỪ KHÓA LIÊN QUAN
TAILIEUCHUNG - Chia sẻ tài liệu không giới hạn
Địa chỉ : 444 Hoang Hoa Tham, Hanoi, Viet Nam
Website : tailieuchung.com
Email : tailieuchung20@gmail.com
Tailieuchung.com là thư viện tài liệu trực tuyến, nơi chia sẽ trao đổi hàng triệu tài liệu như luận văn đồ án, sách, giáo trình, đề thi.
Chúng tôi không chịu trách nhiệm liên quan đến các vấn đề bản quyền nội dung tài liệu được thành viên tự nguyện đăng tải lên, nếu phát hiện thấy tài liệu xấu hoặc tài liệu có bản quyền xin hãy email cho chúng tôi.
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.