Tài liệu Bài toán luồng lớn nhất và luồng chi phí nhỏ nhất trên mạng

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC HOÀNG THỊ CÚC BÀI TOÁN LUỒNG LỚN NHẤT VÀ LUỒNG CHI PHÍ NHỎ NHẤT TRÊN MẠNG LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2016 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC HOÀNG THỊ CÚC BÀI TOÁN LUỒNG LỚN NHẤT VÀ LUỒNG CHI PHÍ NHỎ NHẤT TRÊN MẠNG LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Toán ứng dụng Mã số: 60 46 01 12 NGƯỜI HƯỚNG DẪN KHOA HỌC GS.TS. TRẦN VŨ THIỆU Thái Nguyên - 2016 i Mục lục Danh sách kí hiệu iii Danh sách hình vẽ v Lời nói đầu 1 Chương 1. Kiến thức chuẩn bị 4 1.1 Khái niệm cơ bản về đồ thị . . . . . . . . . . . . . . . . . . . . . 4 1.1.1 Định nghĩa và ký hiệu . . . . . . . . . . . . . . . . . . . 4 1.1.2 Đồ thị đẳng cấu . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.3 Đồ thị liên thông . . . . . . . . . . . . . . . . . . . . . . 8 1.1.4 Đường và chu trình trong đồ thị . . . . . . . . . . . . . . 8 1.1.5 Một số dạng đồ thị đặc biệt . . . . . . . . . . . . . . . . . 9 1.2 Mạng và luồng . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3 Một số bài toán tối ưu trên đồ thị . . . . . . . . . . . . . . . . . . 13 1.3.1 Ghép cặp, phủ cạnh, phủ đỉnh, tập ổn định và clique . . . 13 1.3.2 Bài toán phủ đỉnh, phủ cạnh và ghép cặp . . . . . . . . . 14 Kết luận Chương 1 . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.4 Chương 2. Bài toán luồng lớn nhất trên mạng 2.1 17 Nội dung bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.1.1 17 Mạng và luồng . . . . . . . . . . . . . . . . . . . . . . . ii 2.1.2 Luồng tương thích lớn nhất . . . . . . . . . . . . . . . . . 19 2.1.3 Bài toán luồng lớn nhất trên mạng . . . . . . . . . . . . . 19 2.1.4 Tiêu chuẩn tối ưu . . . . . . . . . . . . . . . . . . . . . . 20 2.2 Thuật toán tìm luồng lớn nhất . . . . . . . . . . . . . . . . . . . . 22 2.3 Luồng lớn nhất và thiết diện nhỏ nhất . . . . . . . . . . . . . . . 25 2.3.1 Khả năng của một mạng . . . . . . . . . . . . . . . . . . 25 2.3.2 Thiết diện nhỏ nhất . . . . . . . . . . . . . . . . . . . . . 27 Kết luận Chương 2 . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.4 Chương 3. Bài toán luồng chi phí nhỏ nhất trên mạng 30 3.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.2 Tiêu chuẩn tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.3 Thuật toán thu hẹp chính tắc . . . . . . . . . . . . . . . . . . . . 35 3.4 Trường hợp tổng quát (d(u) 6= +∞) . . . . . . . . . . . . . . . . . 40 3.5 Kết luận Chương 3 . . . . . . . . . . . . . . . . . . . . . . . . . 41 Kết luận 42 Tài liệu tham khảo 43 iii Danh sách kí hiệu G = G(V, E) đồ thị vô hướng với tập đỉnh V , tập cạnh E G = (A,U, d(u)) mạng với tập đỉnh A, tập cung U, khả năng các cung d(u) X = {x(u)} luồng trên mạng u = (i, j) cạnh (cung) đi từ đỉnh i đến đỉnh j c(u), di j khả năng thông qua của cạnh (cung) u = (i, j) d(u), di j khả năng thông qua của cạnh (cung) u = (i, j) x(u) cường độ của luồng trên cạnh (cung) u Kn đồ thị hai phần đầy đủ n đỉnh Km,n đồ thị hai phần đầy đủ, mỗi phần m và n đỉnh pi yêu cầu của đỉnh i (đỉnh i là trạm phát khi pi < 0, đỉnh i là trạm thu khi pi > 0) αi = αi (X) thông lượng của luồng tại đỉnh i Ui− tập hợp các cung đi tới đỉnh i Ui+ tập hợp các cung đi khỏi đỉnh i σ (X) trị số của luồng X f (X) hàm cước phí của luồng X µ dây chuyền hay chu trình trên mạng iv Danh sách hình vẽ 1.1 Sơ đồ khu phố . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Sơ đồ mạch điện . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Đồ thị đại diện . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4 Cạnh kép và đa đồ thị . . . . . . . . . . . . . . . . . . . . . . . . 6 1.5 Khuyên trong đa đồ thị . . . . . . . . . . . . . . . . . . . . . . . 6 1.6 Đồ thị có hướng . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.7 Bậc của đỉnh trong đồ thị . . . . . . . . . . . . . . . . . . . . . . 7 1.8 Các đồ thị đẳng cấu với đồ thị ở Hình 1.3 . . . . . . . . . . . . . 7 1.9 Đồ thị G1 , G2 và hợp G1 ∪ G2 . . . . . . . . . . . . . . . . . . . 8 1.10 Đồ thị không liên thông . . . . . . . . . . . . . . . . . . . . . . . 8 1.11 Ví dụ về rừng và cây . . . . . . . . . . . . . . . . . . . . . . . . 10 1.12 Đồ thị đầy đủ K4 và K5 . . . . . . . . . . . . . . . . . . . . . . . 11 1.13 Đồ thị hai phần . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.14 Đồ thị hai phần đầy đủ: K1,3 , K2,3 , K3,3 , K4,3 . . . . . . . . . . . . 11 1.15 Phủ đỉnh, phủ cạnh và ghép cặp . . . . . . . . . . . . . . . . . . 15 2.1 Thông lượng ở đỉnh (αi = 18 − 9 = 7) . . . . . . . . . . . . . . . 18 2.2 Dây chuyền chưa bão hòa . . . . . . . . . . . . . . . . . . . . . . 20 2.3 Luồng lớn nhất trong mạng dạng cây . . . . . . . . . . . . . . . . 25 v 3.1 Ví dụ 3.3.6: yêu cầu các trạm, cước phí các cung . . . . . . . . . . 39 3.2 Rút gọn đường nhánh . . . . . . . . . . . . . . . . . . . . . . . . 39 3.3 Luồng tối ưu: x(u) ghi ở cung u . . . . . . . . . . . . . . . . . . . 39 1 Lời nói đầu Các sơ đồ giao thông, sơ đồ mạch điện hay sơ đồ tổ chức của một cơ quan, trường học đã khá quen thuộc với nhiều người. Đó là những hình ảnh sinh động và cụ thể của một khái niệm toán học trừu tượng - khái niệm đồ thị (graph). Có thể hiểu đơn giản "đồ thị" là một cấu trúc toán học rời rạc, bao gồm hai yếu tố chính là đỉnh và cạnh cùng với mối quan hệ giữa chúng. Nếu trên các cạnh của đồ thị có xét tới sự di chuyển của lượng vật chất (nước, xăng dầu, hàng hóa . . . ) thì đồ thị còn được gọi là một mạng (network). Đồ thị và mạng là mô hình toán học cho nhiều vấn đề lý thuyết và thực tiễn đa dạng. Lý thuyết đồ thị và mạng đề cập tới nhiều bài toán đa dạng và có ý nghĩa thực tiễn thiết thực, cùng nhiều phương pháp xử lý và thuật toán giải độc đáo và hiệu quả, giúp ích cho sự phát triển tư duy toán học nói chung và khả năng vận dụng trong cuộc sống thường ngày nói riêng. Trong số đó đáng chú ý là hai bài toán sau đây: bài toán luồng lớn nhất và bài toán luồng chi phí nhỏ nhất trên mạng. Bài toán thứ nhất là tìm cách vận chuyển được nhiều hàng nhất từ một (hay nhiều) đỉnh nguồn tới một (hay nhiều) đỉnh đích trên một mạng cho trước. Bài toán thứ hai thực chất là bài toán vận tải trên mạng làm sao vận chuyển được hàng hóa từ các điểm cung cấp tới các điểm tiêu thụ với chi phí nhỏ nhất. Các bài toán này đã được nhiều nhà toán học nổi tiếng quan tâm, nghiên cứu như Ford-Fulkerson, Hoàng Tụy. . . và đã có lý thuyết đẹp về luồng trên mạng. Luận văn “Luồng lớn nhất và luồng chi phí nhỏ nhất trên mạng” có mục đích 2 tìm hiểu và trình bày về hai bài toán nói trên và các thuật toán giải hai bài toán đó. Luận văn được viết dựa chủ yếu trên các tài liệu tham khảo hiện có [1]-[5]. Nội dung luận văn gồm ba chương: • Chương 1. Kiến thức chuẩn bị nhắc lại một số khái niêm cơ bản về đồ thị: đỉnh và cạnh, đường và chu trình, đồ thị đặc biệt (rừng và cây, đồ thị đầy đủ, đồ thị hai phần), khái niệm mạng và luồng trên mạng. Giới thiệu một số bài toán tối ưu trên đồ thị: tìm phủ đỉnh, phủ cạnh nhỏ nhất, tìm ghép cặp lớn nhất. • Chương 2. Bài toán luồng lớn nhất trên mạng trình bày nội dung bài toán luồng lớn nhất trên mạng, một dạng mở rộng của bài toán luồn lớn nhất trên mạng giao thông Ford -Fulkerson, nêu điều kiện cần và đủ để có luồng lớn nhất và thuật toán tìm luồng lớn nhất trên mạng. Cuối chương giới thiệu định lý quan trọng cho biết trị số của luồng lớn nhất bằng khả năng của thiết diện nhỏ nhất. • Chương 3. Bài toán luồng chi phí nhỏ nhất trên mạng đề cập tới bài toán vận tải trên mạng và trình bày "thuật toán thu hẹp chính tắc" giải bài toán. Luận văn này được thực hiện tại Trường Đại học Khoa học - Đại học Thái Nguyên và hoàn thành với sự hướng dẫn của GS.TS. Trần Vũ Thiệu (Viện Toán học - Viện Hàn lâm Khoa học & Công nghệ Việt Nam). Tác giả xin được bày tỏ lòng biết ơn chân thành và sâu sắc tới người hướng dẫn khoa học của mình, người đã đặt vấn đề nghiên cứu, dành nhiều thời gian hướng dẫn và tận tình giải đáp những thắc mắc của tác giả trong suốt quá trình làm luận văn. Tác giả xin trân trọng cảm ơn Ban Giám hiệu Trường Đại học Khoa học - Đại học Thái Nguyên, Ban Chủ nhiệm Khoa Toán–Tin, cùng các giảng viên tham gia giảng dạy đã tạo mọi điều kiện tốt nhất có thể để tác giả học tập và nghiên cứu. 3 Nhân dịp này, tác giả cũng xin gửi lời cảm ơn tới tập thể Lớp B, cao học Toán khóa 8 (2014-2016) đã động viên và giúp đỡ tác giả rất nhiều trong suốt quá trình học tập. Lời cuối, tác giả muốn dành những lời cảm ơn đặc biệt nhất đến đại gia đình đã luôn động viên và chia sẻ những khó khăn để tác giả hoàn thành tốt luận văn này. Thái Nguyên, ngày 20 tháng 5 năm 2016 Tác giả Hoàng Thị Cúc 4 Chương 1 Kiến thức chuẩn bị Chương này trình bày các kiến thức cơ sở về lý thuyết đồ thị, chủ yếu nhắc lại vắn tắt một số định nghĩa và khái niệm dùng trong lý thuyết đồ thị và mạng, giới thiệu một số bài toán tối ưu và bài toán luồng lớn nhất trên mạng. Trong chương dẫn ra nhiều ví dụ minh họa. Nội dung của chương được tham khảo chủ yếu từ các tài liệu [1], [2], [4] và [5]. 1.1 1.1.1 Khái niệm cơ bản về đồ thị Định nghĩa và ký hiệu Trong thực tế ta thường gặp các sơ đồ giao thông (Hình 1.1 ) hay sơ đồ mạch điện (Hình 1.2). Các sơ đồ này được khái quát thành sơ đồ ở Hình 1.3. Từ đó ta đi Hình 1.1: Sơ đồ khu phố Hình 1.2: Sơ đồ mạch điện tới định nghĩa sau: Đồ thị là một tập hợp hữu hạn và khác rỗng các điểm, gọi là các đỉnh hay nút, và một tập hợp các đường (thẳng hay cong) nối liền một số cặp điểm này, gọi là các cạnh của đồ thị (số cạnh có thể bằng 0). 5 Hình 1.3: Đồ thị đại diện Mỗi đỉnh của đồ thị thường được ký hiệu bằng một chữ cái (a, b, c, . . . hay A, B, C,. . . ) hoặc chữ số (1, 2, 3, . . . ). Cạnh nối liền đỉnh v với đỉnh w được ký hiệu là (v, w) hay đơn giản là vw (v và w có thể là các chữ số). Một cạnh có dạng (a, a), nối đỉnh a với chính nó, gọi là một khuyên. Nếu đồ thị G có tập đỉnh là V và tập cạnh là E ⊆ V ×V thì để cho gọn, ta viết G = (V, E). Ta cũng dùng ký hiệu V (G) để chỉ tập đỉnh và E(G) để chỉ tập cạnh của đồ thị G. Ký hiệu n = |V (G)| là số đỉnh và m = |E(G)| là số cạnh của đồ thị G. Để dễ hình dung, mỗi đồ thị thường được biểu diễn bởi một hình vẽ trên mặt phẳng. Chẳng hạn, Hình 1.3 biểu diễn một đồ thị có 5 đỉnh: P, Q, R, S, T và 8 cạnh (mỗi cạnh là một đoạn thẳng nối hai đỉnh). Chú ý rằng điểm cắt nhau của hai cạnh PS và QT trong hình vẽ không phải là một đỉnh của đồ thị. Đỉnh v gọi là kề đỉnh w nếu có một cạnh của đồ thị nối v với w. Nếu ký hiệu cạnh này là e thì ta viết e = (v, w) và nói cạnh e liên thuộc v, w hay v, w là hai đầu mút của e. Cạnh e và e0 gọi là kề nhau nếu e, e0 có chung đỉnh. Hai cạnh e và e0 cùng nối một cặp đỉnh gọi là cạnh kép. Đồ thị không có cạnh kép gọi là một đơn đồ thị. Trái lại, gọi là một đa đồ thị. Hình 1.4 và 1.5 minh họa cạnh kép và khuyên trong đa đồ thị. Một cạnh của đồ thị gọi là cạnh có hướng nếu qui định rõ một đầu mút của cạnh là đỉnh đầu, mút kia là đỉnh cuối. Cạnh có hướng còn được gọi là một cung. Một đồ thị gồm toàn các cạnh gọi là đồ thị vô hướng, đồ thị gồm toàn các cung 6 Hình 1.4: Cạnh kép và đa đồ thị Hình 1.5: Khuyên trong đa đồ thị gọi là đồ thị có hướng. Một đồ thị vừa có cạnh vừa có cung gọi là đồ thị hỗn hợp. Bằng cách thay một cạnh bởi hai cung có hướng ngược chiều nhau, ta có thể qui mọi đồ thị về đồ thị có hướng. Hình 1.6 mô tả một đồ thị có hướng. Hình 1.6: Đồ thị có hướng Bậc của đỉnh v trong đồ thị vô hướng là số cạnh liên thuộc nó, ký hiệu là ρ(v). Đỉnh có bậc 0 gọi là đỉnh cô lập, đỉnh có bậc 1 gọi là đỉnh treo. Tương tự, trong đồ thị có hướng ta gọi bậc ra (bậc vào) của đỉnh v là số cung đi khỏi v (số cung đi tới v), ký hiệu tương ứng là ρ + (v) và ρ − (v). Qui ước: khuyên tại một đỉnh được tính 2 lần. Ví dụ trong đồ thị vẽ ở Hình 1.7 ta có ρ(P) = ρ(S) = ρ(U) = ρ(V ) = 2; ρ(Q) = ρ(R) = 3 và ρ(T ) = 4 (có khuyên ở T ). Dễ dàng kiểm tra các tính chất sau đây về bậc của đỉnh trong đồ thị: (1) Trong một đồ thị vô hướng, tổng số bậc của mọi đỉnh bằng hai lần số cạnh của đồ thị và số đỉnh có bậc lẻ bao giờ cũng là một số chẵn. 7 Hình 1.7: Bậc của đỉnh trong đồ thị (2) Trong một đồ thị có hướng, tổng các bậc vào của mọi đỉnh bằng tổng các bậc ra của mọi đỉnh và bằng tổng số cung trong đồ thị. Nhiều tính chất của đồ thị có hướng không phụ thuộc vào hướng các cung trong đồ thị. Vì thế, khi bỏ qua hướng trên các cung (đổi cung thành cạnh) ta sẽ nhận được một đồ thị vô hướng, gọi là đồ thị nền của đồ thị có hướng đã cho. 1.1.2 Đồ thị đẳng cấu Hai đồ thị G1 và G2 gọi là đẳng cấu nếu chúng có số đỉnh và số cạnh như nhau và có phép "tương ứng một-một" giữa tập đỉnh của G1 và G2 sao cho hai đỉnh được nối với nhau bởi một cạnh trong đồ thị này khi và chỉ khi hai đỉnh tương ứng trong đồ thị kia cũng được nối với nhau bởi một cạnh và ngược lại. Hình 1.8 vẽ các đồ thị đẳng cấu với đồ thị vẽ ở Hình 1.3. Các cạnh của hai đồ thị ở Hình 1.9 chỉ gặp nhau ở đỉnh. Các đồ thị đẳng cấu được xem là tương đương. Hình 1.8: Các đồ thị đẳng cấu với đồ thị ở Hình 1.3 8 1.1.3 Đồ thị liên thông Có thể ghép hai đồ thị để lập nên một đồ thị lớn hơn. Cho G1 = (V (G1 ), E(G1 )), G2 = (V (G2 ), E(G2 )) với V (G1 ) ∩ V (G2 ) = 0. / Khi đó, hợp G1 ∪ G2 là đồ thị có tập đỉnh là V (G1 ) ∪V (G2 ) và tập cạnh là E(G1 ) ∪ E(G2 ) (Hình 1.9). Hình 1.9: Đồ thị G1 , G2 và hợp G1 ∪ G2 Hầu hết các đồ thị thường gặp là đồ thị ghép. Một đồ thị được gọi là liên thông nếu nó không biểu diễn được dưới dạng hợp của hai hay nhiều đồ thị. Trái lại, đồ thị gọi là không liên thông. Rõ ràng là bất cứ một đồ thị không liên thông G nào cũng biểu diễn được dưới dạng hợp của các đồ thị liên thông, mỗi đồ thị liên thông gọi là một thành phần liên thông của G. Chẳng hạn, một đồ thị gồm ba thành phần liên thông được vẽ ở Hình 1.10. Hình 1.10: Đồ thị không liên thông 1.1.4 Đường và chu trình trong đồ thị Đường P từ đỉnh v tới đỉnh w là một dãy liên tiếp các cạnh có dạng (a0 , a1 ), (a1 , a2 ), . . . , (ak−1 , ak ) 9 với (ai−1 , ai ) ∈ E(G), a0 = v, ak = w và k ≥ 1, trong đó các đỉnh a0 , a1 , . . . , ak đều khác nhau. Để đơn giản, đôi khi ta viết P = {a0 , a1 , . . . , ak } và nói đó là đường nối đỉnh v và đỉnh w. Đỉnh v gọi là đỉnh đầu, đỉnh w gọi là đỉnh cuối của đường P. Một đường nối một đỉnh với chính nó (đỉnh đầu trùng với đỉnh cuối) gọi là một chu trình. Độ dài của đường (chu trình) là số cạnh của đường (chu trình) đó. Ví dụ với đồ thị vẽ ở Hình 1.9 một đường nối đỉnh P và đỉnh R là (P, T ), (T, Q), (Q, R) hay đơn giản là P, T , Q, R. Hai đường khác từ P tới R là P, T , S, R và P, Q, R hay P, S, R. Đồ thị này có các chu trình sau: (P, Q), (Q, R), (R, S), (S, T ), (T, P); (Q, S), (S, T ), (T, Q), v.v . . . Đường và chu trình trong đồ thị có hướng được định nghĩa tương tự (cung thay cho cạnh). Để phân biệt, đôi khi ta gọi đó là đường (chu trình) định hướng. Đồ thị có hướng ở Hình 1.3 có các đường định hướng từ đỉnh 1 tới đỉnh 6 là: 1, 3, 6; 1, 3, 4, 6; 1, 3, 5, 6; 1, 2, 4, 6... Đồ thị đó không có chu trình định hướng. 1.1.5 Một số dạng đồ thị đặc biệt Mục này trình bày một số dạng đồ thị đặc biệt, đáng chú ý và hay được dùng. Ta cần thêm một số khái niệm: Đồ thị con H của một đồ thị G là đồ thị nhận được từ G bằng cách bỏ đi một số đỉnh và một số cạnh của nó. Đồ thị con H của G gọi là đồ thị con bao trùm nếu V (H) = V (G). Một đồ thị có đỉnh, nhưng không có cạnh nào gọi là một đồ thị rỗng. Rừng và cây. Có thể hiểu đồ thị liên thông theo nghĩa tương đương như sau. Một đồ thị vô hướng gọi là liên thông nếu có đường đi nối hai đỉnh bất kỳ của đồ thị. Trái lại, đồ thị gọi là không liên thông. Đồ thị không liên thông sẽ bị tách thành một số đồ thị con liên thông, đôi một không có đỉnh chung. Mỗi đồ thị con liên thông như thế là một thành phần liên thông. Ví dụ, mỗi đồ thị vẽ ở Hình 1.9 là liên thông, còn đồ thị vẽ ở Hình 1.11 là không liên thông (gồm ba thành phần liên thông). 10 Một đồ thị vô hướng không có chu trình gọi là một rừng. Một rừng liên thông gọi là một cây, tức cây là một đồ thị liên thông và không có chu trình. Ví dụ phả hệ của một họ tộc là một cây (cây phả hệ). Rừng có thể gồm nhiều thành phần liên thông khác nhau, mỗi thành phần liên thông là một cây. Như vậy, rừng gồm nhiều cây. Đỉnh có bậc 1 trong cây gọi là một lá. Đồ thị hình sao là một cây có duy nhất một đỉnh không phải là lá. (a) Rừng (không liên thông) (b) Cây (liên thông) (c) Đồ thị hình sao Hình 1.11: Ví dụ về rừng và cây Một đồ thị con, không chứa chu trình của đồ thị G gọi là một cây của G. Một đồ thị con bao trùm của G mà là một cây được gọi là một cây bao chùm của G. Một số tính chất đặc trưng của cây: cây n đỉnh có đúng n − 1 cạnh, trong một cây, bao giờ cũng có một đường đi duy nhất nối một cặp đỉnh bất kỳ của cây, khi thêm vào cây một cạnh bất kỳ khác sẽ tạo nên một chu trình duy nhất . . . Đồ thị đầy đủ. Một đơn đồ thị trong đó mọi cặp đỉnh (khác nhau) đều kề nhau, gọi là một đồ thị đầy đủ. Đồ thị đầy đủ n đỉnh ký hiệu là Kn . Số cạnh của Kn bằng n(n − 1)/2. Đồ thị K4 và K5 được vẽ ở Hình 1.12. Đồ thị hai phần. Nếu tập đỉnh của một đồ thị G có thể được chia tách ra thành hai tập rời nhau A và B sao cho mỗi cạnh của G nối một đỉnh thuộc A với một đỉnh thuộc B, thì G được gọi là một đồ thị hai phần (Hình 1.13). 11 Hình 1.12: Đồ thị đầy đủ K4 và K5 Hình 1.13: Đồ thị hai phần Có thể chứng minh rằng đơn đồ thị G là đồ thị hai phần khi và chỉ khi mọi chu trình trong G đều có độ dài (số cạnh) chẵn. Đồ thị hai phần đầy đủ là một đồ thị hai phần mà mỗi đỉnh trong A được nối với mỗi đỉnh trong B bằng đúng một cạnh. Ký hiệu đồ thị hai phần là Kr,s , trong đó r = |A| và s = |B|. Các đồ thị K1,3 , K2,3 , K3,3 và K4,3 được vẽ ở Hình 1.14. Hình 1.14: Đồ thị hai phần đầy đủ: K1,3 , K2,3 , K3,3 , K4,3 12 Đồ thị phẳng. Một đồ thị (hay đa đồ thị) G gọi là đồ thị phẳng khi G có thể biểu diễn được trên một mặt phẳng sao cho ứng với mỗi đỉnh là một điểm và ứng với mỗi cạnh là một đoạn thẳng hay cong và bất kỳ hai cạnh nào cũng không có điểm chung khác với các đầu mút của chúng. Đồ thị đã vẽ ở Hình 1.4 và Hình 1.4 là các đồ thị phẳng. Khi đó, mỗi miền mặt phẳng hạn định bởi các cạnh và không chứa đỉnh hoặc cạnh ở bên trong nó, gọi là một diện của đồ thị phẳng G. Biên của một diện là chu trình tạo nên bởi các cạnh hạn định nó. Hai diện gọi là kề nhau khi nào biên của chúng có ít nhất một cạnh chung. Rõ ràng mỗi đồ thị phẳng liên thông đều có một diện vô hạn duy nhất, còn mọi diện khác đều là diện hữu hạn. Lưu ý, đồ thị K5 (Hình 1.12) và K3,3 (Hình 1.14) là hai đồ thị không phẳng và người ta chứng minh được rằng một đồ thị là phẳng khi và chỉ khi nó không chứa đồ thị con nào thuộc kiểu K5 hay K3,3 (Định lý Kuratowski). 1.2 Mạng và luồng Trong nhiều ứng dụng ta thường quan tâm tới các mạng, tức là các đồ thị mà trên các cạnh hay cung của nó có các lượng vật chất di chuyển. Chẳng hạn, mạng lưới giao thông, mạng thông tin liên lạc, mạng phân phối điện, mạng ống dẫn dầu, mạng cấp nước thành phố . . . Có thể hiểu mạng là một đồ thị liên thông (vô hướng hay có hướng) mà trên mỗi cạnh hay cung của đồ thị có gắn một số không âm, gọi là năng lực lưu thông của cạnh hay cung đó. Năng lực lưu thông của cạnh hay cung cho biết lượng vật chất tối đa có thể di chuyển trên cạnh hay cung đó (tấn/giờ đối với mạng ống dẫn dầu, m3 /phút đối với mạng cấp nước thành phố, xung/giây đối với mạng thông tin liên lạc, số xe/giờ đối với mạng giao thông thành phố). Các đỉnh trong mạng có thể biểu diễn các kho chứa hàng, các đài tiếp âm, các nút giao thông hay các trạm bơm. . . 13 Nếu không có hạn chế đối với lượng vật chất di chuyển từ đỉnh i tới đỉnh j trong mạng thì năng lực lưu thông di j đặt bằng một số khá lớn, ký hiệu Gz. Còn nếu không có cạnh hay cung nối hai đỉnh i và j thì đặt năng lực lưu thông di j = 0. Ma trận vuông cấp n × n lập nên từ các hệ số năng lực lưu thông của các cạnh hay cung trong mạng gọi là ma trận năng lực lưu thông của mạng. Nếu cho phép di chuyển theo cả hai chiều giữa một cặp đỉnh (như đường hai chiều trong thành phố) thì các đỉnh này được nối liền bằng hai cung, mỗi cung đi theo một hướng và mỗi cung có một năng lực lưu thông riêng (có thể khác nhau). Như vậy, một cạnh vô hướng có thể xem như hai cung ngược chiều nhau (giống như đường hai chiều được xem như đường một chiều có dải phân cách ở giữa). 1.3 Một số bài toán tối ưu trên đồ thị 1.3.1 Ghép cặp, phủ cạnh, phủ đỉnh, tập ổn định và clique ◦ Một ghép cặp trong đơn đồ thị vô hướng G là tập cạnh M ⊆ E(G) sao cho từng đôi một rời nhau (không có đỉnh chung), nghĩa là tất cả các đầu mút của chúng đều khác nhau. Ghép cặp gọi là cực đại nếu nó có nhiều cạnh nhất và gọi là hoàn hảo nếu nó phủ hết mọi đỉnh của đồ thị. ◦ Một phủ cạnh trong đồ thị G là tập cạnh F ⊆ E(G) sao cho mỗi đỉnh của G liên thuộc ít nhất một cạnh trong F, nghĩa là mỗi đỉnh là đầu mút của cạnh nào đó trong F (thực ra phủ cạnh là dùng cạnh để phủ đỉnh). ◦ Một phủ đỉnh trong đồ thị G là tập đỉnh S ⊆ V (G) sao cho mỗi cạnh của G liên thuộc ít nhất một đỉnh trong S, nghĩa là mỗi cạnh có ít nhất một đầu mút thuộc S (thực ra nên hiểu phủ đỉnh là dùng đỉnh để phủ cạnh). ◦ Tập ổn định trong G là một tập đỉnh mà từng đôi một không kề nhau. ◦ Clique là một tập đỉnh mà từng đôi một kề nhau (ngược với tập ổn định).