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

• Kỹ thuật lập trình
• Giáo trình Lý thuyết đồ thị
• Lý thuyết đồ thị
• Bài toán áp dụng lý thuyết đồ thị
• Bài toán mạng
• Bài toán tô màu
• Giải thuật chu trình Hamilton
• bài giảng 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ị
• Đồ thị vô hướng
• Đồ thị có hướng
• Chu trình Euler
• Chu trình Hamilton
• tài liệu về đồ thị
• biểu diễn đồ thị
• bậc của đỉnh trong đồ thị
• đại cương đồ thị
• bài giảng về đồ thị
• tô màu đồ thị
• Vẽ đồ thị
• đồ thị trên máy tính
• ma trận
• đồ thị liên thông
• tài liệu lý thuyết đồ thị
• đồ thị hữu hạn
• đồ thị vô hạn
• giáo trình tin học
• tin học đại cương
• tài liệu học đại học
• kỹ thuật lập trình
• tài liệu lập trình máy tính
• lý thuyết đô thị
• khoa học máy tính
• ngôn ngữ lập trình
• đồ thị cơ bản
• tổng quan đồ thị
• Mô hình toán ứng dụng
• Giáo trình Mô hình toán ứng dụng
• Sơ lược lý thuyết đồ thị
• Phương pháp sơ đồ mạng lưới
• Lý thuyết phục vụ công cộng
• biểu diễn hình học
• biêu diễn đồ thị bằng ma trận
• biểu diễn đồ thị bằng bảng
• sự đẳng cấu của các đồ thị
• Giáo trình
• sổ tay toán học
• tài liệu học môn toán
• đại số
• các loại đồ thị
• Giáo trình Toán rời rạc
• Đại số Bool
• Đồ thị Euler
• Đồ thị Hamilton
• Luồng cực đại trong mạng
• Giáo dục đào tạo
• giáo trình cao đẳng đại học
• bài tập về lý thuyết đồ thị
• đồ thị phẳng
• bài toán t
• toán rời rạc
• giáo trình toán
• đường đi trong đồ thị
• tài liệu toán học
• đồ thị
• tài liệu toán rời rạc
• thuật toán
• ứng dụng cây
• hàm trên đồ thị