Chuyên đề Một số ưng dụng của đồ thị lưỡng phân và đồ thị phẳng

Nội dung tài liệu: Chuyên đề Một số ưng dụng của đồ thị lưỡng phân và đồ thị phẳng

1. SỞ GIÁO DỤC VÀ ĐÀO TẠO TỈNH BẮC GIANG TRƯỜNG THPT CHUYÊN BẮC GIANG ****** CHUYÊN ĐỀ MỘT SỐ ỨNG DỤNG CỦA ĐỒ THỊ LƯỠNG PHÂN VÀ ĐỒ THỊ PHẲNG Dương Thị Việt Hà – Nguyễn Thị Thanh Loan Tổ: Toán - Tin Bắc Giang, tháng 02 năm 2024
2. MỞ ĐẦU I. ĐẶT VẤN ĐỀ Lý thuyết đồ thị là một phần quan trọng trong Toán học và đặc biệt là trong chương trình dành riêng cho các lớp Chuyên Toán. Mặc dù Lý thuyết đồ thị đã được khoa học phát triển từ rất lâu nhưng lại có nhiều ứng dụng hiện đại đặc biệt trong các bài toán Toán-Tin và sự phát triển của công nghệ Machine Learning. Hiện nay, các bài toán chủ đề Lý thuyết đồ thị xuất hiện ngày càng thường xuyên trong các đề thi toán trong khu vực, quốc gia và quốc tế. Vấn đề tổ hợp nói chung và vấn đề đồ thị nói riêng cần được quan tâm phát triển mạnh hơn nữa, tạo tiền đề tốt cho học sinh khi tham gia các kì thi học sinh giỏi khu vực, quốc gia và quốc tế. Trong chương trình giáo dục phổ thông 2018, chủ đề Lý thuyết đồ thị lần đầu tiên được đưa vào chương trình Chuyên đề Toán lớp 11 đã thể hiện tinh thần thiết thực, hiện đại của chương trình giáo dục Việt Nam. Chuyên đề này được viết nhằm phục vụ trực tiếp cho công tác giảng dạy bồi dưỡng học sinh giỏi và hy vọng nó cũng là tài liệu có ích cho các em học sinh tham khảo và học tập. Trong chuyên đề này chúng tôi, tập trung khai thác hệ thống lý thuyết và bài tập về đồ thị lưỡng phân và đồ thị phẳng. Chuyên đề gồm có ba chương: Chương 1. Kiến thức chuẩn bị: trình bày các khái niệm cơ bản và chứng minh các định lý cần thiết trong lý thuyết đồ thị nói chung. Chương 2. Đồ thị lưỡng phân: trình bày khái niệm, mệnh đề, định lý và bài tập về chủ đề đồ thị lưỡng phân. Chương 3. Đồ thị phẳng: trình bày hệ thống lý thuyết, ví dụ và bài tập về chủ đề đồ thị phẳng. II. MỤC ĐÍCH NGHIÊN CỨU Giúp cho học sinh có thêm một tài liệu và một số dạng bài tập cơ bản, nâng cao về đồ thị lưỡng phân và đồ thị phẳng. 2
3. III. NHIỆM VỤ NGHIÊN CỨU Đưa ra hướng tiếp cận cho một số dạng bài toán tổ hợp được xử lý bằng cách xây dựng đồ thị phẳng và đồ thị lưỡng phân, với hệ thống lí thuyết và ví dụ minh họa đặc trưng. IV. ĐỐI TƯỢNG NGHIÊN CỨU Các bài toán cơ bản về đồ thị phẳng và đồ thị lưỡng phân trong các cuộc thi học sinh giỏi khu vực, trong nước và quốc tế. V. PHƯƠNG PHÁP NGHIÊN CỨU Thông qua thực tiễn dạy một số chuyên đề tổ hợp, lí thuyết đồ thị cho lớp chuyên toán trường THPT Chuyên Bắc Giang để tổng hợp, phân tích, đánh giá. VI. NHỮNG ĐÓNG GÓP CỦA ĐỀ TÀI Trong chuyên đề này, chúng tôi đã cố gắng đưa ra được một hệ thống lý thuyết và bài tập tương đối đa dạng, đầy đủ giúp học sinh tiếp cận các bài toán tổ hợp theo hướng sử dụng lý thuyết đồ thị đặc biệt là đồ thị lưỡng phân và đồ thị phẳng. 3
4. NỘI DUNG NGHIÊN CỨU VÀ KẾT QUẢ CHƯƠNG I. KIẾN THỨC CHUẨN BỊ I. Đỉnh, cạnh, bậc của đỉnh. Định nghĩa 1.1.1. Một đồ thị là một tập hợp hữu hạn các điểm (gọi là các đỉnh của đồ thị) cùng với tập hợp các đoạn đường cong hay thẳng (gọi là cạnh của đồ thị) có đầu mút tại các đỉnh của đồ thị. Kí hiệu GVE= ( , ) với V là tập đỉnh và EVV là tập cạnh. Định nghĩa 1.1.2. Hai đỉnh được gọi là kề nhau nếu có 1 cạnh nối 2 đỉnh này. Kí hiệu cạnh nối 2 đỉnh u và v là e= ( u, v) , nói chung (u,v) khác (v,u) , nếu ta coi 2 cạnh này là 1 thì ta có đồ thị vô hướng, nếu coi chúng khác nhau thì ta có đồ thị có hướng. Có thể tồn tại cạnh nối 1 điểm với chính nó, cạnh này gọi là khuyên. Định nghĩa 1.1.3. Một đồ thị không có khuyên, trong đó hai đỉnh được nối bằng nhiều nhất một cạnh (không có hai cạnh nào cùng nổi một cặp đỉnh) gọi là một đơn đồ thị. Một đồ thị không có khuyên, trong đó hai đỉnh có thể nối bằng nhiều cạnh, gọi là một đa đồ thị. Định nghĩa 1.1.4. Một đồ thị đầy đủ với n đỉnh, kí hiệu là Kn , là đơn đồ thị vô 2 hướng mà giữa hai đỉnh bất kì của nó luôn có cạnh nối, khi đó có tất cả Cn cạnh. Ví dụ: K4 K5 4
5. Định nghĩa 1.1.5. Với U là tập con của tập các đỉnh, kí hiệu GU( ) là đồ thị con của G, thu được khi ta xóa tất cả các đỉnh nằm ngoài U, chỉ giữ lại các cạnh mà cả 2 đầu mút thuộc U. Định nghĩa 1.1.6. Trong đồ thị vô hướng GVE( , ) , kí hiệu dv( ) hoặc deg(v) cho bậc của đỉnh v, là số cạnh mà v là đầu mút. Một khuyên được tính 2 lần cho đỉnh. Một điểm gọi là chẵn nếu nó có bậc chẵn và được gọi là lẻ nếu nó có bậc lẻ. Đỉnh bậc 0 được gọi là đỉnh cô lập. Đỉnh bậc 1 được gọi là đỉnh treo. Ví dụ: Đồ thị dưới đây có d( v1) =4, d( v 2) = 6, d( v 3 ) = 1, d( v45) ==3, d( v ) 4. Mệnh đề 1.1.7. Trong một đồ thị có nhiều hơn 1 đỉnh luôn có 2 đỉnh có cùng bậc. Chứng minh. Xét GVE( , ) có n đỉnh, khi đó bậc của mỗi đỉnh sẽ là số tự nhiên nhỏ hơn n, hơn nữa không tồn tại 2 đỉnh mà bậc của chúng tương ứng là 0 và n −1 (Có đỉnh bậc n −1 có nghĩa nó nối với tất cả các đỉnh khác nên không còn đỉnh bậc 0). Nếu không tồn tại 2 đỉnh cùng bậc thì bậc của các đỉnh này nhận tất cả các giá trị 0,1,2,...,n − 1, mâu thuẫn với nhận xét trên. Ta có điều chứng minh. Định lý 1.1.8. (Bổ đề bắt tay) Trong một đồ thị vô hướng GVE( , ) tùy ý tổng bậc của tất cả các đỉnh gấp đôi số cạnh của đồ thị: 2Ev=  deg vV Chứng minh. Trong mỗi đồ thị tổng bậc các đỉnh của một đồ thị thì mỗi cạnh được tính đúng hai lần bởi hai đỉnh của nó. Do đó tổng này gấp đôi số cạnh của đồ thị. 5
6. Hệ quả 1.1.9. Trong một đồ thị vô hướng tùy ý số đỉnh bậc lẻ luôn là một số chẵn. Chứng minh. Theo định lý trên thì tổng các bậc của các đỉnh luôn là một số chẵn do vậy số các đỉnh bậc lẻ luôn là một số chẵn. Hệ quả 1.1.10. Trong một đồ thị vô hướng có số lẻ đỉnh luôn có một số lẻ các đỉnh có bậc chẵn. Chứng minh. Theo hệ quả trên thì số đuỉnh bvậc lẻ etrong= ( u, vđ)ồ thị G là một số chẵn. Do trong đồ thị có số lẻ đỉnh, nên số các đỉnh bậc chẵn phải là số lẻ. Định nghĩa 1.1.11. Nếu là cung của đồ thị có hướng G thì ta nói hai đỉnh và là kề nhau, và nói cung (uv, ) nối đỉnh u với đỉnh v hoặc cũng nói cung này đi ra khỏi đỉnh u và đi vào đỉnh v . Đỉnh u (v ) sẽ được gọi là đỉnh đầu (cuối) của cung (uv, ) . Ta gọi bậc ra (bậc vào) của đỉnh v trong đồ thị có hướng là số cung của đồ thị đi ra khỏi nó (đi vào nó) và ký hiệu là deg+ v và deg− v . Định lý 1.1.12. Trong một đồ thị có hướng GVE( , ) ta có deg+−v== deg v E v V v V II. Đường đi, chu trình, cây Định nghĩa 1.2.1. Đường đi độ dài n từ đỉnh u đến đỉnh vGVE trên( , đồ) thị vô hướng GVE( , ) là dãy các cạnh nối tiếp (hai cạnh nối tiếp là hai cạnh có chung một đầu mút) x0, x 1 ,..., xnn− 1 , x , trong đó n là số nguyên dương x0 == u, xn v , (xii; x+1 ) E in =0, − 1. Đường đi như trên còn có thể biểu diễn thành dãy các cạnh (xx01;,) (x1; x 2) ,...,( xnn− 1 ; x ). Đỉnh u là đỉnh đầu, đỉnh v là đỉnh cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối (uv= ) được gọi là chu trình. 6
7. Đường đi hay chu trình được gọi là sơ cấp nếu như không đi qua đỉnh nào hai lần trở lên. Đường đi hay chu trình được gọi là đơn giản nếu như không đi qua cạnh nào hai lần trở lên. Khái niệm đường đi và chu trình trên đồ thị có hướng được định nghĩa hoàn toàn tương tự, chỉ có điều khác biệt duy nhất là ta phải chú ý tới các cung của đồ thị. Ví dụ. Với đồ thị bên, ta có đường đi v1,v2 ,v6 ,v5 ,v3 , đường đi này có độ dài là 4 và có thể kí hiệu là e1,e6 ,e5 ,e4 . v4 e3 v1 e2 v5 e4 e1 e5 v3 e6 v v2 6 Định nghĩa 1.2.2. Khoảng cách giữa 2 đỉnh a và b là độ dài của đường đi ngắn nhất nối 2 đỉnh này, kí hiệu d( a, b). Quy ước d( a,0 a) = . Nếu không có đường đi nối a, b thì quy ước d( a, b) = . Ví dụ. Ở đồ thị trên ta có d( v1, v 3) == 4, d( v 3 , v 4 ) 1. Định nghĩa 1.2.3. Đường kính của đồ thị G là khoảng cách lớn nhất giữa 2 đỉnh của đồ thị, kí hiệu dG( ). Nếu đồ thị có 2 điểm a, b mà d( a, b) = thì quy ước dG( ) = . u v VíGVE( dụ, . Đ) ồ thị bên trên có đường kính là 4. Định nghĩa 1.2.4. Trên đồ thị vô hướng , hai đỉnh và được gọi là liên thông nếu có một đường đi nối và . Đồ thị vô hướng được gọi là liên thông nếu với mọi cặp đỉnh của G là liên thông. Định lý 1.2.5. Với GVE( , ) là liên thông thì EV −1. Chứng minh. 7
8. Ta chứng minh quy nạp theo số đỉnh n của đồ thị. Với n =1,2 ta thấy điều cần chứng minh. Giả sử bài toán đúng với đồ thị N đỉnh, nghĩa là có ít nhất N −1 cạnh. Xét GVE( , ) có N +1 đỉnh và liên thông, suy ra bậc của mỗi đỉnh đều lớn hơn 0. Ta xét 2 trường hợp Trường hợp 1: Bậc của mỗi đỉnh đều lớn hơn 1. Ta có 22E=  d( A) N , suy ra EN , có điều chứng minh. AV Trường hợp 2 : Giả sử có đỉnh A của đồ thị có bậc 1, xét đồ thị con GGA' =−  (bỏ A và cạnh mà A là đầu mút). Dễ thấy G' là liên thông và có N đỉnh và E −1 cạnh. Theo giả thiết quy nạp với G' ta có ENEN−1 − 1 ( + 1) − 1, có điều chứng minh. Mệnh đề 1.2.6. Cho đồ thị GVE( , ) . Các đỉnh của đồ thị có thể phân hoạch thành các tập VVV12, ,..., r mà các đồ thị con GV( i ) là liên thông và không có cạnh nào nối cặp điểm ở 2 tập khác nhau. Chúng được gọi là các thành phần liên thông của G. Đồ thị GVE( , ) là liên thông khi và chỉ khi G có duy nhất một thành phần liên thông. Định nghĩa 1.2.7. Cho đồ thị và vV . V ' là tập hợp các đỉnh của V liên thông với v , E ' là tập hợp các cạnh nối 2 đỉnh của V ' . Khi đó đồ thị GVE'( ', ') gọi là thành phần liên thông của G chứa v . Đương nhiên nếu v và u liên thông trong G thì thành phần liên thông của G chứa v cũng là thành phần liên thông chứa u . Định nghĩa 1.2.8. Đồ thị có hướng GVE( , ) được gọi là liên thông mạnh nếu có đường đi từ a đến b và từ b đến a với  a, b V . Đồ thị có hướng GVE( , ) được gọi là liên thông yếu nếu đồ thị vô hướng tương ứng của nó là liên thông. Định nghĩa 1.2.9. Một rừng là một đồ thị không nhất thiết liên thông và không có chu trình. 8
9. Định nghĩa 1.2.10. Một cây là một đồ thị liên thông và không có chu trình. Định lý 1.2.11. Một cây bất kì luôn chứa đỉnh có bậc 1, đỉnh này được gọi là lá. Chứng minh. Giả sử tất cả các đỉnh đều có bậc không nhỏ hơn 2. Xét đường đi bất kì (v12, v ,..., vn )( n 2). Nếu vn nối với 1 trong các đỉnh vv12,..., n− thì ta có 1 chu trình, mâu thuẫn. Nếu không thì vn phải nối với 1 đỉnh khác vn+1 . Tiếp tục quá trình thì đồ thị sẽ có vô hạn đỉnh, mâu thuẫn. Hệ quả 1.2.12. Từ kết quả trên suy ra nếu đồ thị có bậc mỗi đỉnh đều lớn hơn hoặc bằng 2 thì có chu trình. Mệnh đề 1.2.13. Một cây có thể tạo thành từ một đồ thị liên thông bằng cách bỏ đi một số cạnh. Chứng minh. Thật vậy, ta có thể tạo ra bằng cách bỏ đi 1 cạnh trong một chu trình, làm với tất cả các chu trình ta sẽ thu được cây. Định lý 1.2.14. Một đồ thị liên thông là một cây nếu và chỉ nếu nó chứa đúng V −1 cạnh. Chứng minh. Giả sử G là liên thông, có n đỉnh và có n −1 cạnh và G có chu trình, chẳng hạn AAAA1 2... k 1 . Nhận thấy nếu loại bỏ cạnh AA12 đồ thị mới vẫn liên thông, tuy nhiên lúc này nó chỉ có n − 2 cạnh, mâu thuẫn với EV −1, do G liên thông. Ngược lại, do mọi cây đều có đỉnh bậc 1, bỏ đỉnh này khỏi đồ thị, khi đó ta có 1 cây mới mà số đỉnh và số cạnh cùng giảm đi 1. Bằng quy nạp theo số đỉnh ta có điều chứng minh. Định lý 1.2.15. Nếu bỏ đi một cạnh bất kì của cây thì nó không liên thông. Chứng minh. 9
10. Giả sử cây có n đỉnh, theo kết quả trên thì nó có n −1 cạnh. Nếu bỏ đi 1 cạnh thì nó còn n − 2 cạnh. Cũng theo kết quả trên thì nó không còn là cây. Việc bỏ đi một cạnh sẽ không làm xuất hiện chu trình nào, suy ra nó không liên thông. Định lý 1.2.16. Nếu đồ thị G không có chu trình, có n đỉnh và n −1 cạnh thì nó là một cây. Chứng minh. Ta cần cần chứng minh G liên thông. Phân hoạch G thành các thành phần liên thông, giả sử có k thành phần liên thông. Ta tạo ra k −1 cạnh mới bằng cách nối thành phần liên thông thứ 1 với thứ 2 (lấy 1 đỉnh ở 1 nối với 1 đỉnh ở 2), làm đến thành phần liên thông thứ k. Khi đó ta sẽ được đồ thị mới liên thông và không có chu trình (mỗi thành phần liên thông không có chu trình và cách nối không tạo ra chu trình), suy ra đồ thị mới này là 1 cây. Theo kết quả trên, số cạnh của cây này là n −1, suy ra k =1, nghĩa là đồ thị ban đầu liên thông, ta có điều chứng minh. Định lý 1.2.17. Giữa 2 đỉnh A, B bất kì trong một cây có đúng một đường đi. Chứng minh. Do cây là một đồ thị liên thông nên giữa A, B có ít nhất 1 đường đi. Giả sử còn 1 đường đi nữa nối A, B. Ta thấy chỉ xảy ra 1 trong 3 trường hợp như hình dưới đây, khi đó cây này có chu trình, mâu thuẫn. Vậy giả sử sai, có điều chứng minh. Nhận xét: 1. Nếu ta nối 2 đỉnh không kề nhau trong cây thì sẽ thu được 1 chu trình. Khi đó nếu đồ thị G có n đỉnh và ít nhất n cạnh thì nó có chu trình. 10
11. 2. Kết quả mạnh hơn được đưa ra bởi Erdos: Một đồ thị có n đỉnh và số cạnh ít (nk−1) nhất là thì tồn tại 1 chu trình có độ dài ít nhất là k +1. 2 3. Một đồ thị có n đỉnh và n +1 cạnh thì có ít nhất 2 chu trình. Thật vậy, trước hết khẳng định đồ thị có 1 chu trình, ta xóa 1 cạnh của chu trình này thì đồ thị còn lại có n cạnh, khi đó có 1 chu trình khác. Vậy nó có ít nhất 2 chu trình. 4. Nếu tất cả các đỉnh có bậc ít nhất là d thì có 1 đường đi có độ dài ít nhất là d +1. III. Đường đi Euler và Hamilton Định nghĩa 1.3.1. Cho một đa đồ thị G. Đường đi qua tất cả các cạnh của đồ thị mỗi cạnh đúng một lần được gọi là đường đi Euler. Chu trình bắt đầu tại một đỉnh v nào đó qua tất cả các cạnh của đồ thị mỗi cạnh đúng một lần sau đó quay trở lại v được gọi là chu trình Euler. u v Định lý 1.3.2. Một đa đồ thị G có một chu trình Euler khi và chỉ khi G liên thông và mọi đỉnh của G đều có bậc chẵn. Chứng minh. Dễ thấy, một đồ thị có chu trình Euler phải liên thông và mỗi đỉnh có bậc chẵn. Thật vậy, khi chu trình Euler tới một đỉnh thì nó cũng phải rời khỏi đó. Vậy mỗi lần chu trình Euler tới một đỉnh, nó nhất định sẽ đi qua hai cạnh nhận đỉnh đó làm đầu mút. Khi quay trở lại điểm xuất phát, chu trình Euler đã đi qua một số cạnh chẵn ở mỗi đỉnh. Ngược lại, khi G liên thông và mọi đỉnh của G đều có bậc chẵn. Ta sẽ xây dựng một chu trình Euler cho một đồ thị có V = n đỉnh. Với n = 2 , dễ thấy G gồm hai đỉnh và được nối với nhau bằng một số chẵn cạnh, ta dễ dàng chỉ ra một chu trình Euler đi từ tới rồi quay lại trở về . Với n 2 , chọn một đỉnh làm đỉnh xuất phát và chọn một đường đi tùy ý để quay lại đỉnh . Do bậc của tất cả các đỉnh đều chẵn nên quá trình trên luôn diễn ra 11
12. và ta không bị mắc kẹt tại bất cứ đỉnh nào, do nếu ra có thể đi vào một đỉnh từ một cạnh nào đó, ta luôn có thể đi ra bằng một cạnh khác. Gọi Eu là tập tất cả các cạnh sau vòng lặp đầu tiên, xét đồ thị con G’ của G gồm tập cạnh là E \ Eu mà không có đỉnh nào bị cô lập, mỗi đỉnh trong đồ thị này đều có bậc chẵn và tổng số đỉnh của đồ thị không vượt quá n. Bằng quy nạp, ta có thể xây dựng được chu trình Euler cho mỗi thành phần liên thông của đồ thị con G’. Mặt khác, do G liên thông nên ta có thể kết nối các chu trình Euler vừa xây dựng trên đồ thị con và trên chu trình , tạo ra một chu trình Euler trên G. Ta có thể minh họa quá trình trên bởi một ví dụ sau: - Xét đồ thị G liên thông gồm tất cả các đỉnh có bậc chẵn như hình vẽ, dễ thấy ta có thể tạo ra một chu trình Eb xuất phát từ b và quay trở lại b: b,c,f. - Khi đó, xét đồ thị con của đồ thị đã cho sau khi đã bỏ đi tất cả các cạnh của chu trình đầu tiên: - Ta có thể tạo ra các chu trình Euler trên mỗi thành phần liên thông của đồ thị con: cdabe và fgh. 12
13. - Kết nối với chu trình ban đầu ta thu được một chu trình Euler trên đồ thị G: Eb v v u v Hệ quả 1.3.3. Một đa đồ thị G có một đường đi Euler từ đỉnh tới đỉnh khi và chỉ khi G liên thông và mọi đỉnh của G đều có bậc chẵn, trừ và có bậc lẻ. Định nghĩa 1.3.4. Cho một đa đồ thị G. Đường đi qua tất cả các đỉnh của đồ thị mỗi đỉnh đúng một lần được gọi là đường đi Hamilton. Chu trình bắt đầu tại một đỉnh nào đó qua tất cả các đỉnh còn lại mỗi đỉnh đúng một lần sau đó quay trở lại được gọi là chu trình Hamilton. Đồ thị được gọi là đồ thị Hamilton nếu nó chứa chu trình Hamilton. Đồ thị chứa đường đi Hamilton được gọi là đồ thị nửa Hamilton. Định lý 1.3.5. (Định lý Ore) Nếu G là đơn đồ thị có n đỉnh ( n 3) và mỗi cặp đỉnh không kề nhau đều có tổng bậc không nhỏ hơn thì G có một chu trình Hamilton. Chứng minh. Xét G là đơn đồ thị có đỉnh ( ) và mỗi cặp đỉnh không kề nhau đều có tổng bậc không nhỏ hơn . Giả sử G không có một chu trình Hamilton nào. Chọn bất kỳ hai đỉnh bất kỳ của G chưa được nối bởi một cạnh và thêm một cạnh mới vào giữa chúng. Tiếp tục làm như vậy cho đến khi chúng ta đạt được đồ thị 13
14. Gl có chu trình Hamilton. (Quá trình này phải dừng lại vì cuối cùng chúng ta sẽ đạt được đồ thị đầy đủ n đỉnh, rõ ràng là có chu trình Hamilton.) Đặt G̃ là đồ thị thu được ngay trước Gl và giả sử (x, y) là cạnh được thêm vào G̃ để thu được Gl . Gọi z1, z2, z3, , zn, z1 là đường đi Hamilton khép kín trong 푙. Đường này phải sử dụng cạnh (x, y) tại một nút (nếu không ̃ sẽ có chu trình Hamilton). Không mất tổng quát, giả sử (z1, zn) = ( , ) thì z1, z2, z3, , zn là đường đi Hamilton không đóng trong ̃. Hơn nữa, ta có 푛 ≥ 3 vì nếu 푛 = 2 thì bước đầu tiên là ( , ) và bước thứ hai là ( , ), nghĩa là ta đã đi qua một cạnh hai lần. Đặt A = {푖: 2 ≤ 푖 ≤ 푛, 푖 kề } và B = {푖: 2 ≤ 푖 ≤ 푛: 푖−1 kề y} Do x và y không kề nhau trong G̃ nên chúng cũng không kề nhau trong G. Do đó 푒 ( ) + 푒 ( ) ≥ 푛. Khi đó |A| + |B| ≥ n, mà A và B là các tập con của {2, 3, 4, , 푛} nên tồn tại 푖 sao cho kề với 푖, và y liền kề với 푖−1. Khi đó , 푖, , 푛−1, , 푖−1, 푖, sẽ là một chu trình Hamilton trong ̃, mâu thuẫn. Hệ quả 1.3.5. (Định lý Dirac) Nếu G là đơn đồ thị có đỉnh ( ) và mỗi đỉnh n đều có bậc không nhỏ hơn thì G có một chu trình Hamilton. 2 Hệ quả 1.3.6. Nếu G là đơn đồ thị có đỉnh ( ) và mỗi đỉnh đều có bậc không n −1 nhỏ hơn thì G có một đường đi Hamilton. n n 3 2 IV. Tô màu đồ thị Định nghĩa 1.4.1. Số màu (sắc số) của graph là số nhỏ nhất của số màu cần thiết để tô các đỉnh sao cho không có 2 đỉnh kề nhau được tô cùng màu. Số màu của graph luôn nhỏ hơn hoặc bằng đỉnh lớn nhất cộng thêm 1. 14
15. CHƯƠNG 2. ĐỒ THỊ LƯỠNG PHÂN I. Đồ thị lưỡng phân Định nghĩa 2.1.1: Một đồ thị = ( , ) được gọi là đồ thị lưỡng phân nếu tập hợp các đỉnh có thể phân thành hai tập con khác rỗng 1 và 2, 1 ∩ 2 = ∅ sao cho không có cạnh nào nối hai đỉnh trong cùng một tập. Ví dụ: Định nghĩa 2.1.2: Một đồ thị = ( 1 ∪ 2, ) được gọi là đồ thị lưỡng phân đầy đủ 퐾 ,푛 nếu | 1| = , | 2| = 푛 và mọi đỉnh của 1 được nối với mọi đỉnh của 2. Ví dụ: Tính chất 2.1.3: +) Một đồ thị là lưỡng phân khi và chỉ khi có thể tô bằng nó bằng hai màu. +) Mỗi đồ thị con của một đồ thị lưỡng phân là một đồ thị lưỡng phân. +) Mỗi cây là một đồ thị lưỡng phân. 15
16. Định lý 2.1.4 (Định lý Koenig): Một đồ thị là đồ thị lưỡng phân khi và chỉ khi mọi chu trình của nó có độ dài chẵn. Chứng minh. +) Giả sử = ( , ) là đồ thị lưỡng phân. Khi đó, tập có thể phân thành hai tập con khác rỗng 1 và 2, 1 ∩ 2 = ∅ sao cho không có cạnh nào nối hai đỉnh trong cùng một tập. Xét một chu trình 1 2 푛 1 bất kì của . Không mất tính tổng quát, ta giả sử 1 ∈ 1. Điều này dẫn đến 2 ∈ 2, 3 ∈ 1, Do đó, ∈ 1 nếu lẻ, ∈ 2 nếu chẵn. Lại có 푛 ∈ 2 suy ra 푛 là số chẵn. Do đó chu trình có độ dài chẵn. +) Giả sử mọi chu trình của đều có độ dài chẵn. Ta sẽ chứng minh mọi thành phần liên thông của là đồ thị lưỡng phân và do đó cũng là đồ thị lưỡng phân. Không mất tính tổng quát, xét thành phần liên thông 1 = ( 1, 1) bất kì của , | 1| ≥ 2 và một điểm ∈ 1. ′ Gọi là tập hợp các đỉnh ∈ 1 sao cho tồn tại một đường đi từ đến ′ có độ ′ dài chẵn và 푌 là tập hợp các đỉnh ∈ 1 sao cho tồn tại một đường đi từ đến ′ có độ dài lẻ. Dễ thấy ∈ nên ≠ ∅. Lại có 1 liên thông và | 1| ≥ 2 nên tồn tại đỉnh liền kề với suy ra ∈ 푌. Do đó 푌 ≠ ∅. Ta có ∩ 푌 = ∅. Thật vậy, nếu tồn tại đỉnh ∈ ∩ 푌 thì tồn tại một chu trình đi từ đến sau đó quay lại có độ dài lẻ (mâu thuẫn). ′ Hơn nữa, 1 liên thông nên luôn tồn tại một đường đi từ đến mọi đỉnh ∈ 1. Điều này dẫn tới ∪ 푌 = 1 và do đó, 1 là đồ thị lưỡng phân. II. Định lý Hall Định lý 2.2.1 Hall: Cho đồ thị lưỡng phân = ( 1 ∪ 2, ). Với mỗi tập con 푆 của 1, gọi (푆) là tập các đỉnh thuộc 2 kề với một đỉnh nào đó thuộc 푆. Khi đó, điều kiện cần và đủ để tồn tại một đơn ánh : 1 → 2 sao cho 푣 kề với (푣) là | (푆)| ≥ |푆| ∀ 푆 ⊂ . 16
17. Chứng minh. +) Giả sử tồn tại một đơn ánh : 1 → 2 sao cho 푣 kề với (푣). Dễ thấy, với mọi tập con 푆 ⊂ 1 ta có | (푆)| ≥ | (푆)| = |푆|. +) Giả sử với mọi tập con 푆 ⊂ 1 ta có | (푆)| ≥ |푆|. Ta sẽ chứng minh bằng quy nạp theo | 1|. Với | 1| = 1, ta thấy | ( 1)| ≥ | 1| = 1 nên với ∈ 1 tồn tại đỉnh ∈ 2 sao cho kề với . Do đó : 1 → 2 sao cho ( ) = là đơn ánh thỏa mãn. Giả sử mệnh đề đúng với | 1| < . Ta sẽ chứng minh mệnh đề đúng với | 1| = . Ta xét hai trường hợp sau: TH1: Với mọi tập 푆 ⊂ 1 ta có | (푆)| > |푆|. Lấy một đỉnh 0 ∈ 1. Vì | ({ 0})| ≥ |{ 0}| = 1 nên tồn tại một đỉnh 0 ∈ 2 sao cho 0 , 0 kề nhau. Khi đó, xóa các đỉnh 0, 0 và các cạnh liên quan khỏi đồ thị ′ ′ ′ ta thu được đồ thị con = ( 1 ∪ 2, ′) cũng là đồ thị lưỡng phân, trong đó ′ ′ 1 = 1\{ 0}, 2 = 2\{ 0}. ′ ′ Ta thấy với mọi tập 푆 ⊂ 1 ⊂ 1: | ′(푆)| ≥ | (푆)| − 1 suy ra |푆| ≤ | (푆)|. ′ ′ ′ Hơn nữa, do | 1 | < nên tồn tại một đơn ánh đi từ : 1 → 2 sao cho sao cho 푣 kề với (푣). ( ) nếu ≠ 0 Khi đó, ta có đơn ánh : 1 → 2 xác định bởi ( ) = { . 0 nếu = 0 TH2: Tồn tại một tập ⊂ 1, 푆 ≠ 1 sao cho | ( )| = | |. Khi đó, do tồn tại một đơn ánh 1: → ( ) sao cho 푣 kề với 1(푣). Ta xóa các đỉnh thuộc , ( ) và các cạnh liên quan khỏi đồ thị ta thu được đồ ′ ′ ′ ′ ′ ′ thị con lưỡng phân = ( 1 ∪ 2, ) với 1 = 1\ , 2 = 2\ ( ). Với mọi tập con 푆 ⊂ 1′, ta có | ′(푆)| ≥ |푆|. Thật vậy, nếu | ′(푆)| < |푆| thì | ( ∪ 푆)| = | ( )| + | ′(푆)| < | | + |푆| = | ∪ 푆| (mâu thuẫn). 17
18. ′ ′ ′ Hơn nữa, do | 1 | < nên tồn tại một đơn ánh đi từ 2: 1 → 2 sao cho sao cho 푣 kề với 2(푣). 1( ) nếu ∈ Khi đó, ta có đơn ánh : 1 → 2 xác định bởi ( ) = { . 2( )nếu ∉ Hệ quả 2.2.2: Cho đồ thị lưỡng phân = ( 1 ∪ 2, ). Nếu tồn tại số nguyên dương sao cho ( ) ≥ ≥ ( ) ∀ ∈ 1, ∈ 2 thì tồn tại một đơn ánh : 1 → 2 sao cho kề với ( ). Chứng minh. Với mọi tập 푆 ⊂ 1, ta thấy có ít nhất |푆| cạnh nối từ các đỉnh trong 푆 với các đỉnh trong 2. Mà với mỗi đỉnh ∈ 2 nối được nhiều nhất cạnh, do đó | (푆)| ≥ |푆|. Khi đó, theo định lý Hall ta có điều phải chứng minh. Hệ quả 2.2.3: Cho đồ thị lưỡng phân = ( 1 ∪ 2, ) và số nguyên không âm. Giả sử với mọi tập con khác rỗng 푆 của 1, ta có | (푆)| ≥ |푆| − . Khi đó, tồn tại một đơn ánh : → 2 với ⊂ 1, | | ≥ | 1| − thỏa mãn ( ) kề với . Chứng minh. Với = 0, mệnh đề đã cho chính là định lý Hall. Với > 0, ta thêm đỉnh vào tập 2 ta được tập ′2, từ mỗi đỉnh trong đỉnh này ′ ′ ′ ta nối với tất cả các đỉnh trong 1. Khi đó, ta thu được đồ thị mới = ( 1 ∪ 2, ) là đồ thị lưỡng phân. Xét tập 푆 ⊂ 1, theo cách xây dựng đồ thị ′ ta có | ′(푆)| = | (푆)| + ≥ |푆| − + = |푆|. Do đó, theo định lý Hall, tồn tại một đơn ánh : 1 → 2′ sao cho ( ) kề với . Đặt = { ∈ 1| ( ) ∈ 2}. Ta thấy | | = | ( )| ≥ | ( 1)| − = | 1| − . Khi đó, đơn ánh : → 2 xác định bởi ( ) = ( ) thỏa mãn đề bài. 18
19. III. Ví dụ minh họa Ví dụ 2.3.1. (Bulgarian autumn competition 2023) Cho một đồ thị lưỡng phân đầy đủ = ( ∪ , ), trong đó | | = , | | = 푛 với , 푛 ∈ ℕ. Người ta tô các cạnh trong bởi màu. Chứng minh rằng tồn tại một màu và một tập 푆 có ít nhất + 푛 đỉnh sao cho giữa hai đỉnh trong 푆 luôn có một đường đi mà tất cả các cạnh trong đó đều có màu . Lời giải. Gọi là màu được tô nhiều nhất. Do đồ thị có 2 푛 cạnh nên số cạnh được tô màu lớn hơn hoặc bằng 푛. Thực hiện xóa đi tất cả các cạnh có màu khác, ta thu được đồ thị mới ′. Khi đó, ta sẽ chỉ ra ′ = ( ∪ , ′) có một thành phần liên thông có ít nhất + 푛 đỉnh. Để chứng minh điều này, ta sẽ chỉ ra tồn tại hai đỉnh ∈ và ∈ sao cho ∈ ′ và ( ) + ( ) ≥ + 푛. Giả sử với mọi cạnh ∈ ′ ta có ( ) + ( ) < + 푛. Khi đó ∑ ( ( ) + ( )) < | ′|. ( + 푛) (1). ∈ ′ Mặt khác, ta lại có ∑ ( ( ) + ( )) = ∑ ( )2 + ∑ ( )2 ∈ ′ ∈ ∈ (∑ ( ))2 (∑ ( ))2 | ′|2 | ′|2 ≥ ∈ + ∈ = + 푛 푛 푛 푛 ≥ | ′| ( + ) = | ′|( + 푛) (2). 푛 Ta thấy (1) và (2) mâu thuẫn. Vậy ta có điều phải chứng minh. Ví dụ 2.3.2. Cho đồ thị = ( , ) với | | hữu hạn. Đỉnh 푣 được gọi là “vua” nếu (푣) > (푤) với mọi đỉnh 푤 kề với 푣. Gọi 퐾( ) là tập các đỉnh “vua” trong . | | |퐾( )| 1 Chứng minh rằng |퐾( )| < . Hãy chỉ ra một ví dụ thỏa mãn lim = . 2 | |→∞ | | 2 19
20. Lời giải. Trước hết, ta sẽ chứng minh bổ đề sau: Bổ đề: Cho đồ thị lưỡng phân = ( 1 ∪ 2, ) không có đỉnh cô lập với | 2| > | 1|. Khi đó, tồn tại hai đỉnh ∈ 1 và ∈ 2 kề nhau sao cho ( ) > ( ). Chứng minh. Đặt 1 = { 1, 2, , } và 2 = { 1, 2, , 푛}. Xét ma trận = ( 푖푗) trong đó 푖푗 = 1 nếu hai đỉnh 푖, 푗 kề nhau và 푖푗 = 0 nếu ngược lại. 푖푗 푖푗 Đặt 푖푗 = , 푖푗 = 푛 . Dễ thấy ∑푖,푗 푖푗 = 푛 và ∑푖,푗 푖푗 = . ∑ =1 푗 ∑ =1 푖 Khi đó, ta có ∑푖,푗 푖푗 > ∑푖,푗 푖푗 nên tồn tại cặp (푖, 푗) sao cho 푖푗 > 푖푗 hay 푛 ∑ =1 푗 ( 푗). Bây giờ, ta quay lại với bài toán ban đầu. Đặt 2 = 퐾( ), 1 = \퐾( ). Ta sẽ chứng minh | 2| ≤ | 1| bằng phản chứng. Giả sử | 2| > | 1|. Ta thấy hai đỉnh “vua” không thể kề nhau, nên không có cạnh nào giữa hai đỉnh bất kì trong 2. Ta thực hiện xóa đi các cạnh giữa các cặp đỉnh trong 1, khi đó ta thu ′ ′ được đồ thị lưỡng phân ( 1 ∪ 2, ). Áp dụng bổ đề trên, ta thấy tồn tại ∈ 1, ∈ 2 sao cho ′( ) > ′( ). Điều này dẫn đến ( ) > ( ), mâu thuẫn do đỉnh là “vua”. | | Do đó, ta có | | ≤ | |, suy ra |퐾( )| ≤ | | − |퐾( )|. Vậy |퐾( )| < . 2 1 2 Xét đồ thị lưỡng phân đầy đủ = ( 1 ∪ 2, ) sao cho | 1| = 푛 − 1, | 2| = 푛. Ta thấy 퐾( ) = 1 vì ( ) = 푛 ∀ ∈ 1, ( ) = 푛 − 1 ∀ ∈ 2. Khi đó, ta có |퐾( )| 푛 − 1 1 lim = = . | |→∞ | | 2푛 − 1 2 20