TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI KHOA TOÁN NGUYỄN THỊ THANH THỦY TÌM HIỂU VỀ LÝ THUYẾT MATROID KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Toán Ứng Dụng Người hướng dẫn khoa học: TS TRẦN MINH TƯỚC Xuân Hòa - 2015 LỜI CAM ĐOAN Tôi thực đề tài Tìm hiểu lý thuyết Matroid Tôi xin cam đoan công trình nghiên cứu riêng Kết nghiên cứu đề tài đảm bảo tính khách quan, trung thực, không trùng lặp với tác giả khác Hà Nội, tháng năm 2015 Sinh viên Nguyễn Thị Thanh Thủy LỜI CẢM ƠN Trước trình bày nội dung khóa luận tốt nghiệp, em xin bày tỏ lòng biết ơn sâu sắc tới Tiến sĩ Trần Minh Tước người tận tình hướng dẫn để em hoàn thành đề tài Em xin bày tỏ lòng biết ơn chân thành tới toàn thể thầy cô giáo khoa Toán, Trường Đại học Sư phạm Hà Nội dạy bảo em tận tình suốt trình học tập khoa Nhân dịp em xin gửi lời cảm ơn chân thành tới gia đình, bạn bè bên em, động viên, giúp đỡ em suốt trình học tập thực đề tài Hà Nội, tháng năm 2015 Sinh viên Nguyễn Thị Thanh Thủy Mục lục Chương KHÁI NIỆM MATROID VÀ HỆ THỐNG TIÊN ĐỀ 1.1 Khái niệm matroid 1.2 Tiên đề sở 1.3 Tiên đề hạng 1.4 Tiên đề vòng Chương SỰ LIÊN HỆ GIỮA MATROID VÀ LÝ THUYẾT ĐỒ THỊ 12 2.1 Matroid vòng đồ thị 13 2.2 Matroid đối ngẫu 18 2.2.1 Đồ thị đối ngẫu 2.2.2 Maroid đối ngẫu 18 19 Chương SỰ LIÊN HỆ GIỮA MATROID VỚI TRANSVERSAL 20 3.1 Khái niệm transversal 20 3.2 Sự liên hệ matroid với transversal 21 Chương SỰ LIÊN HỆ GIỮA MATROID VÀ TỐI ƯU TỔ HỢP 23 4.1 Thuật toán tham lam 23 4.2 Ví dụ 24 MỞ ĐẦU 1.Lí chọn đề tài Lý thuyết Matroid dạng đại hình học đề cập lần nhà toán học Bill Tutte Lý thuyết Matroid lý thuyết tập hợp với cấu trúc độc lập xác định chúng Như vậy, theo lý thuyết chung, nghiên cứu đối tượng (hình thức) mối quan hệ với đối tượng khác dựa cấu trúc Lý thuyết Matroid tổng quát hóa tính chất độc lập tuyến tính, phụ thuộc tuyến tính không gian vector nhiều ứng dụng lý thuyết đồ thị, tổ hợp Hơn nữa, sau người ta thấy Matroid có ý nghĩa với Toán học đại Mục đích nhiệm vụ nghiên cứu Bước đầu tiếp cận để tìm hiểu Lý thuyết Matroid Phương pháp nghiên cứu Nghiên cứu Lý thuyết, vận dụng phép suy luận logic để tìm cách chứng minh số định lý, tính chất chưa trình bày Phạm vi nghiên cứu Khái niệm Matroid, liên hệ Matroid với lý thuyết đồ thị, transvertion, tối ưu tổ hợp hạn chế tài liệu thu thập Bố cục Bố cục khóa luận bao gồm : Mở đầu Chương 1: Khái niệm Matroid hệ thống tiên đề Chương 2: Sự liên hệ Matroid với lý thuyết đồ thị Chương 3: Sự liên hệ Matrid với transversal Chương 4: Sự liên hệ Matroid với tối ưu tổ hợp Kết luận Do thời gian thực đề tài không nhiều, kiến thức hạn chế nên khóa luận không tránh khỏi thiếu sót Tác giả mong nhận góp ý ý kiến phản biện thầy cô bạn đọc Xin chân thành cảm ơn! Chương KHÁI NIỆM MATROID VÀ HỆ THỐNG TIÊN ĐỀ 1.1 Khái niệm matroid Đầu tiên ta tìm hiểu matroid gì? Khái niệm đưa sau dựa tập độc lập tập S với số ví dụ giúp ta có hình dung Matroid Ngoài ta định nghĩa Matroid khái niệm tương đương dựa tập sở, tập vòng hay hàm hạng được trình bày mục sau Định nghĩa 1.1.1 Matroid cặp M gồm tập hữu hạn S họ F tập S gọi tập độc lập M thỏa mãn điều kiện sau: M(1i) 0/ ∈ F M(2i) Nếu X ∈ F Y ⊆ X Y ∈ F M(3i) Nếu U,V ∈ F |U| > |V | tồn phần tử x ∈ U −V cho (V ∪ {x}) ∈ F Sau ta xét số ví dụ minh họa Ví dụ 1.1.1 Cho ma trận với nhãn tương ứng: 2   0 0 1  0  1 0 1 Ký hiệu E = {1, 2, 3, 4, 5, 6, 7} tập vector cột xác định nhãn chúng Giả sử F họ tập số I ⊆ E cho tập vector cột gãn nhãn I độc lập tuyến tính Khi F gồm tập E − {7} có nhiều ba phần tử loại trừ {1, 2, 4}, {2, 3, 5}, {2, 3, 6} loại tập chứa {5, 6} Ta (E, F) matroid Tính chất "độc lập" phần tử tính chất độc lập tuyến tính hệ vector cột ma trận cho Ví dụ 1.1.2 Xét đồ thị G cho hình vẽ Hình 1.1: Đồ Thị G Xét họ F tập cạnh G mà không chứa chu trình G Như vậy, tập F không chứa tập tập sau: {7}, {5, 6}, {1, 2, 4}, {2, 3, 5}, {1, 3, 4, 5}, {1, 3, 4, 6} Khi đó, E(G) với họ F xác định lập thành matroid G Tính độc lập phần tử xác định tính chất không chứa chu trình tập cạnh Matroid xác định gọi matroid vòng G Ví dụ 1.1.3 Cho tập S hữu hạn phần tử Xét họ F1 = {0} / ta có (S, F1 ) matroid gọi matroid tầm thường Xét họ F2 = P(S) = 2S ta chứng minh (S, F2 ) matroid gọi matroid rời rạc Trên khái niệm matroid định nghĩa dựa tính độc lập phần tử Người ta định nghĩa matroid với cách khác, tất nhiên chúng tương đương Sau ta tìm hiểu điều thông qua tiên đề 1.2 Tiên đề sở Cho matroid M = (S, F) Xét họ không rỗng B có phần tử tập độc lập lớn S M Vì phần tử B tập độc lập nên B họ tập độc lập M Bổ đề 1.2.1 Nếu B1 , B2 sở matroid M |B1 | = |B2 | Chứng minh Cho B1 , B2 hai sở M, |B1 | < |B2 | Vì B1 B2 hai tập độc lập nên thỏa mãn điều kiện M(3i), tồn phần tử e ∈ (B2 − B1 ) cho (B1 ∪ e) ∈ F Như B1 tập độc lập lớn nhất, mâu thuẫn với B1 sở, suy giả sử sai Vì |B1 | ≥ |B2 | Đổi vai trò B1 B2 , tương tự ta chứng minh |B2 | ≥ |B1 | Suy |B1 | = |B2 | Định lý 1.2.1 Họ khác rỗng tập hữu hạn S, kí hiệu B họ sở matroid S thỏa mãn điều kiện sau: B(1i) ∀B1 , B2 ∈ B, B1 B2 B2 B1 B(2i) Nếu B1 , B2 ∈ B x1 ∈ (B1 − B2 ) tồn y ∈ B2 − B1 cho (B1 ∪ {y}) − {x} ∈ B Chứng minh Ta chứng minh họ B xác định thỏa mãn hai điều kiện B(1i), B(2i) định lý 1.2.1 Xét B1 , B2 ∈ B, B1 = B2 , mà theo bổ đề 1.2.1 ta có số phần tử sở |B1 | = |B2 |, hiển nhiên B(1i) thỏa mãn Cho B1 − x B2 hai tập độc lập, |B1 − x| < |B2 | Theo điều kiện M(3i), ∃y ∈ (B2 − (B1 − x)) cho ((B1 − x) ∪ y) ∈ F Hiển nhiên y ∈ (B2 − B1 ) Đặt B3 = (B1 − x) ∪ y Theo bổ đề 1.2.1 ta có |B3 | = |(B1 − x) ∪ y| = |B1 | Hơn nữa, (B1 − x) ∪ y tập độc lập, suy B3 sở M Vậy B(2i) thỏa mãn Bây ta chứng minh họ B tập S matroid theo định nghĩa 1.1.1 Cho I = {I ⊆ B|B ∈ B} Ta chứng minh (S, I) matroid Từ B thỏa mãn B(1i) nên I thỏa mãn M(1i) Nếu I ∈ I, I ⊆ I ⇒ I ⊂ B, B ∈ B, thỏa mãn M(2i) Cho I1 , I2 ∈ I với |I1 | < |I2 | cho ∀e ∈ I2 − I1 , I1 ∪ e ∈ / I Theo định nghĩa, B có chứa phần tử B1 , B2 Như vậy, I1 ⊆ B1 I2 ⊆ B2 Cho tập B2 chọn cho |B2 − (I2 ⊆ B1 )| nhỏ Bởi ta chọn I1 , I2 để I2 − B1 = I2 − I1 (1) Giả sử B2 − (I2 ∪ B1 ) khác rỗng Khi đó, ta chọn phần tử x từ tập này, theo B(2i), có phần tử y ∈ B1 − B2 cho (B2 − x) ∪ y ∈ B Nhưng sau |((B2 − x) ∪ y) − (I2 ∪ B1 )| < |B2 − (I2 ∪ B1 )| việc chọn B2 mâu thuẫn, nên B2 − (I2 ∪ B1 ) rỗng B2 − B1 = I2 − B1 Mà theo (1)I1 = B1 nên B2 − B1 = I2 − I1 (2) Tiếp theo ta chứng minh B1 − (I1 ∪ B2 ) rỗng Giả sử B1 − (I1 ∪ B2 ) không rỗng, có x ∈ B1 − (I1 ∪ B2 ) y ∈ B2 − B1 cho (B1 − x) ∪ y ∈ B Bây (I1 ∪ y) ⊆ ((B1 − x) ∪ y) nên I1 ∪ y ∈ I Từ y ∈ (B2 − B1 ), theo (2), y ∈ (I2 − I1 ), mâu thuẫn với điều giả sử Suy B1 − (I1 ∪ B2 ) rỗng Vì B1 − B2 = I1 − B2 B1 − B2 ⊆ I1 − I2 (3) Mà |B1 | = |B2 | nên |B1 − B2 | = |B2 − B1 |, kết hợp với (1), (2), (3) ta có |I1 − I2 | ≥ |I2 − I1 | ⇔ |I1 | ≥ |I2 |, mâu thuẫn với giả thuyết |I1 | < |I2 | ⇒ (S, I) matroid Ví dụ 1.2.1 Cho ma trận A ma trận 5x8 có cột vecter R5 Tập vecter cột A {1, 2, 3, 4, 5, 6, 7, 8} 5   0  0   0 1 0 1 0 0 1 0 1 0 1 0 1   0  0   1 Cơ sở matroid tập độc lập tuyến tính tối đại không gian vector cột Xét hai sở matroid           1                 1 0 1 0              B1 =  0,1,0,0              0 0 1 1       0          0                  1 1 0 0              B2 =  0,1,1,0              0 0 1 1      0  Thay vector thứ B1 vecter thứ B2 sở B3          0                  1 1 1 0              B3  0,1,0,0              0 0 1 1      1  Trong trường hợp ta thấy tính chất B(2i), thỏa mãn.Và điều chứng tỏ sở chứa sở khác Một cách mô tả khác khái niệm matroid nhờ vào hàm hạng 1.3 Tiên đề hạng Cho M = (S, F) họ tất tập S 2S Tính chất 2.1.2 Nếu G liên thông r(M(G)) = |V (G) − 1| (bằng số cạnh khung) Chứng minh Hàm hạng tập A số phần tử tập độc lập lớn A Theo tính chất 2.1.1, ta có khung G sở M(G) tập độc lập lớn Vậy r(M(G)) số cạnh khung Từ tính chất này, hiển nhiên ta có hệ sau Hệ 2.1.2 Khi G không liên thông, r(M(G)) = |V (G) − k(G)| với k(G) số thành phần liên thông đồ thị G Với X ⊆ E(G), X đồ thị độc lập thỏa mãn tính chất Từ hiển nhiên ta có tính chất Tính chất 2.1.3 ∀X ⊆ E(G), r(X) = |V (X)| − k(X) với k(X) số thành phần liên thông X Ví dụ 2.1.1 Cho đồ thị K hình vẽ: Hình 2.1: Đồ Thị K Theo tính chất 2.1.1 ta có tập sở đồ thị gồm: {a, b, c, d, e} , {a, b, c, d, f }, {b, c, d, e, f } , {a, c, d, e, f } {a, b, d, e, f } , {a, b, c, e, f }, {a, b, c, d, g} , {a, b, c, g, e} {a, f , e, d, g} , {a, f , g, e, c}, {c, d, g, f , a} , {b, c, d, g, f } {b, g, f , e, d} , {b, c, g, f , e} Theo tính chất 2.1.2 ta có: 14 r(M(G)) = |V (G)| − = − = Ví dụ 2.1.2 Trong hình 1.2, ta thấy sở đồ thị H là: {a, b, c, d}, {a, e, d, c}, {b, c, d, e} {b, a, e, d}, {c, b, a, e}, {c, b, f , e} {c, d, f , a}, {c, g, a, e}, {c, g, f , e} Quan sát danh sách ta thấy điều kiện B(1i) thỏa mãn sở chứa sở khác Ta chứng minh điều kiện B(2i) việc xét hai sở Nếu ta chọn B1 = {a, b, c, d} B2 = {c, g, a, e}, ta thấy khung B1 B2 hình 2.2 hình 2.3 Hình 2.2: Cây khung B1 Hình 2.3: Cây khung B2 15 Ta thấy, khung đồ thị G có đỉnh cạnh Chúng ta chứng minh B(2i) cách thay cạnh a B1 cạnh e B2 cho B3 sở B3 = B1 − {a} ∪ {e} Hình 2.4: Cây khung B3 Làm tương tự với sở ta thấy B(2i) thỏa mãn Ta xem xét ví dụ sau để thấy rõ hạng matroid lý thuyết đồ thị Ví dụ 2.1.3 Cho đa đồ thị P với tập cạnh E (đồ thị có khuyên a) Xét matroid vòng M(G) tập cạnh E Hình 2.5: Đồ thị G Ta tính hạng số tập cạnh G Xét A cho hình 2.6 đồ thị liên thông không chu trình G (là tập độc lập M(G)) Vì A tập độc lập M(G) nên r(A) = |A| = = − Xét B cho hình 2,7 đồ thị liên thông chu trình G Hạng B tập có số phần tử lớn B mà không chứa vòng {b, c, d}, {b, c, e}, {b, e, d}, có phần tử B có đỉnh, r(B) = = − 16 Hình 2.6: Đồ thị A G Hình 2.7: Đồ thị B G Hình 2.8: Đồ thị C G Xét C cho hình 2.8 đồ thị có khuyên G r(C) = = − Hình 2.9: Đồ thị D G Xét D cho hình 2.9 đồ thị G D có hai đỉnh hai cạnh, r(D) = = − 17 2.2 Matroid đối ngẫu 2.2.1 Đồ thị đối ngẫu Cho đồ thị phẳng G Xây dựng đồ thị đối ngẫu G* G sau Mỗi đỉnh G* biểu diễn miền đồ thị phẳng G Với cạnh e G, e nằm ranh giới hai miền G* có cạnh nối hai đỉnh G* biểu diễn hai miền gán cho nhãn e Nếu e nằm miền G* khuyên đỉnh tương ứng G* gán cho nhãn e Ví dụ 2.2.1 Xây dựng đối ngẫu G* đồ thị G cho Hình 1.1 Đồ thị G Đồ thị G* Hình 2.1: Đồ thị G* đối ngẫu đồ thị G Họ chu trình đồ thị G* họ vòng matroid M(G*) : {{1, 4} , {1, 2, 3} , {2, 3, 4} , {3, 5, 6} , {1, 2, 5, 6} , {2, 4, 5, 6}} Mỗi vòng G*, loại cạnh tương ứng G đồ thị G bị chia thành hai phần Một tập cạnh gọi lát cắt đồ thị G Từ ví dụ ta thấy lát cắt đồ thị G vòng M(G) 18 2.2.2 Maroid đối ngẫu Định lý 2.2.1 Cho M = (S, B) matroid S định nghĩa theo tiên đề sở Xét họ B∗ xác định B∗ = {S − B|B ∈ B} Khi họ B* thiết lập matroid M ∗ = {S, B∗ } S Chứng minh Sau ta chứng minh M ∗ = (S, B∗ ) matroid Ta có ∀B1 , B2 ∈ B, B1 B2 B2 B1 , nên ∀e ∈ B1 , e ∈ / B2 Với B∗1 = S − B1 , B∗2 = S − B2 , ta suy e ∈ / B∗1 , e ∈ B∗2 Vậy thỏa mãn điền kiện B(1i) Cho B∗1 , B∗2 ∈ B∗ (M) Với j = 1, 2, cho B j = S − B∗ Khi B j ∈ B(M) B∗1 − B∗2 = B2 − B1 Theo B(2i), x ∈ B2 − B1 ∃y ∈ B1 − B2 cho (B1 − y ∪ x) ∈ B(M) Theo mà y ∈ B∗2 − B∗1 S(M) − ((B1 − y) ∪ y) ∈ B∗ (M) Nhưng S(M) − ((B1 − y) ∪ x) = ((S(M) − B1 − x) ∪ y = (B∗1 − x) ∪ y) Suy B∗ (M) thỏa mãn B(2i) Vậy B∗ (M) sở matroid S hay M ∗ = {S, B∗ } matroid Matroid định lý 2.2.1 S(M) họ sở B∗ (M) gọi đối ngẫu M Như B(M ∗ ) = B∗ (M) Sự liên hệ M M* nói đến định lý sau Định lý 2.2.2 Trên tập S ta có (M ∗ )∗ = M Matroid đối ngẫu cho ta thấy quan hệ rõ matroid đồ thị Xét đồ thị G = (V, E), tập cạnh B ⊆ E gọi lát cắt đồ thị G đồ thị V, E − B có số phần tử liên thông lớn G Người ta chứng minh rằng, họ tất lát cắt cực tiểu đồ thị G tạo nên họ vòng (tập phụ thuộc nhỏ nhất) matroid E(G) Kí hiệu M ∗ (G) Định lý sau cho ta thấy liên hệ đặc biệt Định lý 2.2.3 Với đồ thị G = (V, E), ta có M ∗ (G) = (M(G))∗ , M(G) matroid vòng G, M ∗ (G) matroid với lát cắt cực tiểu đồ thị G Chứng minh Ta có M(G) matroid vòng G hay M(G) = (E(G), C∗ ) C∗ tập không chứa vòng G (M(G))∗ = (E(G∗ ), C), C tập chứa vòng G* Mà vòng G* lát cắt cực tiểu G matroid với lát cắt cực tiểu G Suy (M(G))∗ = M ∗ (G) 19 Chương SỰ LIÊN HỆ GIỮA MATROID VỚI TRANSVERSAL 3.1 Khái niệm transversal Ở chương ta xem xét kết toán thực tế có tên "đám cưới vùng quê" Bài toán đám cưới vùng quê phát biểu sau: có m chàng trai đến tuổi lấy vợ, với chàng trai i, ta biết tập Si cô gái mà chàng trai thích Hỏi ghép cô cho chàng mà chàng vừa ý hay không? Nếu có cách ghép đôi thỏa mãn toán ta gọi kết hệ đại diện phân biệt hay transversal Sau ta tìm hiểu rõ cấu trúc transversal Định nghĩa 3.1.1 Cho A họ {A1 , A2 , , Am } tập tập E hữu hạn Một tập {x1 , x2 , , xk } E transversal phận A tương ứng một từ tập {1, 2, , k} đến tập {1, 2, , m} cho xi ∈ Ai ∀i Với k = m transversal phận gọi transversal Ví dụ 3.1.1 Xét tập E = {1, 2, 3, 4, 5, 6, 7} Cho A = ({1, 2, 4} , {2, 3, 5, 6} , {5, 6} , {7}) có {2, 3, 6, 7} transversal 2, 3, 6, thuộc A1 , A2 , A3 , A4 20 A biểu diễn đồ thị hai phía với đỉnh bên trái biểu diễn cho phần tử thuộc E, đỉnh bên phải biểu diễn cho phần tử thuộc A, gọi đồ thị T (A) Gọi A đồ thị biểu diễn transversal A (a) (b) Hình 3.1: (a) Đồ thị T (A), (b) đồ thị A 3.2 Sự liên hệ matroid với transversal Định lý 3.2.1 Cho A họ tập E hữu hạn Cho I họ tất transversal phận A Khi (E, I) matroid Chứng minh Rõ ràng tập transversal phận transversal phận, nên điều kiện M(2i) thỏa mãn Tập 0/ transversal họ rỗng tập A nên điều kiện M(1i) thỏa mãn Ta xây dựng đồ thị hai phía A sau: Gán nhãn cho lớp đỉnh đồ thị phần tử E lớp đỉnh tập A1 , A2 , , Am A Đặt cạnh từ phần tử e ∈ E đến phần tử A j đại diện cho A j phần tử thuộc A Cho X Y hai transversal phận phần tử A |X| = |Y | + Ta xét đồ thị hai phía A hai tập X, Y Các cạnh đại diện cho tập X tô màu xanh đại diện cho tập Y tô màu đỏ, cách cạnh giống coi vừa màu xanh màu đỏ Như ta có |X −Y | cạnh màu xanh |Y - X| cạnh màu đỏ 21 |X −Y | = |Y − X| + Vì A đồ thị hai phía đỉnh thuộc lớp gán nhãn phần tử E đại diện cho phần tử A Nên đỉnh có nhãn phần tử E bậc có cạnh màu xanh cạnh màu đỏ Tương tự lớp đỉnh có nhãn tập E Như thành phần liên thông A có cạnh xen kẽ màu Suy thành phần liên thông A vòng có số cạnh màu xanh đỏ Vậy hiển nhiên có đường H có n cạnh màu xanh n − cạnh màu đỏ, nên đường phải bắt đầu màu xanh kết thúc màu xanh Đổi màu cạnh H có n − cạnh màu đỏ n cạnh màu xanh Lúc A có số cạnh màu đỏ |X| |Y | + Thực ta thêm phần tử vào tập Y làm thay đổi n − cạnh Y Cụ thể H đỉnh gán nhãn phần tử thuộc E nối với đỉnh khác gán nhãn phần tử A việc đổi màu Và ban đầu cạnh màu xanh H đảm bảo tương ứng một thể đại diện transversal nên sau đổi màu ta thu cạnh màu đỏ giữ nguyên tính chất Như Y ∪ {x} tranversal Điều kiện M(3i) thỏa mãn Ta định nghĩa matroid định lý matroid transversal I họ transversal E Ví dụ 3.2.1 Cho đồ thị G Hình 3.1: Đồ thị G Vòng matroid M(G) transversal M(G1 ) = M(A) A = {{1, 2, 7} , {3, 4, 7} , {5, 6, 7}} 22 Chương SỰ LIÊN HỆ GIỮA MATROID VÀ TỐI ƯU TỔ HỢP Ở chương ta xem xét thuật toán tham lam thực matroid trọng số 4.1 Thuật toán tham lam Thuật toán tham lam nhận đầu vào matroid M = (S, T) với hàm trọng số dương từ T vào R+ trả tập tối ưu A Trong thuật toán ta biểu diễn thành phần M S[M] T[M] hàm trọng số ω Thuật toán gọi tham lam chọn phương án tốt bước, xem phần tử x ∈ S xếp theo trọng số giảm dần trực tiếp cộng vào A A ∪ {x} độc lập Thuật toán A ←− / Sắp xếp S[M] theo thứ tự giảm dần trọng số ω for x ∈ S[M] lấy vị trí từ tập xếp giảm dần theo trọng số if A ∪ {x} ∈ t[M] 23 A ←− A ∪ {x} Đưa kết A Những phần tử thuộc S xếp theo thứ tự giảm dần theo trọng số Nếu phần tử x xét thêm vào A mà A độc lập chọn x Vì tập 0/ độc lập theo định nghĩa matroid x thêm vào A với điều kiện A ∪ {x} độc lập, nên tập A độc lập theo quy nạp Vì thuật toán cho kết tập độc lập chọn cạnh có trọng số lớn thỏa mãn qua bước, nên A nhận tập độc lập có tổng trọng số lớn nhất.Sau ta chứng minh thuật toán trả tập tối ưu qua định lý sau Định lý 4.1.1 Giả sử M = (S,t) matroid trọng số với hàm trọng số ω S xếp theo thứ tự giảm dần trọng số Cho x phần tử S cho {x} tập độc lập Nếu x tồn tồn tập tối ưu A S chứa x Chứng minh Nếu không tồn x tập độc lập tập rỗng Nói cách khác, cho B tập tối ưu khác rỗng Giả sử x ∈ / B cho A = B Không có phần tử B có trọng số lớn ω(x) Để thấy điều này, ta có y ∈ B, dẫn đến {y} độc lập Mặt khác x không thỏa mãn B ∪ x tập độc lập nên với y ∈ B Xây dựng tập A sau, bắt đầu với A = {x} Do cách chọn nên A độc lập Áp dụng tính chất trao đổi, lặp lại việc tìm phần tử B để thêm vào A cho A độc lập, |A| = |B| A độc lập Lúc A = B − {y} ∪ {x} ∀y ∈ B Suy ω(A) = ω(B) − ω(y) + ω(x) ≥ ω(B) Vì A B tối ưu x ∈ A nên định lý chứng minh Ta thấy việc tìm tập độc lập có tổng trọng số nhỏ áp dụng thuật toán tham lam tương tự Sau ta xem xét ví dụ cụ thể thuật toán tham lam 4.2 Ví dụ Ví dụ 4.2.1 Thuật toán Kruskal 24 Xét matroid vòng M(G), S(M) = E(G) T(M) = {X ⊆ E(G), X không chứa chu trình Thuật toán Kruskal xây dựng tập cạnh A khung nhỏ H = (V, A) đồ thị G có n đỉnh theo bước Trước hết xếp cạnh đồ thị G theo thứ tự không giảm độ dài Bắt đầu từ tập A = 0, / bước ta duyệt danh sách cạnh xếp, từ cạnh có độ dài nhỏ đến lớn để tìm cạnh mà việc bổ sung vào tập A không tạo thành chu trình tập Thuật toán kết thúc ta thu tập A có n − cạnh Thuật toán Kruskal begin A := / while |A| < (n − 1) and (E = 0) / begin Chọn e cạnh có độ dài nhỏ E: E := E − {e}; if (A ∪ {e} ∈ T(M)) then A := A ∪ {e}; end; if (|A| < n − 1) then Đồ thị không liên thông; end; Ví dụ 4.2.2 Tìm khung nhỏ đồ thị cho hình sau: Hình 4.1: Đồ thị H 25 Bước Cạnh e A ∪ {e} ∈ T(M) EA ωA e35 thỏa mãn {35} e46 thỏa mãn {35}, {46} 4+8 e45 thỏa mãn {35}, {46}, {45} 4+8+9 e13 thỏa mãn {35}, {46}, {45}, {13} + + + 17 e23 thỏa mãn {35}, {46}, {45}, {13}, {23} + + + 17 + 23 Bảng 4.1: Các bước tìm khung nhỏ A = {(3, 5), (4, 6), (4, 5), (1, 3), (2, 3)} 26 KẾT LUẬN Sau trình thực đề tài này, so với mục đích đề ra, tìm hiểu kiến thức mở đầu cho lĩnh vực Toán học Cụ thể nội dung sau: Khái niệm matroid tiên đề Sự liên hệ matroid lý thuyết đồ thị Sự liên hệ matroid transversal, cụ thể khái niệm transversal matroid transversal Sự liên hệ matroid tối ưu tổ hợp, cụ thể thuật toán tham lam Đối với thân, lần thực đề tài nghiên cứu khoa học thực cảm thấy hút Càng tiếp xúc tìm hiểu sâu thấy muốn tiếp không ngừng suy nghĩ vấn đề chưa hiểu Đối với nội dung nghiên cứu, thấy matroid hình dung đơn giản cấu trúc tổng quát cho loại cấu trúc toán học Cụ thể đề tài thể với cấu trúc tuyến tính cấu trúc rời rạc, nhiều loại mà matroid thể hiệu chưa có điều kiện nghiên cứu sâu Matroid lĩnh vực toán học giới đặc biệt với ngành toán nước ta Matroid chưa giảng dạy trường đại học người tìm hiểu Vì nghiên cứu matroid gặp không khó khăn, tài liệu Tuy nhiên, với khó khăn mẻ đó, mong người có hứng thú nghiên cứu matroid Những bước đầu tiên, ta tìm hiểu sâu mối liên hệ với lý thuyết đồ thị, matroid đối ngẫu, thuật toán ứng dụng tối ưu tổ hợp nhiều hướng khác 27 TÀI LIỆU THAM KHẢO [1] Michel X Goemans (2009), "Combinatorial Optimization", Massachusetts Institute of Technologi [2] James Oxley (1992), Matroid Theory, Oxford University Press, New York [3] James Oxley (2007), "What is a matroid", Department Of Mathematics, Louissiana State University, Baton Rouge, LA, USA [4] R J Wilson (1973), An Introduction To Matroid Theory, The Amecican Mathematical Monthly [5] Nguyễn Đức Nghĩa - Nguyễn Tô Thành (2003), Toán Rời Rạc, NXB Đại Học Quốc Gia Hà Nội [6] Ngô Đắc Tân (2005), Lý Thuyết Tổ Hợp Đồ Thị, NXB Đại Học Quốc Gia Hà Nội 28 [...]... thỏa mãn 11 Chương 2 SỰ LIÊN HỆ GIỮA MATROID VÀ LÝ THUYẾT ĐỒ THỊ Sự liên hệ giữa matroid với lý thuyết đồ thị sẽ cung cấp thêm công cụ mang tính lý thuyết có thể làm sáng tỏ nhiều vấn đề trong lý thuyết đồ thị Tuy nhiên sự thay thế hoàn toàn là không thể Chẳng hạn trong ví dụ sau đây, hai đồ thị Q1 và Q2 là không đẳng cấu nhưng hai matroid vòng M(Q1 ) và M(Q2 ) là hai matroid đẳng cấu Ta nhắc lại, M1 =... sâu Matroid là một lĩnh vực khá mới đối với toán học thế giới và đặc biệt là với ngành toán nước ta Matroid chưa được giảng dạy ở các trường đại học và rất ít người đã tìm hiểu về nó Vì vậy khi nghiên cứu về matroid gặp không ít khó khăn, nhất là về tài liệu Tuy nhiên, với những khó khăn và sự mới mẻ đó, tôi mong rằng mọi người sẽ có hứng thú và nghiên cứu về matroid Những bước đầu tiên, ta có thể tìm. .. hiện đề tài này, so với mục đích đã đề ra, tôi đã tìm hiểu được những kiến thức cơ bản mở đầu cho lĩnh vực mới của Toán học Cụ thể là những nội dung sau: 1 Khái niệm matroid và các tiên đề 2 Sự liên hệ giữa matroid và lý thuyết đồ thị 3 Sự liên hệ giữa matroid và transversal, cụ thể là khái niệm transversal và matroid transversal 4 Sự liên hệ giữa matroid và tối ưu tổ hợp, cụ thể là thuật toán tham... khi ϕ(X) ∈ F2 12 Ở ví dụ trên, chỉ cần xét matroid rời rạc trên E(G1 ) và E( G2 ) hiển nhiên ta thấy M(G1 ) và M(G2 ) là đẳng cấu Sau đây chúng ta sẽ tìm hiểu một số mối liên hệ giữa matroi với lý thuyết đồ thị Các kí hiệu liên quan tới lý thuyết đồ thị nói tới trong chương này được sử dụng theo [5] 2.1 Matroid vòng của đồ thị Cho đồ thị G = (V, E), khái niệm matroid vòng của G, kí hiệu M(G) đã được... thỏa mãn B(2i) Vậy B∗ (M) là cơ sở của matroid trên S hay M ∗ = {S, B∗ } là một matroid Matroid trong định lý 2.2.1 trên nền S(M) và họ cơ sở B∗ (M) được gọi là đối ngẫu của M Như vậy B(M ∗ ) = B∗ (M) Sự liên hệ giữa M và M* được nói đến trong định lý sau đây Định lý 2.2.2 Trên mỗi tập nền S ta luôn có (M ∗ )∗ = M Matroid đối ngẫu cũng cho ta thấy quan hệ rõ hơn giữa matroid và đồ thị Xét đồ thị G = (V,... tiên, ta có thể tìm hiểu sâu hơn về mối liên hệ với lý thuyết đồ thị, matroid đối ngẫu, các thuật toán ứng dụng trong tối ưu tổ hợp và nhiều hướng đi khác 27 TÀI LIỆU THAM KHẢO [1] Michel X Goemans (2009), "Combinatorial Optimization", Massachusetts Institute of Technologi [2] James Oxley (1992), Matroid Theory, Oxford University Press, New York [3] James Oxley (2007), "What is a matroid" , Department... thấy cuốn hút Càng tiếp xúc và tìm hiểu sâu tôi càng thấy muốn đi tiếp và không ngừng suy nghĩ về vấn đề mình chưa hiểu Đối với nội dung nghiên cứu, tôi thấy rằng matroid có thể hình dung đơn giản là một cấu trúc tổng quát cho các loại cấu trúc của toán học Cụ thể trong đề tài này tôi đã thể hiện với cấu trúc tuyến tính và cấu trúc rời rạc, ngoài ra còn nhiều loại nữa mà matroid thể hiện rất hiệu quả... M(3i) được thỏa mãn Ta định nghĩa matroid như trong định lý là matroid transversal khi I là một họ các transversal của E Ví dụ 3.2.1 Cho đồ thị G Hình 3.1: Đồ thị G Vòng của matroid M(G) là transversal M(G1 ) = M(A) A = {{1, 2, 7} , {3, 4, 7} , {5, 6, 7}} 22 Chương 4 SỰ LIÊN HỆ GIỮA MATROID VÀ TỐI ƯU TỔ HỢP Ở chương này ta sẽ xem xét thuật toán tham lam thực hiện trên một matroid trọng số bất kỳ 4.1 Thuật... của đồ thị G tạo nên một họ các vòng (tập phụ thuộc nhỏ nhất) của matroid trên E(G) Kí hiệu là M ∗ (G) Định lý sau sẽ cho ta thấy một sự liên hệ đặc biệt Định lý 2.2.3 Với mọi đồ thị G = (V, E), ta luôn có M ∗ (G) = (M(G))∗ , trong đó M(G) là matroid vòng của G, M ∗ (G) là matroid với lát cắt cực tiểu của đồ thị G Chứng minh Ta có M(G) là matroid vòng của G hay M(G) = (E(G), C∗ ) trong đó C∗ là tập không... thỏa mãn Cho C là họ tập con của S thỏa mãn các điều kiện của định lý 1.4.1, C là họ các tập C với C ⊂ C Như vậy C là tập độc lập, suy ra C ⊆ F Theo định nghĩa 1.1.1 (S, C ) là một matroid Ví dụ 1.4.1 Cho đồ thị H bởi hình vẽ Hình 1.2: Đồ thị H Ta có thể nhìn nhận một vòng là một chu trình trong lý thuyết đồ thị Ta sẽ lấy một vòng trong matroid M, là chu trình của H Tập vòng của đồ thị H gồm: {a, b, ... 1.Lí chọn đề tài Lý thuyết Matroid dạng đại hình học đề cập lần nhà toán học Bill Tutte Lý thuyết Matroid lý thuyết tập hợp với cấu trúc độc lập xác định chúng Như vậy, theo lý thuyết chung, nghiên... tìm hiểu Lý thuyết Matroid Phương pháp nghiên cứu Nghiên cứu Lý thuyết, vận dụng phép suy luận logic để tìm cách chứng minh số định lý, tính chất chưa trình bày Phạm vi nghiên cứu Khái niệm Matroid, ... 11 Chương SỰ LIÊN HỆ GIỮA MATROID VÀ LÝ THUYẾT ĐỒ THỊ Sự liên hệ matroid với lý thuyết đồ thị cung cấp thêm công cụ mang tính lý thuyết làm sáng tỏ nhiều vấn đề lý thuyết đồ thị Tuy nhiên thay