tailieunhanh - 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