Khoá luận tốt nghiệp toán Tìm hiểu về lý thuyết Matroid

  • Số trang: 31 |
  • Loại file: PDF |
  • Lượt xem: 185 |
  • Lượt tải: 0
tailieuonline

Đã đăng 27372 tài liệu

Mô tả:

TRƯỜNG ĐẠI HỌC s ư PHẠM HÀ NỘI 2 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 M INH TƯỚC Xuân Hòa - 2015 LỜI CAM ĐOAN Tôi đã thực hiện đề tài Tìm hiểu về lý thuyết Matroỉd. Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Kết quả nghiên cứu của đề tài này đảm bảo tính khách quan, trung thực, không trùng lặp với các tác giả khác. Hà Nội, tháng 5 năm 2015 Sinh viên Nguyễn Thi T hanh Thủy 1 LỜI CẢM ƠN Trước khi trình bày nội dung chính của 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 M inh Tước người đã tận tình hướng dẫn để em có thể hoàn thành đề tài này. Em cũng xin bày tỏ lòng biết ơn chân thành tới toàn thể các thầy cô giáo trong khoa Toán, Trường Đại học Sư phạm Hà Nội 2 đã dạy bảo em tận tình trong suốt quá trình học tập tại khoa. Nhân dịp này em cũng xin được gửi lời cảm ơn chân thành tới gia đình, bạn bè đã luôn bên em, động viên, giúp đỡ em trong suốt quá trình học tập và thực hiện đề tài này. Hà Nội, tháng 5 năm 2015 Sinh viên Nguyễn Thị T hanh Thủy 2 Mục lục Chương 1. KHÁI NIỆM MATROID VÀ HỆ T H ố N G TIÊN ĐE 2 1.1. K hái niệm m atroỉd 2 V 9 1.2. Tiên đê cơ sở 4 1.3. Tiên đề hạng 6 1.4. Tiên đề vòng 9 Chương 2. S ự LIÊN HỆ GIỮA MATROID VÀ LÝ THUYET Đ ồ TH Ị 12 2.1. M atroid vòng của đồ thị 13 2.2. M atroid đối ngẫu 18 2 .2 . 1. Đ ồ thị đối ngẫu 18 2.2.2. M aroid đối ngẫu 19 Chương 3. 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ệ giữa m atroid vối transversal 21 Chương 4. Sự LIÊN HỆ GIỮA MATROID VÀ T ố i Ưu T ổ HỢ P 23 4.1. T huật toán tham lam 23 4.2. V íd ụ l........................... 24 3 MỞ ĐẦU 1.Lí do chọn đề tài Lý thuyết Matroid là một dạng hiện đại của hình học được đề cập lần đầu tiên bởi nhà toán học Bill Tutte. Lý thuyết Matroid là lý thuyết về tập hợp với cấu trúc độc lập xác định trên chúng. Như vậy, vẫn theo lý thuyết chung, nghiên cứu những đối tượng (hình thức) trong mối quan hệ với các đối tượng khác dựa trên một cấu trúc nào đó. Lý thuyết Matroỉd đã tổng quát hóa được những tính chất về sự độc lập tuyến tính, phụ thuộc tuyến tính trong không gian vector và còn nhiều ứng dụng đối với lý thuyết đồ thị, tổ hợp. Hơn nữa, càng về sau người ta càng thấy Matroid có ý nghĩa với Toán học hiện đại. 2. M ục đích và nhiệm vụ nghiên cứu Bước đầu tiếp cận để tìm hiểu về Lý thuyết Matroid. 3. Phương pháp nghiên cứu Nghiên cứu Lý thuyết, vận dụng các phép suy luận logic để tìm cách chứng minh một số định lý, tính chất chưa được trình bày. 4. Phạm vi nghiên cứu Khái niệm Matroid, sự liên hệ giữa Matroid với lý thuyết đồ thị, transvertion, tối ưu tổ hợp hạn chế trong các tài liệu thu thập được. 5. Bố cục Bố cục của khóa luận bao gồm : Mỏ đầu. Chương 1: Khái niệm Matroid và hệ thống tiên đề. Chương 2: Sự liên hệ giữa Matroid với lý thuyết đồ thị. Chương 3: Sự liên hệ giữa Matrid với transversal. Chương 4: Sự liên hệ giữa Matroid với tối ưu tổ hợp. Kết luận. Do thời gian thực hiện đề tài không nhiều, kiến thức còn hạn chế nên khóa luận không tránh khỏi những thiếu sót. Tác giả mong nhận được sự góp ý và những ý kiến phản biện của thầy cô và bạn đọc. Xin chân thành cám ơn! Chương 1 KHÁI NIỆM MATROID VÀ HÊ THỐNG TIÊN ĐỀ 1.1. Khái niệm matroid Đầu tiên ta sẽ tìm hiểu matroid là gì? Khái niệm được đưa ra sau đây dựa trên các tập con độc lập của tập nền s cùng với một số ví dụ giúp ta có hình dung đầu tiên về Matroid. Ngoài ra ta có thể định nghĩa Matroid bằng các khái niệm tương đương dựa trên tập cơ sở, tập vòng hay hàm hạng được được trình bày trong các mục sau. Đỉnh nghĩa 1.1.1. Matroid là một cặp M gồm tập hữu hạn của s và họ J các tập con s được gọi là các tập độc lập của M nếu thỏa mãn các điều kiện sau: M (li) 0 6 5. M(2i) N ế u X e J v à Y ạ thì Y e 7. M(3i) Nếu u , v E ÍF và |ơ | > |v | thì sẽ tồn tại phần tử X £ ( V U { i} ) G Ĩ . Sau đây ta sẽ xét một số ví dụ minh họa. Ví dụ 1.1.1. Cho ma trận dưới đây với các nhãn tương ứng: 2 u —V sao cho 1 2 3 4 1 0 0 1 0 0 1 0 0 0 5 6 7 0 0 1 1 1 0 1 0 1 1 0 Ký hiệu E — { 1 ,2,3,4,5,6,7 } là tập các vector cột xác định bởi nhãn của chúng. Giả sử 3 là họ các tập chỉ số I c E sao cho tập các vector cột được gãn nhãn bởi I là độc lập tuyến tính . Khi đó 3 gồm các tập con của E — {7} có nhiều nhất ba phần tử loại trừ {1,2,4}, {2,3,5}, {2,3,6} và loại cả các tập chứa {5,6}. Ta được {E, J) là matroid. Tính chất "độc lập" của các phần tử ở đây chính là tính chất độc lập tuyến tính của hệ vector cột của ma trận đã cho. Ví dụ 1.1.2. Xét đồ thị G cho bởi hình vẽ. 7 Hình 1.1: Đồ Thị G Xét họ 3 các tập cạnh của G mà không chứa chu trình nào của G. Như vậy, các tập của J sẽ không chứa bất kỳ tập nào trong các 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ọ jF xác định trên lập thành một matroid của G. Tính độc lập của các phần tử xác định bởi tính chất không chứa chu trình của các tập cạnh. Matroid xác định như trên gọi là matroid vòng của G. 3 Ví dụ 1.1.3. Cho tập s hữu hạn phần tử. Xét họ = {0} khi đó ta có ( s , ^ ) là một matroid được gọi là matroid tầm thường. Xét họ З 2 = СР(5*) = 2s khi đó ta có thể chứng minh được (51, З 2 ) là một matroid được gọi là matroid rời rạc. Trên đây khái niệm matroid được định nghĩa dựa trên tính độc lập của các phần tử . Người ta có thể định nghĩa matroid với những cách khác, tất nhiên là chúng tương đương. Sau đây ta tìm hiểu điều này thông qua các tiên đề. 1.2. Tiên đề cơ sở Cho matroid M = (s , jF). Xét họ không rỗng ъ có phần tử là các tập con độc lập lớn nhất của s trong M. Vì các phần tử của ъ là các tập độc lập nên ъ là họ các tập độc lập của M. Bổ đề 1.2.1. Nếu B\, B 2 là cơ sở của matroỉd M thì \B\ I = |Ä2 1Chứng minh Cho B \, B 2 là hai cơ sở của M, \B\ I < 1^21- Vì Bị và B 2 là hai tập độc lập nên thỏa mãn điều kiện M(3i), tồn tại phần tử e G (в 2 —Bị) sao cho (Bị и e) G 3 . Như vậy B\ không phải là tập độc lập lớn nhất, mâu thuẫn với B\ là cơ sở, suy ra giả sử sai. Vì thế \B\ I > \I$2 1• Đổi vai trò của B\ và B 2 , tương tự ta chứng minh được 1^21> \B\ |. Suy ra \Bị I = 1^21- О Định lý 1.2.1. Họ khác rỗng các tập con hữu hạn của s, kí hiệu là ъ là họ cơ sở của một matroỉd trên s khi và chỉ khi thỏa mãn các điều kiện sau: B(li) MBUB2 е Ъ , Bị Ç B 2 v à B2 Ç B \ . B(2i) Nếu B ị, B 2 G ъ và Xị £ (В 1 —в 2 ) thì tồn tại y G B 2 —B\ sao cho (ß, и {><})-W e ® . Chứng minh Ta chứng minh rằng họ ъ được xác định như trên thỏa mãn hai điều kiện Bị li), B(2i) của định lý 1.2.1. Xét B ị,B 2 G Ъ ,В\ Ф z?2 » mà theo bổ đề 1.2.1 ta có số phần tử của các cơ sỏ bằng nhau \B\ I = |z?2 |, hiển nhiên B(li) được thỏa mãn. 4 Cho B\ —X và B 2 là hai tập độc lập, \B\ —x\ < 1-^21- Theo điều kiện M(3i), G (B 2 — (B 1 —Jt)) sao cho ((# 1 - i ) U } ') G 3r. Hiển nhiên y E (B 2 —Bị). Đặt Bị — (Bị —x) Uy. Theo bổ đề 1.2.1 ta có |Яз| = |(5 | —x) U}’| = \B\ |. Hơn nữa, (В] —Jt) Uy là tập độc lập, suy ra z?3 là cơ sở của M. Vậy B(2i) được thỏa mãn. Bây giờ ta sẽ chứng minh họ ъ và tập s là một matroid theo định nghĩa 1.1.1. Cho 3 — {/ ç B\B G Ъ }. Ta sẽ chứng minh (5, J) là một matroid. Từ ъ thỏa mãn Bị li) nên 3 thỏa mãn Mị ỉ ỉ). Nếu ỉ e 3 , ĩ С ỉ ^ Ï с в , в е Ъ , thỏa mãn M(2i). Cho / ] , /2 G 0 với |/i I < |/г| sao cho v’ G0. Từ y G (B2 — В \), theo (2), y G ( /2 —/ | ), mâu thuẫn với điều giásử. Suyra B\ — ( / 1 u B2) là rỗng. Vì thế B\ —B2 — I\ —B2. B ,-B 2Ç h - I 2 (3) Mà IB\ I = |ß 2| nên |ßi —# 2 ! = \Вг —в 1 1, kết hợp với (1), (2), (3) ta có ^ 1^2 !9 IĨ13.U thuan VƠI § 1 ã thuyet (5,J) làmatroid. □ Ví dụ 1.2.1. Cho ma trận A là ma trận 5x8 có các cột là các vecter trong M5. Tập các vecter cột của A là { 1 ,2,3 ,4 ,5 ,6 ,7 ,8 }. 5 1 2 3 4 5 6 7 8 1 0 0 0 0 0 1 1 0 1 0 0 1 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 Cơ sở của matroid là một tập độc lập tuyến tính tối đại trong không gian vector cột. Xét hai cơ sở của matroid. / 1 1 0 > 0 1 1 0 0 = < 0 5 1 5 0 1 0 1 1 0 0 1 о 1 1 о 1 1 0 0 1 у ч 0 1 1 0 0 1 1о 4 / 1 о 1 1 о 1 1 1о = < 0 5 1 5 1 5 0 1 1 0 0 1 J Thay vector thứ 2 trong B\ bằng vecter thứ 2 trong # 2 được cơ sở Bi / 1 0 0 0 1 1 1 0 0 1 5 0 5 0 1 1 0 к 1 1 о 1 1 1о 0 ч 1 J Trong trường hợp này ta thấy tính chất B(2i), được thỏa mãn.Và điều này cũng chứng tỏ không có cơ sở nào chứa cơ sở khác. Một cách mô tả khác về khái niệm matroid là nhờ vào hàm hạng. 1.3. Tiên đề hạng Cho M = (S , jF) và họ tất cả các tập con của 6 s là 2S. Gọi hàm số r{A) — max{\X\ với X ç A và X G (F)} là hạng của A. Hạng của matroid M kí hiệu là r(M ), hay r(s). Nhận xét: Hạng của tập A là số phần tử của tập độc lập cực đại thuộc A. Nếu A độc lập thì r(A) = |A| Định lý 1.3.1. Cho s là tập hữu hạn khác rỗng và hàm số r : 2S — >N. Khi đó r là hàm hạng của matroid trên s khi và chỉ khi thỏa mãn cấc điều kiện sau v x , Y của S: R ( l i ) 0 < r ( X ) < |X|. R(2i) Nếu Y Ç X thì r(y) < r(x ). R(3i) r(X u y ) < r(X) + r(Y) - r(X n Y). Chứng minh Ta chứng minh rằng hàm số r được xác định như trên thỏa mãn ba điều kiện của định lý 1.3.1. Theo M(]ỉ),(d r ( ơ u v ) + / '( ơ n v ) ^ r(U) + r(V) > r ( u u v ) + r ( u п V) r ( u u v ) < t ị u ) + r(v) — r ( u п V) Cho R(3Ỉ) được thỏa mãn. 3 = ị x Ç 5 |r(x ) = |x|}, bây giờ ta sẽ chứng minh (5,J) là một matroid. Để làm được điều này, trước tiên ta đưa ra bổ đề sau. Bổ đề 1.3.1. Cho E là một tập hữu hạn và r là một hàm trên 2E thỏa mãn điều kiện R(3i). N ế u X , Y e 2E y y G Y —X , r ( X и y) = r { x ) thì r ( X u y ) = r ( x) . Chứng minh Cho X — Y — { j | , -^Ук}- Ta xét phép quy nạp theo к. Nếu к = 1 bài toán hiển nhiên là đúng. Giả sử bài toán đúng với k = n, cần chứng minh bài toán đúng với к = n + 1. 7 r(X ) + r(X ) = r ( Z U { y i ,> ?2 ,..-,>'/t}) + K ^ u >’« + 0 > r((X U {yi,);2,--.,);J ) U ( X U j „ + l)) + r((X U {ji,} 72,--,)7-t} ) n ( X U ^ + 1)) = r ( x u {)’! ,);2, - , y i c + 1}) + r(X) o r(X) > /•(XU{}'i,)’2 v , ) ' t + 1}) Theo R(2i) suy ra (X u { > ’ 1 ,>’2 , + 1}) Q X, vô lý, suy ra r(X) = r ( x u {>’1 ,}’2 , •••,}’£: + 1}) □ Ta trở lại phần chứng minh (S,J) là matroid. Theo Rị li), 0 > r(0) > |0|nên r|0| = |0| suy ra 0 G 0. Mị l i ) được thỏa mãn. Cho / e J ,/' C /. Khi đó rự) = |/|. Theo R(3i) rự ' u (/ —/ ) ) + r { ỉ n (/ —/ ) ) > r ( / ) + r ( / - / ) > r(//) + r ( 7 - / ) ^r(/) + r(0) >r(/) + r(/-/) (1) Nhưng r(ỉ) — |/| và r(0) = 0. Ngoài ra, theo R(2i), r ự ) > | / | và r(I —ĩ ) > \I —ĩ \ và (1) suy ra |/| > r ự ) + r ( I - í ) > | / | + | / - / ' | = |/| => r ự ) = |/1 I G J. M(2/J được thỏa mãn. Để chứng minh J thỏa mãn M(3i), giả sử ngược lại. Cho /ị , / 2 G ũ với |/| I < I/2 I và Ve £ ( /2 —/1 ),/j u £ e J. Khi đó , Vé’, r(/i u e) Ỷ |/j Ue\. Do đó, theo R ịli), R(2i) và / e 3. ta nhận được \fe: |/, I + 1 > r(/i U^) > r(/,) = /1 <£> (/1 Ue ) = |/i I Áp dụng bổ đề trên với X = I\ và Y = h , ta có /*(/]) = rự\ u / 2 ). Nhưng|/] I = r ự I) và rự\ u / 2 ) < r ự 2) = 1/ 2 1, nên |/i I < |/2|, mâu thuẫn với |/| I <: |/2|. Suy ra 3 thỏa mãn M(3i). Vậy (S, 3) là một matroid. □ Ví dụ 1.3.1. Xét ma trận A và matroid như ở ví dụ 1.2.1. Ta có một trong những không gian vector cột của A là / 1 1 0 0 \ 1 1 0 0 0 5 1 5 0 5 0 1 1 0 0 0 0 0 1 V Vì đây có 4 vector trong cơ sở và là tập độc lập tuyến tính lớn nhất nên hạng của ma trận A là 4. Quan sát ma trận c các vector cột của A. / \ 1 1 0 0 0 1 0 1 0 1 0 1 0 1 5 5 0 5 0 0 1 1 0 0 0 0 1 0 V Kích thước của c là 5, hạng của c là 4 nên R(2i) được thỏa mãn. Cho tập D sao cho D c c CA \ / 1 1 0 1 0 1 0 í 1 5 0 0 0 1 0 0 0 > Ta thấy rằng 3 = rị p) < r(c) — 4 nên điều kiện R(2i) được thỏa mãn. Từ định nghĩa của matroid, điều kiện R(3i) được thỏa mãn với hai tập C,D c E. r ( c UD ) + ĩ ị c n ữ ) < r(C) + r(D) 4+ 3 = 4+ 3 1.4. Tiên đề vòng Cho matroid M = (s , jf). Gọi mỗi tập phụ thuộc cực tiểu của M là một vòng, kí hiệu G(M) là họ các vòng. Nhận xét: Nếu bớt đi một phần tử của c thì ta được tập độc lập. Định lý 1.4.1. Cho tập hữu hạn s và c là họ các tập con của s. Khi đóc là tập vòng của matroỉd M trên s khỉ và chỉ khi thỏa mãn các điều kiện sau: C(li) %ị Q. C(2i) Nếu C\ ,C 2 6 c vồ C\ c C2 thì C\ = C2 . C(3i) Nếu C\ ,C 2 6 c và e G C\ n C 2 thì tồn tại C3 G c, C3 c (Cl UC 2 ) —e. 9 Chứng minh Ta chứng minh tập с được xây dựng như trên sẽ thỏa mãn ba điều kiện của Định lý 1.4.1 Theo M(li) ta có 0 £ jF nên hiển nhiên ữ ị G, C(ỉi) được thỏa mãn. Theo M(2i), nếu X e J , Y ç X thì Y G 3\ Khi ta thêm cùng một phần tử vào mỗi tập X, Y thì được X , Y là các tập phụ thuộc tối tiểu và Y Ç x ' . Nếu Ý с X thì vô lý vì một tập phụ thuộc tối tiểu không thể là con thực sự của một tập phụ thuộc tối tiểu khác, suy ra Ý = x ' , C(2Ỉ) được thỏa mãn. Cho c , , c 2 G С,С] Г1С2 = e. G iả sử không CÓC3 G с sao CI10C3 ç (Cl UC2) —e. Ta CÓ Cl —e,C 2 — е,Сз ç ( с I UC 2 ) —e đều là các tập độc lập và |(C| UC 2 ) — e \> IC\ —e\, |(Ci UC2 ) —e \ > |Сг —e\. Theo M(3i), xét hai tậpCị —е,Сз Ç (Cị UC2 ) —e độc lập và |(Cị UC 2 ) —e\ > \Cị — e\ thì 3 / G ((Cl UC 2 ) — e) — (Cl —e) sao cho (C, - e) u / G 3r. Mà / G ((Cl UC 2 ) —e) <^> / G (c2-e) suy ra |Сг —ể| > |C] - e\. Tương tự ta có \C\ — e\ > |Сг —e\, mâu thuẫn chứng tỏ giả sử sai. Vậy điều kiện C(3i) được thỏa mãn. □ Cho С 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 С với С С С. Như vậy С là tập độc lập, suy ra с ç Theo định nghĩa ì. 1.1 {s , ể ) là một matroid. Ví dụ 1.4.1. Cho đồ thị H bởi hình vẽ. 2 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 dồ 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, c, d, e} 10 {a,ej} 6, úí, g j{dj,g} {b,c,g} {b,c,d,f} Quan sát các vòng trên ta thấy điều kiện C(li), C(2i) được thỏa mãn. Xét vòng C\ — { a , e , f } ,C 2 = {a, b, c, d, e} thuộc c. Ta thấy hai vòng đều chứa hai phần tử {«} và {^}. X étX = c 1 UC 2 . 2 Hình 1.3: Vòng c, 2 Hình 1.4: VòngC2 Có thể thấy ở đây ba vòng trong X là { ữ ,£ ,/} , {ữ,z?,c,d,e}, trong đó, { b, c , d, f } là một vòng trong X mà không chứa cả {a } và {e}. Như vậy, điều kiện C(3i) được 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ị Q\ và Q2 là không đẳng cấu nhưng hai matroid vòng M(Q\ ) và M(QÌ) là hai matroid đẳng cấu. Ta nhắc lại, M\ = ( S\, 5^1 ) và М2 = (S2 , 3 2 ) được gọi là đẳng cấu nếu có song ánh (p : S\ — » S 2 sao cho X ç Si ,x G 5 khi và chí khi 12 ọ(x) E 3^2 . Ở ví dụ trên, chỉ cần xét matroid rời rạc trên E(G 1 ) và EịGỉ) hiển nhiên ta thấy M ( G \ ) và M{G 2 ) 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 nói đến trong chương 1. Ở đó, cấu trúc độc lập của M( G) được xây dựng bởi các tập cạnh không chứa chu trình của G. Trong mục này ta sẽ nói đến sự liên hệ giữa matroid với đồ thị thông qua khái niệm matroid vòng của đồ thị. Định lý sau có thể suy ra ngay từ định nghĩa. Định lý 2.1.1. Cho đồ thị G — (V, £), khi đó mỗi chu trình của G sẽ tạo thành một vòng của matroid M(G) trên tập cạnh E của G. Một số tính chất khác. Tính chất 2.1.1. Nếu đồ thị G là liên thông thì mỗi cơ sỏ của M(G) là một cây khung của đồ thị G. Chứng minh Ta đã biết với đồ thị liên thông G có n đỉnh. Có thể hình dung một cách đơn giản cây khung của G là đồ thị con kết nối mọi đỉnh của G và có /ì — 1 cạnh. Nếu T là cây khung bất kỳ của đồ thị G và có 72— 1 cạnh thì T không chứa chu trình. Nếu thêm vào T một cạnh thì T sẽ chứa chu trình và có n cạnh. Ta đi chứng minh tập cây khung có n — 1 cạnh của đồ thị G là họ cơ sở. Trên đồ thị G không có cây khung nào là con của cây khung nào nên B(ỉi) luôn thỏa mãn. Xét cây khung p 1 , p2 của G v ầe 1 G P\ — P2 . Ta thêm 6\ vào P2 thì p2 có n cạnh nên chứa một chu trình. Luôn tồn tại đỉnh bớt đi £2 - Xem thêm -