Luận văn Nghiên cứu về đồ thị

Mục lục Lời mở đầu 3 Chương 1 Kiến thức chuẩn bị về đồ thị 5 1.1 Các Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Các Đường, Vòng và Cây . . . . . . . . . . . . . . . . . . . 12 1.3 Các Vòng Hamilton và Chu trình Euler . . . . . . . . . . . . 18 Chương 2 Phương pháp Cơ bản 22 2.1 Phương pháp Xác suất . . . . . . . . . . . . . . . . . . . . 22 2.2 Lý thuyết Đồ thị . . . . . . . . . . . . . . . . . . . . . . . 24 2.3 Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.4 Lý thuyết Số Tổ hợp . . . . . . . . . . . . . . . . . . . . . 30 2.5 Các cặp rời nhau . . . . . . . . . . . . . . . . . . . . . . . 30 Chương 3 Sự tuyến tính của kỳ vọng 32 3.1 Cơ sở . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.2 Các đồ thị tách . . . . . . . . . . . . . . . . . . . . . . . . 33 3.3 Hai kết quả nhanh . . . . . . . . . . . . . . . . . . . . . . 35 3.4 Vectơ cân bằng . . . . . . . . . . . . . . . . . . . . . . . . 36 3.5 Đèn nhấp nháy . . . . . . . . . . . . . . . . . . . . . . . . 38 Chương 4 Bổ đề Địa phương 40 4.1 Bổ đề . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.2 Tính chất B và các tập đa sắc của các số thực . . . . . . . . . 43 1 4.3 Cận dưới cho các số Ramsey . . . . . . . . . . . . . . . . . 44 4.4 Một kết quả hình học . . . . . . . . . . . . . . . . . . . . . 46 4.5 Số arboricity tuyến tính của đồ thị . . . . . . . . . . . . . . 47 4.6 Bước chuyển Latin . . . . . . . . . . . . . . . . . . . . . . 52 4.7 Khía cạnh giải thuật . . . . . . . . . . . . . . . . . . . . . 54 Chương 5 Chứng minh Định lý Weierstrass theo Phương pháp Xác suất 58 5.1 Một số kiến thức xác suất cơ sở chuẩn bị . . . . . . . . . . . 58 5.2 Định lý xấp xỉ Weierstrass . . . . . . . . . . . . . . . . . . 61 5.3 Một đánh giá về tốc độ hội tụ của đa thức Bernstein . . . . . . 64 Kết luận 68 Tài liệu tham khảo 69 2 Lời mở đầu Phương pháp xác suất phát triển mạnh gần đây và trở thành một trong những công cụ được dùng hữu hiệu và rộng rãi để ứng dụng cho tổ hợp. Một trong những lý do chính trong sự phát triển nhanh này là vai trò quan trọng của sự ngẫu nhiên trong Lý thuyết Khoa học Máy tính, lĩnh vực mà gần đây là động lực của nhiều bài toán tổ hợp hấp dẫn. Sự tác động qua lại giữa Toán Rời rạc và Khoa học Máy tính yêu cầu một mảng giải thuật trong tìm tòi về Phương pháp Xác suất trong Tổ hợp và một số vấn đề bước đầu được trình bày trong tài liệu này. Tài liệu vì vậy bao gồm sự nghiên cứu các phương pháp cơ bản cũng như các phương pháp hiện đại ứng dụng trong đó kèm theo một số ý tưởng về giải thuật. Xin nói ngay rằng chúng ta sẽ chủ yếu tìm hiểu về phương pháp cơ bản mà thôi. Phương pháp xác suất cơ bản có thể được mô tả như sau: Nhằm chứng minh sự tồn tại của những cấu trúc tổ hợp với những tính chất chắc chắn nào đó, chúng ta xây dựng một không gian xác suất hợp lý cho cấu trúc đó và chỉ ra rằng những tính chất mong muốn tồn tại với xác suất dương. Phương pháp này được khởi nguồn bởi Paul Erdos, người đóng góp rất nhiều cho sự phát triển của nó trong năm mươi năm qua. Và dường như hợp lý khi gọi nó là "Phương pháp Erdos". Những đóng góp của ông không chỉ đo bằng số các kết quả sâu sắc trong chủ đề này, mà còn bởi nhiều bài toán và dự đoán thú vị điều đòi hỏi nhiều tâm huyết nghiên cứu trong lĩnh vực này. Dường như là không thể viết một quyển sách giáo khoa về phương pháp xác suất; quá nhiều kết quả gần đây cung cấp những lập luận xác suất, và chúng ta không liệt kê tất cả chúng. Điều nhấn mạnh của chúng ta là về phương pháp cơ bản, và chúng ta vì vậy cố gắng miêu tả những ý tưởng, và không phải luôn luôn đưa ra những kết quả tốt nhất có thể nếu việc giải quyết quá đòi hỏi về kĩ thuật, chẳng hạn những kết quả trong nhận xét sau Mệnh đề 4.3.1. Nhiều kết quả là tiệm cận, chúng ta dùng những quy ước tiệm cận chuẩn sau: cho hai hàm f và g, chúng ta viết f = O(g) nếu f ≤ cg cho mọi giá trị đủ lớn của biến của hai hàm, ở đây c là một hằng số dương, chúng ta viết f = Ω(g) nếu g = O(f), viết f = Θ(g) nếu f = O(g) và f = Ω(g). Nếu tỷ số f/g 3 dần tới không khi biến của hai hàm dần tới vô cùng ta viết f = o(g). Cuối cùng, f ∼ g kí hiệu f = (1 + o(1))g, nghĩa là f/g dần tới 1 khi các biến dần tới vô cùng. Luận văn gồm năm chương. Chương đầu tiên trình bày những kiến thức cơ sở về đồ thị. Đây là do chúng ta dùng phương pháp xác suất để giải một số bài toán liên quan dến đồ thị. Các chương sau đi vào những bài toán cụ thể. Chương hai trình bày lời giải một số bài toán nhằm làm rõ phương pháp xác suất. Chương ba áp dụng phương pháp cho lớp các bài toán dùng đến kỳ vọng của biến ngẫu nhiên. Chương bốn trình bày lời giải cho một lớp các bài toán bằng cách dùng Bổ đề Địa phương, chúng ta thu được nhiều kết quả rất thú vị. Chương cuối cùng trình bày áp dụng kĩ thuật xác suất để chứng minh Định lý Weierstrass. Công việc của tác giả như vậy là đọc hiểu tài liệu - chủ yếu bằng tiếng Anh trong hai quyển sách [1], [2] - và trình bày lại theo tiếng Việt. Mặc dù tác giả đã cố gắng, tuy nhiên do khả năng còn hạn chế nên trong quá trình thực hiện luận văn này không tránh khỏi những thiếu sót. Tác giả mong được sự đóng góp ý kiến của các thầy cô giáo, các nhà nghiên cứu và những ai quan tâm đến luận văn này. Cuối cùng, tác giả xin bày tỏ lòng biết ơn chân thành sâu sắc tới Thầy giáo GS. TSKH. Nguyễn Duy Tiến về sự hướng dẫn, chỉ bảo và giúp đỡ tận tình, tạo điều kiện cho tác giả hoàn thành bản luận văn này. Tác giả cũng xin chân thành cảm ơn Ban Giám hiệu Trường Đại học Khoa học Tự nhiên - Đại học Quốc gia Hà Nội, Ban Chủ nhiệm Khoa Toán - Cơ - Tin và các thầy cô giáo, cán bộ, công nhân viên của Nhà trường; Ban Giám hiệu Trường THPT Kim Liên đã giúp đỡ, tạo điều kiện thuận lợi trong suốt thời gian học tập và quá trình hoàn thành luận văn./. Hà Nội, tháng 10 năm 2009 Tác giả Quản Anh Tuấn 4 Chương 1 Kiếnthứcchuẩnbịvềđồthị 1.1 Các Định nghĩa Một đồ thị G là một cặp có thứ tự các tập hợp rời nhau (V,E) sao cho E là tập con của tập gồm các cặp không có thứ tự của V . Trừ khi nó được cho tường minh theo cách khác, chúng ta chỉ xét những đồ thị hữu hạn, đó là, V và E luôn luôn hữu hạn. Tập V là tập đỉnh và tập E là tập cạnh. Nếu G là một đồ thị, thì V = V (G) là tập đỉnh, E = E(G) là tập cạnh. Một cạnh {x, y} được nói là nối các đỉnh x, y và kí hiệu bởi xy. Như vậy xy hay yx biểu thị cùng một cạnh; các đỉnh x và y gọi là các đỉnh cuối của cạnh này. Nếu xy ∈ E(G), thì x và y là các đỉnh kề nhau hay lân cận với nhau, và các đỉnh x và y là liên thuộc với cạnh xy. Hai cạnh là kề nhau nếu chúng có đúng một đỉnh cuối chung. Chúng ta thường không nghĩ đồ thị như một cặp có thứ tự mà như một tập các đỉnh mà một số cặp đỉnh được nối với nhau bởi các cạnh. Chúng ta nói rằng G′ = (V ′, E′) là đồ thị con của G nếu V ′ ⊂ V và E′ ⊂ E. Trong trường hợp này ta viết G′ ⊂ G. Nếu mọi cạnh của G mà nối hai đỉnh của V ′ đều chứa trong G′ thì ta nói G′ là đồ thị con cảm sinh của G và viết là G′ = G[V ′]. Một đồ thị con của G mà chứa mọi đỉnh của G gọi là đồ thị con dẫn xuất của G hay một nhân tử của G. Chúng ta cũng thường tạo những đồ thị mới từ những đồ thị cũ bằng cách xóa đi hay thêm vào các cạnh và đỉnh. Nếu W ⊂ V (G), thì G −W = G[V \ W ] là đồ thị con của G nhận được bằng cách xóa đi W và tất cả các cạnh liên thuộc với các đỉnh của nó. Tương tự, nếu E′ ⊂ E(G) thì G − E′ = (V (G), E(G) \ E′). NếuW = {w} và E′ = {xy}, thì các kí hiệu này đơn giản viết là G−w và G− xy . Tương tự, nếu x và y là các đỉnh không kề nhau của G, thì G+ xy nhận từ G bằng cách nối x và y. 5 Nếu x là một đỉnh của đồ thị thì đôi khi chúng ta viết x ∈ G thay cho x ∈ V (G). Số thứ tự của G là số các đỉnh của G, kí hiệu bới |G|. Kí hiệu này cũng dùng cho số các phần tử của một tập hợp: |X| biểu thị số các phần tử của tập X . Vậy |G| = |V (G)|. Cỡ của G là số các cạnh của G; nó được kí hiệu bởi e(G). Chúng ta viết Gn cho một đồ thị tùy ý có thứ tự n. Tương tự, G(n,m) là kí hiệu cho một đồ thị tùy ý có thứ tự n và cỡm. Cho hai tập con rời nhau U vàW của tập đỉnh của một đồ thị, chúng ta viết E(U,W ) cho tập các cạnh của U −W , đó là, tập các cạnh nối mỗi đỉnh của U với một đỉnh của W . Cũng vậy, e(U,W ) = |E(U,W )| là số các cạnh của U −W . Nếu chúng ta muốn nhấn mạnh đồ thị ban đầu của chúng ta là G thì ta đặt EG(U,W ) và eG(U,W ). Hai đồ thị là đẳng cấu nếu có một ánh xạ giữa các tập đỉnh của chúng mà bảo toàn tính liên thuộc. Như vậyG = (V,E) gọi là đẳng cấu vớiG′ = (V ′, E′) nếu có một song ánh φ : V → V ′ sao cho nếu xy là một cạnh của G thì φ(x)φ(y) là một cạnh của G′. Rõ ràng, hai đồ thị đẳng cấu thì có cùng thứ tự và cỡ. Thông thường, chúng ta không phân biệt giữa các đồ thị đẳng cấu, trừ khi chúng ta xét những đồ thị có tập đỉnh được đánh dấu hay ghi nhãn (ví dụ, đồ thị con từ một đồ thị đã cho). Theo quy ước này, nếu G vàH là hai đồ thị đẳng cấu, thì chúng ta viết G ∼= H hay đơn giản G = H . Cỡ của một đồ thị thứ tự n là ít nhất 0 và nhiều nhất (n 2 ) . Rõ ràng, với mỗi m, 0 ≤ m ≤ (n2), có một đồ thị G(n,m). Một đồ thị có thứ tự n với cỡ(n 2 ) được gọi là n-đồ thị đầy đủ và kí hiệu bởi Kn; một n-đồ thị rỗng En có thứ tự n và không cạnh. Trong Kn mọi đỉnh đều kề nhau, trong khi với En không có đỉnh nào kề nhau. Đồ thịK1 = E1 gọi là tầm thường. Vì En gần giống với kí hiệu tập các cạnh của đồ thị, chúng ta thường dùng kí hiệu Kn cho tập rỗng với thứ tự n, chú ý rằng nó là phần bù của đồ thị đầy đủ. Tổng quát, với đồ thị G = (V,E) phần bù của G là đồ thị G = (V, V (2)−E); như vậy, hai đỉnh là kề nhau trongG nếu và chỉ nếu nó không kề nhau trong G. Tập các đỉnh kề của x ∈ G, lân cận của x, được ký hiệu bởi Γ(x). Đôi khi chúng ta nói Γ(x) là lân cận mở của x, và Γ(x) ∪ {x} là lân cận đóng của x. Cũng vậy, x ∼ y nếu x là đỉnh kề của y. Như vậy y ∈ Γ(x), x ∈ Γ(y), x ∼ y, y ∼ x là tương đương, mỗi một trong chúng biểu thị xy là một 6 cạnh. Bậc của x là d(x) = |Γ(x)|. Nếu chúng ta muốn nhấn mạnh rằng đồ thị ban đầu là G, thì chúng ta viết ΓG(x), dG(x); quy ước tương tự dùng cho một hàm phụ thuộc vào đồ thị ban đầu G. Như vậy nếu x ∈ H = G[W ], thì ΓH(x) = {y ∈ H : xy ∈ E(H)} = ΓG(x) ∩W. Bậc nhỏ nhất của đồ thịG được kí hiệu bởi δ(G) và bậc lớn nhất được kí hiệu bởi∆(G). Một đỉnh bậc 0 được gọi là đỉnh cô lập. Nếu δ(G) = ∆(G) = k, đó là, mọi đỉnh của G có bậc k, thì G được nói là k-chính quy hay chính quy bậc k. Một đồ thị là chính quy nếu nó là k-chính quy với k nào đó. Một đồ thị 3-chính quy được nói là lập phương. Nếu một nhân tử của G mà mọi đỉnh của nó có bậc r thì ta gọi nó là một r-nhân tử của G. Chẳng hạn 1-nhân tử là một đồ thị con dẫn xuất của G mà mọi đỉnh của nó có bậc 1. Nếu V (G) = {x1, x2, . . . , xn} thì {d(xi)}ni=1 là dãy bậc của G. Thường chúng ta xếp các đỉnh theo cách mà dãy bậc nhận được theo cách này là đơn điệu tăng hay đơn diệu giảm, ví dụ, δ(G) = d(x1) ≤ . . . ≤ d(xn) = ∆(G). Do mỗi cạnh có hai đỉnh cuối, tổng của các bậc chính xác là hai lần số cạnh: n∑ 1 d(xi) = 2e(G). (1) Đặc biệt, tổng của các bậc là chẵn: n∑ 1 d(xi) ≡ 0 (mod 2). (2) Nhận xét cuối đôi khi được gọi là bổ đề rung tay, do nó biểu thị rằng tổng số lần rung tay là chẵn. Tương đương, (2) phát biểu rằng tổng số các đỉnh bậc lẻ là chẵn. Chúng ta thấy từ (1) rằng δ(G) ≤ b2e(G)/nc và ∆(G) ≥ d2e(G)/ne. ở đây bxc kí hiệu số nguyên lớn nhất không lớn hơn x và dxe = −b−xc kí hiệu số nguyên nhỏ nhất không nhỏ hơn x. Một đường là một đồ thị P có dạng V (P ) = {x0, x1, . . . , xl}, E(P ) = {x0x1, x1x2, . . . , xl−1xl}. Đường P này thường được kí hiệu bởi x0x1 . . . xl. Các đỉnh gọi là các đỉnh cuối của P , l gọi là độ dài của P . Chúng ta nói rằng P là một đường từ x0 tới 7 xl, hay một đường x0− xl. Dĩ nhiên P cũng là một đường từ xl đến x0, hay đường xl− x0. Đôi khi để nhấn mạnh rằng P được xét khi đi từ x0, chúng ta gọi x0 là đỉnh đầu và xl là đỉnh cuối của P . Một đường với đỉnh đầu x gọi là một x-đường. Thuật ngữ độc lập sẽ được dùng trong liên hệ với các đỉnh, cạnh và đường của một đồ thị. Một tập của các đỉnh (cạnh) gọi là độc lập nếu không có hai phần tử nào của nó là kề nhau; cũng vậy,W ⊂ V (G) bao gồm các đỉnh độc lập nếu G(W ) là một đồ thị rỗng. Một tập các đường là độc lập nếu cho hai đường tùy ý mỗi đỉnh thuộc cả hai đường là điểm cuối của cả hai. Như vậy P1, P2, . . . , Pk là các đường x− y độc lập nếu V (Pi) ∩ V (Pj) = {x, y} với i 6= j. Các đường Pi cũng được nói là tự rời nhau. Có vài khái niệm liên quan đến các đường của một đồ thị. Một di độngW của một đồ thị là một dãy các đỉnh và cạnh x0, e1, x1, e2, . . . , el, xl, ở đây ei = xi−1xi, 0 < i ≤ l. Theo thuật ngữ trên,W là một di động x0−xl và được kí hiệu bởi x0x1 . . . xl; độ dài củaW là l.W này được gọi là một vệt nếu mọi cạnh của dãy đều phân biệt. Chú ý rằng một đường là một di động với các đỉnh phân biệt. Một vệt mà các đỉnh cuối của nó là trùng nhau (một vệt đóng) được gọi là một chu trình. Rõ hơn, một chu trình là một vệt đóng mà không phân biệt các đỉnh cuối và hướng, ví dụ, hai tam giác với một đỉnh duy nhất chung đưa ra hai chu trình với sáu cạnh. Nếu một di độngW = x0x1 . . . xl với l ≥ 3, x0 = xl và các xi, 0 < i < l, phân biệt lẫn nhau và x0 thìW được gọi là một vòng. Để đơn giản vòng này được kí hiệu là x1x2 . . . xl. Chú ý rằng kí hiệu này khác với một đường ở chỗ xlx1 cũng là một cạnh của vòng. Một vòng không có đỉnh bắt đầu cũng như hướng, như vậy x1x2 . . . xl, xlx1 . . . xl−1, x2x3 . . . x1 cùng kí hiệu một vòng. Chúng ta thường dùng Pl để kí hiệu cho một đường và Cl để kí hiệu cho một vòng. Chúng ta gọi C3 là một tam giác, C4 là một tứ giác và C5 là một ngũ giác; Cl được gọi là một l-vòng. Một vòng là chẵn (lẻ) nếu độ dài của nó là chẵn (lẻ). Sẽ ít rắc rối hơn nếu dùng P l, Cl cho những đường và vòng tổng quát, còn cho những đường và vòng cụ thể ta dùng P1, P2, . . . , C1, C2, . . . Tuy nhiên, nhằm tuân theo cách dùng chỉ số dưới được chấp nhận rộng rãi, chúng ta cũng chọn chỉ số dưới. Hy vọng rằng những quy ước này sẽ không dẫn đến hiểu lầm nào. 8 Trước khi tiếp tục các định nghĩa, chúng ta đưa ra hai kết quả đối với các vòng. Cái đầu tiên đưa bởi Veblen vào 1912. Định lý 1.1.1 Tập các đỉnh của một đồ thị có thể phân chia thành các vòng nếu, và chỉ nếu, mọi đỉnh có bậc chẵn. Chứng minh. Điều kiện cần là rõ ràng, do nếu một đồ thị là hợp của các vòng không có cạnh chung và các đỉnh cô lập, thì một đỉnh chứa trong k vòng có bậc 2k, còn mỗi đỉnh cô lập có bậc 0. Giả sử rằng mỗi đỉnh của đồ thị đều có bậc chẵn và e(G) > 0. Làm thế nào chúng ta có thể tìm được một vòng đơn trongG? Lấy x0x1 . . . xl là một đường có độ dài lớn nhất l trong G. Do x0x1 ∈ e(G), chúng ta có d(x0) ≥ 2. Nhưng như thế thì phải có một lân cận khác y ngoài x1; thêm nữa, chúng ta phải có y = xi với xi nào đó, 2 ≤ i ≤ l, do nếu khác thì yx0x1 . . . xl sẽ là một đường có độ dài l + 1. Từ đó, chúng ta tìm được một vòng: x0x1 . . . xi. Tìm thấy một vòng, gọi là C1, việc chúng ta phải làm là lặp lại thủ tục này tiếp và tiếp nữa. Để thiết lập điều này, đặt G1 = G, như thế C1 là một vòng trong G1 và xác định G2 = G1 − E(C1). Mỗi đỉnh thuộc G2 có bậc chẵn, vậy hoặc E(G2) = ∅, hoặc G2 chứa một vòng C2. Tiếp tục theo cách này, chúng ta tìm được các vòng không có cạnh chung C1, C2, . . . , Cs thỏa mãn E(G) = ∪si=1E(Ci).  Để chứng minh kết quả thứ hai, một Định lý đẹp của Matel từ 1907, chúng ta sẽ dùng nhận xét (1) và bất đẳng thức Cauchy. Định lý 1.1.2 Mỗi đồ thị thứ tự n với cỡ lớn hơn bn2/4c chứa một tam giác. Chứng minh. Giả sử phản chứng rằng G là một đồ thị thứ tự n mà không chứa một tam giác nào. Thế thì Γ(x)∩Γ(y) = ∅ với mỗi cạnh xy ∈ E(G), nên d(x) + d(y) ≤ n. Cộng các bất đẳng thức cho tất cả e(G) cạnh xy của G, chúng ta nhận được∑ x∈G d(x)2 ≤ ne(G). (3) 9 Theo (1) và bất đẳng thức Cauchy, (2e(G))2 = ( ∑ x∈G d(x))2 ≤ n( ∑ x∈G d(x)2). Vậy, theo (3), (2e(G))2 ≤ n2e(G), chứng tỏ rằng e(G) ≤ n2/4.  Đánh giá của kết quả này nhận thấy dễ dàng là tốt nhất có thể được. Định lý của Matel được mở rộng lớn bởi Turán vào 1941: Định lý này của Turán là điểm bắt đầu của lý thuyết đồ thị cực trị. Cho các đỉnh x, y. Khoảng cách của chúng d(x, y) là độ dài ngắn nhất của các đường x− y. Nếu không có đường x− y nào thì d(x, y) =∞. Một đồ thị gọi là liên thông nếu mọi cặp các đỉnh phân biệt {x, y} đều có một đường từ x đến y. Chú ý rằng một đồ thị liên thông của ít nhất hai đỉnh không thể chứa một đỉnh cô lập. Một đồ thị con liên thông lớn nhất, tức là không có một đồ thị con liên thông nào chứa nó thực sự, là một thành tố của đồ thị. Một đỉnh cắt là một đỉnh mà sự xóa bỏ nó làm tăng số các thành tố của đồ thị. Tương tự, một cầu là một cạnh mà sự xóa bỏ nó làm tăng số thành tố của đồ thị. Như vậy một cạnh là một cầu nếu sự xóa bỏ nó làm mất tính liên thông của đồ thị. Một đồ thị không chứa vòng nào là một rừng, hay một đồ thị không vòng; một cây là một rừng liên thông. Mối quan hệ giữa cây và rừng nghe bớt gượng gạo nếu ta thấy rằng một rừng là một tập gồm các cây rời nhau; nói khác đi, một rừng là một đồ thị mà mỗi thành tố của nó là một cây. Một đồ thị G là một đồ thị hai nhánh với các lớp đỉnh V1, V2 nếu V (G) = V1 ∪ V2, V1 ∩ V2 = ∅ và mọi cạnh nối một đỉnh của V1 với một đỉnh của V2. Ta cũng nói rằng G có hai nhánh (V1, V2). Tương tự ta nói G là r-nhánh với các lớp đỉnh V1, V2, . . . , Vr (hay r-nhánh (V1, V2, . . . , Vr)) nếu V (G) = V1∪V2∪ . . .∪Vr, Vi∩Vj = ∅, 1 ≤ i < j ≤ r, và không có cạnh nào nối hai đỉnh của cùng một lớp. Kí hiệuK(n1, . . . , nr)dùng cho một đồ thị r-nhánh đầy đủ: nó chứa ni đỉnh trong lớp thứ i và hai đỉnh bất kì trong hai lớp phân biệt đều được nối với nhau. Để đơn giản, chúng ta thường viết Kp,q thay thế cho K(p, q) và Kr(t) thay thế cho K(t, . . . , t). Chúng ta sẽ viếtG∪H = (V (G)∪V (H), E(G)∪E(H)) và kG cho hợp của k bản 10 sao rời nhau củaG. Chúng ta nhận được đồ thị nốiG+H từG∪H bằng cách thêm tất cả các cạnh giữa G vàH . Theo đó,K2,3 = E2 + E3 = K2 +K3 vàKr(t) = Et + . . .+ Et = Kt + . . .+Kt. Có một dạng đồ thị gần đây được nói tới nhiều. Một siêu đồ thị là một cặp (V,E) sao cho V ∩ E = ∅ và E là tập con của tâp P(V ), tập mạnh của V , đó là tập gồm tất cả các tập con của V . Thực tế, có một tương ứng đơn giản 1 − 1 giữa lớp các siêu đồ thị và lớp các đồ thị hai nhánh với các lớp đỉnh V,E trong đó x ∈ V được nối với siêu cạnh S ∈ E nếu x ∈ S. Cho một họ A = {A1, A2, . . . , Am} các tập con của một tậpX . Một tập gồmm phần tử, mỗi cái từ mỗi Ai được gọi là tập các đại diện phân biệt của họ A. Hệ tập A tự nhiên xác định một đồ thị 2-nhánh với các lớp đỉnh V1 = A và V2 = X trong đó Ai nối với một số x ∈ X chứa trong Ai. Ta nói rằng có một tương xứng từ V1 dến V2. Theo định nghĩa một đồ thị không chứa một nút, một "cạnh" nối một đỉnh với chính nó; nó cũng không chứa các đa cạnh, đó là, một vài cạnh nối cùng hai đỉnh. Trong một đa đồ thị các đa nút và đa cạnh là được phép; một nút là một cạnh đặc biệt. Khi có những lo ngại về hiểu nhầm, các đồ thị được gọi là các đồ thị đơn. Chúng ta sẽ chủ yếu làm việc với các đồ thị đơn. Nếu các cạnh là các cặp định hướng của các đỉnh thì chúng ta nhận được đồ thị có hướng hay đa đồ thị có hướng. Một cặp có thứ tự (a, b) được gọi là một cạnh hướng từ a đến b, hay một cạnh bắt đầu từ a và kết thúc tại b, và được kí hiệu là −→ ab hay đơn giản là ab. Các khái niệm được xác định cho đồ thị dễ dàng chuyển qua đa đồ thị, đồ thị có hướng, đa đồ thị có hướng. Chẳng hạn một vệt có hướng trong một đa đồ thị có hướng là một dãy xen kẽ các đỉnh và cạnh: x0, e1, x1, e2, . . . , el, xl , sao cho ei bắt đầu tại xi−1 và kết thúc tại xi. Cũng vậy, một đỉnh x của một đồ thị có hướng có một bậc ngoài và một bậc trong: bậc ngoài d+(x) là số các cạnh bắt đầu từ x, bậc trong d−(x) là số các cạnh kết thúc tại x. Một đồ thị định hướng là một đồ thị có hướng nhận được từ một đồ thị bằng cách định hướng mỗi cạnh của nó, đó là, gán cho cạnh ab hướng −→ ab hoặc −→ ba. Như vậy một đồ thị định hướng là một đồ thị có hướng trong đó nhiều nhất một trong hai trường hợp −→ ab và −→ ba xảy ra. 11 Chú ý rằng Định lý 1.1.1 có một sự biến đồi tự nhiên cho đa đồ thị có hướng như sau: Tập cạnh của một đa đồ thị có hướng có thể phân chia thành những vòng có hướng nếu và chỉ nếu mọi đỉnh có cùng bậc ngoài và bậc trong, đó là, d+(x) = d−(x)với mọi đỉnh x. Để thấy điều kiện đủ, điều chúng ta phải chú ý là, như trước, nếu đồ thị của chúng ta có một cạnh, thì nó phải có một vòng có hướng. 1.2 Các Đường, Vòng và Cây Với những khái niệm định nghĩa mới đây, chúng ta có thể bắt đầu đưa ra vài kết quả về đồ thị. Dù những kết quả này không phải là khó, chúng ta cũng vẫn gọi đó là những định lý. Định lý 1.2.1 Cho x là một đỉnh của đồ thị G và gọiW là một thành tố của đồ thị G mà chứa x. Các khẳng định sau đây là đúng. (a)W = {y ∈ G : G chứa một đường x− y}. (b)W = {y ∈ G : G chứa một vệt x− y}. (c)W = {y ∈ G : d(x, y) <∞}. (d) Cho u, v ∈ V = V (G), đặt uRv nếu uv ∈ E(G), và đặt R˜ là quan hệ tương đương nhỏ nhất trên V chứaR. Thế thìW là một lớp tương đương của x. Kết quả nhỏ này chứng tỏ rằng mỗi đồ thị là một hợp các đỉnh rời nhau của các thành tố của nó (tương đương, mỗi đỉnh chứa trong một thành tố duy nhất), và rằng mỗi cạnh là một cầu nếu nó không chứa trong một vòng nào. Định lý 1.2.2 Một đồ thị là hai nhánh nếu và chỉ nếu nó không chứa một vòng lẻ. Chứng minh. Giả sử G là hai nhánh với các lớp đỉnh V1, V2. Đặt x1x2 . . . xl là một vòng trong G. Chúng ta có thể giả sử rằng x1 ∈ V1. Thế thì x2 ∈ V2, x3 ∈ V1, và có: xi ∈ V1 nếu và chỉ nếu i là lẻ. Do xl ∈ V2, chúng ta thấy rằng l là chẵn. Bây giờ giả sử G không chứa một vòng lẻ nào. Do một đồ thị là hai nhánh nếu và chỉ nếu mỗi thành tố của nó cũng vậy, chúng ta có thể giả sử rằng G là liên thông. Lấy một đỉnh x ∈ V (G) và đặt V1 = {y ∈ G : d(x, y) là lẻ}, 12 V2 = V \ V1. Không có cạnh nào nối hai đỉnh của cùng một lớp Vi, do nếu không thì G sẽ chứa một vòng lẻ. Như vậy G là hai nhánh.  Một đồ thị hai nhánh (V1, V2) có nhiều nhất |V1||V2| cạnh, vậy một đồ thị hai nhánh thứ tự n có nhiều nhất maxkk(n− k) = bn2/4c cạnh. Giá trị lớn nhất đạt được ứng với đồ thị đầy đủKbn/2c,dn/2e. Theo Định lý 1.2.2, bn2/4c cũng là cỡ lớn nhất của một đồ thị thứ tự n không chứa các vòng lẻ. Thực tế, như chúng ta thấy trong Định lý 1.1.2, đó là số cạnh tốt nhất có thể để đồ thị không chứa một tam giác. Định lý 1.2.3 Một đồ thị là một rừng nếu và chỉ nếu cho mỗi cặp {x, y} của hai đỉnh phân biệt, nó chứa nhiều nhất là một đường x− y. Chứng minh. Cho G là đồ thị có nhiều nhất một đường với mỗi cặp hai đỉnh phân biệt. Nếu x1x2 . . . xl là một vòng trong đồ thị G, thì x1x2 . . . xl và x1xl là hai đường của G. Như thế G không có vòng và là một rừng. Ngược lại, cho G là một rừng, và giả sử có P1 = x0x1 . . . xl và P2 = x0y1 . . . ykxl là hai đường x0−xl phân biệt của đồ thịG. Lấy i+1 là chỉ số nhất thỏa mãn xi+1 6= yi+1 và đặt j là chỉ số nhỏ nhất thỏa mãn j ≥ i và yj+1 là một đỉnh của P1, có yj+1 = xh. Thế thì xixi+1 . . . xhyjyj−1 . . . yi+1 là một vòng trong G. Mâu thuẫn này chứng tỏ G có nhiều nhất một đường với mỗi cặp hai điểm phân biệt.  Định lý 1.2.4 Các khẳng định sau là tương đương cho một đồ thị G. (a) G là một cây. (b) G là một đồ thị liên thông nhỏ nhất, đó là, G là liên thông và nếu xy ∈ E(G), thìG−xy là không liên thông. (Nói cách khác,G là liên thông và mỗi cạnh là một cầu.) (c) G là đồ thị không vòng lớn nhất, đó là, G là không vòng và nếu x và y là các đỉnh không kề nhau của G, thì G+ xy là một đồ thị có vòng. Chứng minh. Giả sử G là một cây. Cho mỗi cạnh xy ∈ E(G), đồ thị G−xy không thể chứa một đường x−y, gọi là xz1z2 . . . zky, do nếu khác thì G chứa một vòng xz1z2 . . . zky. Như vậy G − xy là không liên thông; và có G là đồ thị liên thông nhỏ nhất. Tương tự, nếu x và y là hai đỉnh không 13 kề của một cây G, thì G chứa một đường x− y, gọi là xz1z2 . . . zky, và có G+ xy chứa một vòng xz1z2 . . . zky. Như vậy G+ xy chứa một vòng, và G là đồ thị không vòng lớn nhất. Tiếp theo giả sửG là một đồ thị liên thông nhỏ nhất. NếuG chứa một vòng xz1z2 . . . zky, thì G− xy vẫn là liên thông, do trong di động u− v bất kì trong G cạnh xy có thể thay thế bởi đường xz1z2 . . . zky. Vì điều này mâu thuẫn với tính nhỏ nhất của G, chúng ta kết luận rằng G là không vòng và nó là một cây. Cuối cùng, giả sử rằngG là đồ thị không vòng lớn nhất. G có là liên thông? Có, do nếu x và y thuộc hai thành tố khác nhau, việc thêm cạnh xy vào G sẽ không tạo ra một vòng xz1z2 . . . zky, do nếu khác thì đường xz1z2 . . . zky là thuộcG. Như vậyG không thể có nhiều hơn một thành tố và nó là một cây.  Hệ quả 1.2.5 Mọi đồ thị liên thông chứa một cây dẫn xuất, đó là, một cây chứa mọi đỉnh của đồ thị. Chứng minh. Lấy một đồ thị con liên thông nhỏ nhất chứa mọi đỉnh của đồ thị.  Có vài cách dựng đơn giản một cây dẫn xuất của một đồ thị liên thông G. Chúng ta giới thiệu hai trong số đó. (1) Lấy một đỉnh x và đặt Vi = {y ∈ G : d(x, y) = i}, i = 0, 1, . . .. Chú ý rằng nếu yi ∈ Vi, i > 0, và xz1z2 . . . zi−1yi là một đường (sự tồn tại của nó được đảm bảo do cách định nghĩa của Vi), thì d(x, zj) = j cho mỗi j, 0 0, có một đỉnh y′ ∈ Vi−1 nối với y. (Dĩ nhiên, nói chung đỉnh y′ này không duy nhất, nhưng với mỗi y 6= x ta chỉ lấy duy nhất một y′). Đặt T là đồ thị con của G với tập đỉnh V và tập cạnh E(T ) = {yy′ : y 6= x}. Thế thì T là liên thông, do mỗi đỉnh y ∈ V − {x} được nối với x bởi một đường yy′y′′ . . . x. Hơn nữa, T là không vòng, do nếuW là một tập con bất kì của V và ω là một đỉnh trong W xa nhất từ x, thì ω được nối với nhiều nhất một đỉnh trongW . Như vậy T là một cây dẫn xuất. Những lập luận trên chỉ ra rằng nếu k = maxyd(x, y), chúng ta có Vi 6= ∅ cho 0 ≤ i ≤ k và V = V (G) = ∪k0Vi. Đến lúc này thật khó để bỏ qua 14 các khái niệm sau: diamG = maxx,yd(x, y) được gọi là đường kính của G và radG = minxmaxyd(x, y) được gọi là bán kính của G. Nếu chúng ta chọn x ∈ G với k = maxyd(x, y) = radG, thì cây dẫn xuất T cũng có bán kính k. (2) Một biến đổi nhẹ nhàng cách xây dựng trên của T tiến hành như sau. Lấy x ∈ G và lấy T1 là đồ thị con của G với đỉnh đơn x này. Thế thì T1 là một cây. Giả sử chúng ta đã dựng các cây T1 ⊂ T2 ⊂ . . . ⊂ Tk ⊂ G, ở đây Ti có thứ tự i. Nếu k < n = |G| thì bởi sự liên thông của G có một đỉnh y ∈ V (G) \ V (Tk) mà kề (trong G) với một đỉnh z ∈ Tk. Lấy Tk+1 nhận được từ Tk bằng cách thêm vào nó đỉnh y và cạnh yz. Thế thì Tk+1 là liên thông và do yz không thể là một cạnh trong Tk, nó cũng là không vòng. Như vậy Tk+1 cũng là một cây, và dãy T0 ⊂ T1 ⊂ . . . có thể tiếp tục đến Tn. Cây Tn này khi đó sẽ là một cây dẫn xuất của G. Các cây dẫn xuất xây dựng bởi các cách trên có thứ tự n (dĩ nhiên) và cỡ n− 1. Trong cách xây dựng thứ nhất có một tương ứng 1− 1 giữa V −{x} và E(T ), cho bởi y 7→ yy′. Và trong cách xây dựng thứ hai e(Tk) = k− 1 cho mỗi k, do e(T1) = 0 và Tk+1 có hơn một cạnh so với Tk. Theo Định lý 1.2.4 mỗi cây có một cây dẫn xuất duy nhất, là chính nó, chúng ta đi tới kết quả sau, đưa bởi Listing vào 1862. Hệ quả 1.2.6 Một cây có thứ tự n có cỡ n − 1. Một rừng có thứ tự n với k thành tố có cỡ n− k. Phần đầu của hệ quả này là một đặc điểm cốt lõi của cây. Cụ thể, một đồ thị thứ tự n là một cây nếu và chỉ nếu nó là liên thông và có cỡ n− 1. Hệ quả 1.2.7 Một cây thứ tự ít nhất 2 có ít nhất hai đỉnh bậc 1. Chứng minh. Đặt d1 ≤ d2 ≤ . . . ≤ dn là dãy bậc của một cây T thứ tự n ≥ 2. Do T là liên thông, δ(T ) = d1 ≥ 1. Vậy nếu T có nhiều nhất một đỉnh bậc 1, theo (1) và Hệ quả 1.2.6 ta sẽ có 2n− 2 = 2e(T ) = n∑ 1 di ≥ 1 + 2(n− 1).  15 Một bài toán cơ bản trong lý thuyết tối ưu yêu cầu một cách tìm dễ dàng một cây dẫn xuất của một đồ thị với một tính chất đặc biệt nào đó. Cho một đồ thị G = (V,E) và một hàm giá trị dương f xác định trên các cạnh, f : E(G) → R+, tìm một đồ thị con liên thông dẫn xuất T = (V,E′) của G để f(T ) = ∑ xy∈E′ f(xy) là nhỏ nhất. Chúng ta gọi đồ thị con liên thông dẫn xuất T như thế là một đồ thị con dẫn xuất kinh tế. Ta không cần phải tưởng tượng nhiều để dịch điều này ra một bài toán “cuộc sống thực”. Giả sử các ngôi làng nào đó được nối với một nguồn nước được đặt tại một trong các ngôi làng đó. Hệ thống đường dẫn gồm các ống dẫn liên thông các tháp nước của hai ngôi làng. Với mỗi hai ngôi làng chúng ta biết giá làm đường ống nối hai làng đó, và mọi đường ống đều có thể làm được. Chúng ta tìm hệ thống đường ống dẫn kinh tế như thế nào? Để giải bài toán trên bằng phương pháp đồ thị, đặt G là một đồ thị mà tập các đỉnh của nó là tập các ngôi làng và mỗi cạnh xy là một đường ống có thể được làm để nối hai làng x và y; kí hiệu giá của mỗi đường ống dẫn là f(xy). Thế thì hệ thống đường ống dẫn tương ứng với một đồ thị con liên thông dẫn xuất của G, tức là một cây dẫn xuất của G, do hệ thống phải là kinh tế nên T sẽ là đồ thị con dẫn xuất liên thông nhỏ nhất. Đồ thị con liên thông dẫn xuất T phải là đồ thị con liên thông nhỏ nhất, do nếu khác thì sẽ có một cạnh α mà sự xóa bỏ nó không làm mất tính liên thông của T , như thế T − α sẽ là một đồ thị con dẫn xuất kinh tế hơn. Như vậy T là một cây dẫn xuất kinh tế của G. Tương ứng với các đặc điểm và các cách xây dựng khác nhau của một cây dẫn xuất, chúng ta có vài cách tìm đơn giản một cây dẫn xuất kinh tế; chúng ta sẽ trình bày bốn trong số các phương pháp này. (1) Cho G và f : E(G) → R+, chúng ta chọn một trong những cạnh rẻ nhất của G, đó là, cạnh α mà với nó f(α) là nhỏ nhất. Mỗi cạnh của dãy sẽ được chọn từ trong những cạnh còn lại rẻ nhất chỉ với một quy tắc là chúng ta sẽ không chọn tất cả các cạnh của cùng bất kì một vòng nào; đó là, đồ thị con của G tạo bởi các cạnh được chọn là không vòng. Quá trình kết thúc nếu không cạnh nào có thể thêm vào tập E′ các cạnh đã được chọn mà không tạo ra một vòng. Thế thì T1 = (V (G), E ′) là đồ thị con không vòng lớn nhất của G, theo Định lý 1.2.4(c) thì T1 chính là một cây dẫn xuất của G. 16 (2) Phương pháp này dựa trên thực tế rằng ta sẽ không dùng một cạnh đắt đỏ trừ khi nó cần để đảm bảo tính liên thông của đồ thị con của G. Như vậy chúng ta xóa từng cạnh đắt nhất mà sự xóa bỏ nó không làm mất tính liên thông của đồ thị còn lại. Theo Định lý 1.2.4(b) quá trình kết thúc thì ta được cây dẫn xuất T2. (3) Lấy một đỉnh x1 của G và chọn một cạnh ít đắt nhất liên thuộc với nó, gọi là x1x2. Sau đó chọn một trong những cạnh ít đắt nhất có dạng xix, ở đây 1 ≤ i ≤ 2 và x /∈ {x1, x2}. Với các đỉnh vừa tìm x1, x2, . . . , xk và một cạnh xixj, i < j, với mỗi đỉnh xj mà j ≤ k, chọn một trong những cạnh ít đắt nhất có dạng xix, gọi là xixk+1, ở đây 1 ≤ i ≤ k và xk+1 /∈ {x1, x2, . . . , xk}. Quá trình kết thúc sau khi chúng ta chọn được n− 1 cạnh. Kí hiệu bởi T3 cây dẫn xuất được cho bởi các cạnh này. (4) Phương pháp này chỉ áp dụng nếu không có hai đường ống nào cùng một giá. Ưu điểm của phương pháp này là mỗi ngôi làng tự quyết định được cho mình và bắt đầu xây dựng mà không cần lo xem các ngôi làng khác sẽ làm gì. Dĩ nhiên, mỗi làng sẽ bắt đầu xây dựng ống dẫn rẻ nhất kết thúc tại làng mình. Có thể xảy ra rằng cả hai làng x và y cùng xây ống dẫn xy; trong trường hợp này họ sẽ gặp nhau ở giữa và kết thúc với chỉ một đường đơn được tạo thành từ x đến y. Như vậy ở cuối của mỗi chặng vài làng nào đó được nối với nhau bằng ống dẫn nhưng toàn bộ hệ thống ống dẫn chưa cần là liên thông. Đến chặng sau mỗi nhóm làng nối với nhau bởi các ống dẫn, tìm ống dẫn rẻ nhất đi tới một làng trong nhóm và bắt đầu xây ống dẫn đơn đó. Thủ tục giống như thế được lặp lại cho đến khi nhận được một hệ thống liên thông các ống dẫn. Rõ ràng, các làng sẽ không bao giờ xây tất cả các ống dẫn của cùng một vòng, nên hệ thống ống dẫn cuối cùng sẽ là một cây dẫn xuất. Định lý 1.2.8 Mỗi một trong bốn phương pháp trên sản xuất ra một cây dẫn xuất kinh tế. Nếu không có hai cạnh nào cùng giá, thì có cây dẫn xuất kinh tế duy nhất. Chứng minh. Chọn một cây dẫn xuất kinh tế T của G mà có cùng số cạnh nhiều nhất có thể với T1, ở đây T1 là cây dẫn xuất được chọn theo phương pháp đầu tiên. Giả sử rằng E(T1) 6= E(T ). Các cạnh của T1 được chọn từng cái một: lấy 17 xy là cạnh đầu tiên của T1 mà không phải là một cạnh của T . Thế thì T chứa một đường xy duy nhất, gọi là P . Đường P này có ít nhất một cạnh, gọi là uv, mà không thuộc vào T1, do nếu khác thì T1 sẽ chứa một vòng. Khi xy đã được chọn như một cạnh của T1, thì uv cũng sẽ là một ứng viên. Vì xy đã được chọn mà không phải là uv, cạnh xy không thể đắt hơn uv; đó là, f(xy) ≤ f(uv). Thế thì T ′ = T − uv + xy là một cây dẫn xuất, và do f(T ′) = f(T )−f(uv) +f(xy) ≤ f(T ), cây mới T ′ là một cây dẫn xuất kinh tế của G. (Dĩ nhiên, bất đẳng thức này chứng tỏ rằng f(T ′) = f(T ) và f(xy) = f(uv).) Cây T ′ này có nhiều cạnh chung với T1 hơn T , mâu thuẫn với cách chọn của T . Vậy T = T1, và T1 thực sự là một cây dẫn xuất kinh tế. Sự biến đổi nhẹ nhàng chứng minh trên sẽ chỉ ra rằng các cây dẫn xuất T2 và T3, xây dựng theo phương pháp thứ hai và thứ ba, cũng là kinh tế. Giả sử rằng không có hai cạnh nào có cùng giá; đó là, f(xy) 6= f(uv) với xy 6= uv. Lấy T4 là một cây dẫn xuất xây dựng bởi phương pháp thứ tư và lấy T là một cây dẫn xuất kinh tế. Giả sử rằng, T 6= T4, và lấy xy là cạnh đầu tiên không thuộc T mà ta chọn cho T4. Cạnh xy đã được chọn, do nó là cạnh rẻ nhất của G nối một đỉnh của tập con F của T4 với một đỉnh bên ngoài F . Đường x− y trong T có một cạnh uv nối một đỉnh của F với một đỉnh bên ngoài F , nên f(xy) < f(uv). Tuy nhiên, điều này là không thể, do T ′ = T − uv + xy là một cây dẫn xuất của G và f(T ′) < f(T ). Vậy T = T4. Điều này chỉ ra rằng T4 thực sự là một cây dẫn xuất kinh tế. Hơn nữa, do cây dẫn xuất xây dựng bởi phương pháp thứ tư là duy nhất, cây dẫn xuất kinh tế là duy nhất nếu không có hai cạnh nào có cùng một giá.  1.3 Các Vòng Hamilton và các Chu trình Euler Bài toán nhà buôn du lịch rất giống với bài toán cây dẫn xuất kinh tế được thảo luận ở phần trên, tuy nhiên sự tương tự chỉ là bề ngoài. Một nhà buôn làm một tua qua n thành phố, cuối cùng ông ấy phải trở về trụ sở nơi bắt đầu khởi hành. Giá của hành trình giữa hai thành phố bất kì là đã biết. Bài toán yêu cầu tìm một giải thuật hiệu quả xác định một chuyến đi có giá ít đắt nhất. (Vì chúng ta không thảo luận về giải thuật, chúng ta bỏ qua thuật ngữ “hiệu quả”; nói nôm na, một giải thuật hiệu quả nếu số lần tính toán là một đa thức của số 18 các đỉnh.) Dù nhiều tài liệu đã xem xét bài toán này do tính chất quan trọng áp dụng trong thực hành của lời giải, vẫn chưa biết biết liệu rằng có hay không một giải thuật hiệu quả để tìm một con đường ít đắt nhất. Trong một phiên bản khác của bài toán nhà buôn, con đường được yêu cầu là một vòng, đó là, nhà buôn không được phép đi qua cùng một thành phố hai lần (ngoại trừ thành phố có trụ sở, nơi ông ấy bắt đầu và kết thúc hành trinh). Một vòng chứa tất cả các đỉnh của đồ thị gọi là một vòng Hamilton của đồ thị. Nguồn gốc của thuật ngữ này là một trò chơi phát minh năm 1857 bởi Ngài William Rowan Hamilton cơ sở trên việc xây dựng một vòng chứa tất cả các đỉnh thuộc đồ thị của một hình mười hai mặt. Một đường Hamilton của đồ thị là một đường chứa tất cả các đỉnh của đồ thị, Một đồ thị chứa một vòng Hamilton gọi là Hamiltonian. Thực tế, các đường và vòng Hamilton trên các đồ thị đặc biệt đã được tìm hiểu kĩ càng trước khi Hamilton đề nghị trò chơi của ông ấy. Cụ thể, câu đố về tua của quân ngựa trên một bàn cờ, được phân tích sâu bởi Euler vào 1759, yêu cầu một vòng Hamilton trong đồ thị mà các đỉnh của nó là 64 ô vuông của bàn cờ trong đó hai đỉnh là kề nhau nếu quân ngựa có thể nhảy từ ô này đến ô kia. Nếu hạn chế thêm trong phiên bản thứ hai của bài toán nhà buôn du lịch, mỗi chuyến đi giữa hai thành phố chỉ có hai giá là 1 và∞, thì câu hỏi là liệu có hay không một đồ thị chứa một vòng Hamilton tạo bởi các cạnh với các chuyến đi giá 1 chứa một vòng Hamilton. Thậm chí trường hợp đặc biệt này của bài toán nhà buôn là không giải được: không có một giải thuật hiệu quả được biết để xây dựng một vòng Hamilton, và cũng không biết là có hay không một giải thuật như vậy. Nếu giá của chuyến đi giữa hai thành phố bất kì là như nhau, nhà buôn của chúng ta sẽ không khó khăn để tìm tua ít đắt nhất: một phép thế bất kì của n− 1 thành phố (thành phố thứ n có trụ sở) sẽ thỏa mãn. Nhằm thiết lập một một dãy các chuyến đi yêu cầu cho nhà buôn của chúng ta, chúng ta phải phân tích Kn thành tập các vòng Hamilton các cạnh rời nhau. Liệu rằng giá trị của n có thể là bao nhiêu? DoKn là một (n− 1)-chính quy và vòng Hamilton là 2-chính quy, một điều kiện cần là n− 1 phải chẵn, đó là, n phải lẻ. Điều kiện cần này cũng được suy ra từ tính chất là e(Kn) = 1 2n(n − 1) và một vòng Hamilton chứa n cạnh, nênKn phải là tập của 1 2(n− 1) vòng Hamilton. 19 Bây giờ chúng ta giả sử rằng n là lẻ, n ≥ 3. Xóa một đỉnh của Kn chúng ta thấy rằng nếuKn là một tập của 1 2(n− 1) vòng Hamilton thìKn−1 là một tập của 1 2(n− 1) đường Hamilton. (Thật vậy, n− 1 phải là chẵn nếu Kn−1 là hợp của một số vòng Hamilton nào đó, do e(Kn−1) = 12(n− 1)(n− 2) và một đường Hamilton trong Kn−1 có n − 2 cạnh.) Trong sự phân tích của Kn−1 vào 12(n−1) đường Hamilton này, mỗi đỉnh là đỉnh cuối của chính xác một đường Hamilton. (Thực vậy, điều này đúng với mỗi sự phân tích Kn−1 thành 1 2(n− 1) đường Hamilton các cạnh rời nhau, do mỗi đỉnh x củaKn−1 có bậc lẻ, nên ít nhất một đường Hamilton phải kết thúc tại x.) Cho nên, nếu chúng ta thêm một đỉnh mới vàoKn−1 và mở rộng một đường Hamilton trong Kn−1 thành một vòng Hamilton trongKn, thì chúng ta sẽ nhận được sự phân tíchKn thành 1 2(n− 1) vòng Hamilton các cạnh rời nhau. Như vậy chúng ta vừa chứng minh kết quả sau. Định lý 1.3.1 Với n ≥ 3 đồ thị đầy đủ Kn là phân tích được thành các vòng Hamilton các cạnh rời nhau nếu và chỉ nếu n là lẻ. Với n ≥ 2 đồ thị đầy đủ Kn phân tích được thành các đường Hamilton nếu và chỉ nếu n là chẵn. Kết quả trên chỉ ra rằng nếu n là lẻ thì chúng ta có thể xâu chuỗi các vòng Hamilton với nhau để nhận được một chu trình chứa tất cả các cạnh của Kn. Tổng quát, một chu trình của G chứa tất cả các cạnh của E(G) được gọi là một chu trình Euler của G. Tương tự, một vệt mà chứa tất cả các cạnh gọi là một vệt Euler. Một đồ thị là Eulerian nếu nó có một chu trình Euler. Các chu trình và vệt Euler được đặt tên theo Leonard Euler, người, vào 1736, nghiên cứu các đồ thị chứa chúng. Khi Euler là giáo sư toán tại St. Petersburg, ông bị lôi cuốn bởi bài toán bảy cây cầu trên sông Pregel. Định lý 1.3.2 Một đồ thị liên thông không tầm thường có một chu trình Euler nếu và chỉ nếu mọi đỉnh của nó có bậc chẵn. Một đồ thị liên thông có một vệt Euler từ x đến y 6= x nếu và chỉ nếu chỉ có x và y là các đỉnh bậc lẻ. Chứng minh. Các điều kiện cần là rõ ràng. Nếu đồ thị G có một chu trình Euler và x xảy ra k lần trong dãy x1, x2, . . . , xm, thì d(x) = 2k. 20 Chúng ta chứng minh điều kiện đủ của mệnh đề thứ nhất bằng cách quy nạp theo số các cạnh. Nếu không có cạnh nào, thì không có gì phải chứng minh, như vậy chúng ta thực hiện bước quy nạp tiếp theo. GọiG là một đồ thị liên thông không tầm thường trong đó mọi đỉnh đều có bậc chẵn. Do e(G) ≥ 1, chúng ta thấy rằng δ(G) ≥ 2, nên theo Hệ quả 1.2.7,G chứa một vòng. Gọi C là một chu trình trong G với số cạnh lớn nhất. Giả sử C không là Eulerian. Vì G là liên thông, C chứa một đỉnh x thuộc một thành tố không tầm thườngH củaG−E(C). Mỗi đỉnh thuộcH có bậc chẵn trong H , nên theo giả thiết quy nạp, H chứa một chu trình Euler D. Các chu trình C vàD có các cạnh rời nhau và có một đỉnh chung, nên chúng có thể liên kết để tạo thành một chu trình có nhiều cạnh hơn C. Vì điều này mâu thuẫn với sự lớn nhất của e(C), chu trình C phải là Eulerian. Bây giờ giả sử rằngG là liên thông và chỉ có x, y là các đỉnh bậc lẻ. GọiG∗ là đồ thị nhận được từ G bằng cách thêm vào nó đỉnh u và các cạnh ux, uy. Thế thì, theo phần đầu, G∗ có một chu trình Euler C∗. Rõ ràng, C∗ − u là một vệt Euler từ x đến y.  21 Chương 2 Phươngphápcơbản 2.1 Phương pháp Xác suất Phương pháp xác suất là công cụ hữu hiệu để xử lý nhiều vấn đề trong toán rời rạc. Nói nôm na, phương pháp tiến hành như sau: cố gắng chứng minh một cấu trúc có một tính chất mong muốn nào đó, người ta định nghĩa một không gian xác suất hợp lý cho các cấu trúc và sau đó chứng tỏ tính chất mong muốn là đúng trong không gian này với xác suất dương. Phương pháp minh họa tốt nhất qua các ví dụ. Đây là một ví dụ đơn giản. Số Ramsey R(k, l) là số nguyên nhỏ nhất n sao cho bất kỳ cách tô hai màu nào các cạnh của đồ thị đầy đủ n đỉnh Kn bởi màu đỏ và xanh cũng có một Kk đỏ (đồ thị con k đỉnh đầy đủ mọi cạnh đều đỏ) hoặc một Kl xanh. Ramsey (1929) chỉ ra rằng R(k, l) là hữu hạn với bất kỳ hai số nguyên k, l. Chúng ta nhận được cận dưới cho số Ramsey chéo R(k, k). Mệnh đề 2.1.1 Nếu (n k ) 21−( k 2) n. Vì vậy R(k, k) > b2k/2c với mọi k ≥ 3. Chứng minh. Xét một cách tô hai màu các cạnh của Kn nhận được bằng cách tô mỗi cạnh độc lập màu xanh hoặc màu đỏ, ở đây vai trò mỗi màu là như nhau. Với mỗi tập cố định R có k đỉnh, gọi AR là sự kiện (biến cố) đồ thị con lấy từ Kn trên R là đơn màu (hoặc mọi cạnh đều đỏ, hoặc mọi cạnh đều xanh). Rõ ràng Pr(AR) = 2 1−(k2) . Do có (n k ) cách chọn cho R, xác suất để ít nhất một sự kiện AR xảy ra nhiều nhất là (n k ) 21−( k 2) < 1. Vì vậy, với xác suất dương, không có sự kiện AR nào xảy ra và sẽ có cách tô màu cho Kn mà không có đơn màu Kk nào, nghĩa là R(k, k) > n. Chú ý rằng nếu k ≥ 3 và ta lấy n = b2k/2c thì (n k ) 21−( k 2) < 2 1+k2 k! . nk 2k2/2 < 1 và có 22 R(k, k) > b2k/2c, mọi k ≥ 3.  Ví dụ đơn giản này biểu thị cốt lõi của phương pháp xác suất. Để chứng minh sự tồn tại của một cách tô màu tốt chúng ta không giới thiệu một cách tô tường minh nhưng chỉ ra mà không dựng rằng nó tồn tại. Ví dụ này xuất hiện trong tài liệu của P. Erdos từ 1947. Mặc dù Szele có ứng dụng phương pháp xác suất trong một bài toán tổ hợp khác, đưa ra trong chương 3, đã có trong 1943, Erdos chắc chắn đã là người đầu tiên hiểu đầy đủ sức mạnh của phương pháp này và ứng dụng nó thành công trong nhiều năm vào các bài toán số. Ta có thể, dĩ nhiên, phát biểu rằng xác suất là công cụ thiết yếu của chứng minh ở trên. Một chứng minh đơn giản tương đương có thể bày tỏ bằng cách đếm: Chúng ta kiểm tra rằng tổng số cách tô màu hai màu của Kn lớn hơn số cách tô hai màu mà có một đơn màuKk. Hơn nữa, do phần lớn những không gian xác suất trong việc tìm hiểu những bài toán tổ hợp xét trong không gian hữu hạn, cách liệt kê này áp dụng cho hầu hết những ứng dụng của phương pháp xác suất cho toán rời rạc. Tuy nhiên, trong thực hành, xác suất là cốt lõi. Phương pháp xác suất có một khía cạnh thuật toán thú vị. Xét, ví dụ, chứng minh của Mệnh đề 2.1.1 chỉ ra rằng có một cách tô hai màu các cạch của Kn không có đơn màu K2 log2 n. Chúng ta có thể tìm cách tô màu như vậy? Vì tổng số cách tô màu là hữu hạn, vì vậy chúng ta có thể thử tất cả chúng đến khi tìm được cái mong muốn. Tuy nhiên, thủ tục này yêu cầu 2( n 2) bước, tốn rất nhiều thời gian với cỡ [= (n 2 ) ] của bài toán. Chứng minh của bài toán chỉ ra một cách tô màu dường như tốt, hiệu quả. Đó là vì với k lớn, nếu n = b2k/2c thì ( n k ) .21−( k 2) < 21+k/2 k! .( n 2k/2 )k ≤ 2 1+k/2 k!  1. Thế nên, một cách tô màu bất kỳ của Kn dường như không chứa đơn màu K2 log2 n. Điều đó có nghĩa là, vì một lý do nào đó, chúng ta phải giới thiệu một cách tô hai màu cho các cạnh của K1024 mà không chứa đơn màu K20 nào, chúng ta có thể đơn giản tạo một cách tô màu ngẫu nhiên bằng cách tung đồng xu hai mặt (1024 2 ) lần. Chúng ta sẽ nhận được một cách tô màu đáng tin: xác suất để có một đơn màu K20 nhỏ hơn 211 20! . Do đó, trong một vài trường hợp, phương pháp xác suất không xây dựng đưa ra một giải thuật hiệu quả. 23 Phương pháp xác suất là một công cụ mạnh và hiệu quả của lý thuyết Đồ thị và Tổ hợp. Nó cũng là ứng dụng hàng đầu trong Lý thuyết Số và trong Hình học Tổ hợp. Gần đây nó được ứng dụng nhiều hơn trong việc phát triển kĩ thuật giải thuật hiệu quả và trong việc tìm hiểu những bài toán máy tính khác nhau. 2.2 Lý thuyết Đồ thị Một giải đấu trên tập V của n người chơi là một sự định hướng T = (V,E) của các cạnh của đồ thị đầy đủ trên tập n đỉnh của V . Vì vậy, với mọi hai phần tử x, y của V thì hoặc (x, y) thuộc E, hoặc (y, x) thuộc E nhưng không cả hai. Cái tên "giải đấu" là tự nhiên, vì mỗi cặp tham gia đấu tay đôi và (x, y) thuộc E nếu x thắng y. Chúng ta nói T có tính chất Sk nếu mỗi tập k người chơi có một người (của V ) đánh bại tất cả k người này. Ví dụ, tam giác liên thông T3 = (V,E), ở đây V = {1, 2, 3} và E = {(1, 2), (2, 3), (3, 1)} có tính chất S1. Liệu rằng mỗi số nguyên k sẽ có giải đấu T (nhiều hơn k người chơi) có tính chất Sk? ý tưởng cơ bản (và tự nhiên) là nếu n đủ lớn như một hàm của k thì giải đấu ngẫu nhiên trên tập n người chơi của V sẽ có tính chất Sk.Một giải đấu ngẫu nhiên là như sau. Chúng ta đưa ra một giải đấu T trên V bằng cách chọn, với mỗi 1 ≤ i < j ≤ n, hoặc cạnh (i, j) hoặc cạnh (j, i), ở đây mỗi một trong hai cách chọn là tương đương. Giả sử rằng theo cách này, mỗi một trong các giải đấu trên V là bình đẳng, không gian xác suất được xét là đối xứng. Rất đáng chú ý rằng chúng ta thường dùng trong ứng dụng những không gian xác suất đối xứng. Trong trường hợp này, chúng ta đôi khi coi những phần tử của không gian như những phần tử ngẫu nhiên, mà không mô tả cụ thể phân phối xác suất. Vì vậy, ví dụ, trong chứng minh của Mệnh đề 2.1.1, những cách tô hai màu củaKn được xét thì mỗi cách tô màu là bình đẳng với nhau. Tương tự, trong chứng minh của kết quả đơn giản sau đây chúng ta tìm hiểu về giải đấu ngẫu nhiên trên V . Định lý 2.2.1 Nếu (n k ) (1 − 2−k)n−k < 1 thì có một giải đấu n đỉnh có tính chất Sk. Chứng minh. Xét một giải đấu ngẫu nhiên của tập V = {1, 2, . . . , n}. 24 Với mỗi tập conK cố định có k đỉnh của V , đặtAK là sự kiện không có đỉnh nào đánh bại mọi thành viên củaK. Rõ ràng Pr(AK) = (1−2−k)n−k. Đây là vì mỗi đỉnh cố định v ∈ V −K, xác suất để v không đánh bại mọi thành viên của K là 1− 2−k, và tất cả n− k cách chọn khác nhau có thể của v là độc lập. Kéo theo Pr( ∨ K⊂V |K|=k AK) ≤ ∑ K⊂V |K|=k Pr(AK) = ( n k ) (1− 2−k)n−k < 1. Từ đó, với xác suất dương không sự kiện AK nào xảy ra, tức là có một giải đấu n đỉnh có tính chất Sk. Gọi f(k) kí hiệu số nhỏ nhất có thể của các đỉnh của giải đấu mà có tính chất Sk. Do (n k ) < (en k )k và (1 − 2−k)n−k < e−(n−k)/2k, Định lý 1.2.1 chứng tỏ rằng f(k) ≤ k22k(ln 2)(1 +o(1)). Không khó khăn kiểm tra rằng f(1) = 3 và f(2) = 7. Theo chứng minh của Szekeres, f(k) ≥ c1k2k.  Một tập trội của đồ thị không liên thông G = (V,E) là tập U ⊆ V sao cho mọi v ∈ V − U có ít nhất một đỉnh kề trong U . Định lý 2.2.2 Cho G = (V,E) là đồ thị n đỉnh, bậc nhỏ nhất δ > 1. Thế thì G có tập trội với nhiều nhất n1+ln(δ+1) δ+1 đỉnh. Chứng minh. Lấy p ∈ [0, 1] là số tuỳ ý. Chọn một cách ngẫu nhiên và độc lập mỗi đỉnh của V với xác suất p . Lấy X là tập (ngẫu nhiên) tất cả các đỉnh được chọn và đặt Y = YX là tập mà mọi đỉnh thuộc V − X mà không có đỉnh kề trongX . Giá trị kỳ vọng củaX rõ ràng là np. Với mỗi đỉnh v ∈ V,Pr(v ∈ Y ) = Pr(v và các đỉnh kề không trongX) ≤ (1− p)δ+1. Do kỳ vọng của tổng các biến ngẫu nhiên bằng tổng các kỳ vọng (thậm chí nếu chúng không độc lập) và do biến ngẫu nhiên |Y | có thể viết như tổng các biến ngẫu nhiên chỉ số χv(v ∈ V ), với χv = 1 nếu v ∈ V và χv = 0 nếu khác, chúng ta kết luận rằng kì vọng của |X| + |Y | nhiều nhất là np+n(1− p)δ+1. Suy ra, có ít nhất một cách chọn củaX ⊆ V sao cho |X| + |YX| ≤ np + n(1 − p)δ+1. Tập U = X ∪ YX rõ ràng là tập trội mà lực lượng của nó nhiều nhất là số này. Các lập luận trên đúng với p ∈ [0, 1] tuỳ ý. Để nhận kết quả chúng ta 25 dùng tính toán sơ cấp. Để tiện ta đánh giá 1 − p ≤ e−p (điều này đúng mọi p không âm và xấp xỉ tốt khi p nhỏ) để có đánh giá đơn giản hơn |U | ≤ np+ ne−p(δ+1). Lấy đạo hàm về phải theo p và cho bằng không, giá trị nhỏ nhất của vế phải đạt tại p = ln(δ + 1)/(δ + 1). Lấy p là giá trị này trong dòng đầu của chứng minh, ta có |U | ≤ n1+ln(δ+1) δ+1 như đã nêu.  Ba ý tưởng đơn giản nhưng quan trọng được thể hiện trong chứng minh cuối. Thứ nhất là sự tuyến tính của kỳ vọng; những kết quả đẹp được thảo luận trong chương 3. Thứ hai, có lẽ, tinh tế hơn, là sự sửa đổi sau khi thực hiện lần đầu tiên. Cách chọn ngẫu nhiên không cung cấp ngay một tập trội U mong muốn; nó chỉ cung cấp tập X , tập mà sai khác một ít (bằng cách thêm vào tập YX) để đưa ra tập trội mong muốn. Thứ ba là cách chọn của p. Chúng ta muốn tạo một lựa chọn ngẫu nhiên nhưng không biết xác suất p nào được dùng. Chúng ta cứ tiến hành chứng minh, đến cuối sẽ tìm p để đạt kết quả tối ưu. ý tưởng thứ tư là phép tính tiệm cận. Để đánh giá các kết quả, tiện hơn trong nhiều tình huống dùng đánh giá 1 − p ≤ e−p, đưa ra một đánh giá sáng sủa và dễ tính hơn là tính đúng. Chúng ta muốn tiệm cận của min np+ n(1− p)δ+1 khi p chạy khắp [0, 1]. Điểm cực tiểu đúng p = 1− (δ+1)−1/δ là khó làm việc và trong nhiều trường hợp tương tự không thể tìm được cực tiểu. Tiện hơn, chúng ta đưa ra một sai khác nhỏ, 1 − p ≤ e−p, là một đánh giá đẹp. Đây là một phần nghệ thuật của phương pháp xác suất. Liệu chúng ta có bị sai khác quá nhiều? Câu trả lời phụ thuộc vào câu hỏi ban đầu. Với δ = 3 đánh giá của chúng ta đưa đến |U | ≤ 0.596n trong khi tính toán chính xác hơn đưa đến |U | ≤ 0.496n, có lẽ là khác biệt nhiều. Với δ lớn cả hai cách đưa đến tiệm cận n ln δ δ . Kết hợp điều này với vài ý tưởng của Podderyugin và Matula, chúng ta có một giải thuật rất hiệu quả để quyết định xem liệu một đồ thị không liên thông đã cho có là n 2 -cạnh kết nối. Một lát cắt trong đồ thịG = (V,E) là cách chia tập các đỉnh thành hai tập rời nhau khác rỗng V = V1 ∪ V2. Nếu v1 ∈ V1 và v2 ∈ V2, ta nói lát cắt tách v1 và v2. Cỡ của lát cắt là số các cạnh mà một đỉnh thuộc V1 còn một đỉnh thuộc V2. Thực tế chúng ta xác định lát cắt theo các cạnh này. Số cạnh-kết nối 26 của G là số nhỏ nhất các cỡ của các lát cắt. Bổ đề sau là theo Podderyugin và Matula (một cách độc lập). Bổ đề 2.2.3 ChoG = (V,E) là đồ thị bậc nhỏ nhất δ và cho V = V1∪V2 là lát cắt có cỡ nhỏ hơn δ. Thế thì mỗi tập trội U của G có đỉnh trong V1 và V2. Chứng minh. Giả sử điều này sai và U ⊆ V1. Chọn ngẫu nhiên một đỉnh của V2 và lấy v1, v2, . . . , vδ là δ đỉnh kề của nó. Với mỗi i, xác định cạnh ei của lát cắt đã cho như sau; nếu vi ∈ V1 thì ei = {v, vi} nếu không vi ∈ V2 và do U là tập trội có ít nhất một đỉnh u ∈ U sao cho {u, vi} là một cạnh; lấy u này, và đặt ei = {u, vi}. δ cạnh e1, e2, . . . , eδ là phân biệt và đều nằm trong lát cắt đã cho, trái với giả sử cỡ của nó nhỏ hơn δ. Điều này hoàn thành chứng minh.  2.3 Tổ hợp Một siêu đồ thị là một cặp H = (V,E), ở đây V là một tập hữu hạn mà các phần tử của nó gọi là các đỉnh, còn E là họ các tập con của V , gọi là các cạnh. Nó là n-đều nếu mỗi cạnh bao gồm đúng n đỉnh. Chúng ta nói H có tính chất B, hay hai sắc nếu có cách tô hai màu của V sao cho không có cạnh nào là đơn màu. Gọi m(n) là số cạnh nhỏ nhất có thể của siêu đồ thị n-đều mà không có tính chất B. Mệnh đề 2.3.1 Mỗi siêu đồ thị n-đều với ít hơn 2n−1 cạnh đều có tính chất B. Từ đóm(n) ≥ 2n−1. Chứng minh. Gọi H = (V,E) là một siêu đồ thị n-đều với ít hơn 2n−1 cạnh. Tô màu ngẫu nhiên V bởi hai màu. Với mỗi e ∈ E, gọi Ae là sự kiện e là đơn màu. Rõ ràng Pr(Ae) = 2 1−n . Từ đó Pr( ∨ e∈E Ae) ≤ ∑ e∈E Pr(Ae) < 1 và có cách tô hai màu không có cạnh đơn màu.  Cận trên tốt nhất đã biết chom(n) được tìm bằng cách dùng lập luận xác 27 suất "trên đầu của nó". Cơ bản là, các tập trở thành ngẫu nhiên và mỗi cách tô màu xác định một sự kiện. Cố định V với v điểm, ở đây chúng ta sẽ tối ưu v sau. Đặt χ là cách tô màu với a điểm cùng một màu, b = v − a điểm cùng màu kia. Gọi S ⊆ V là một n-tập được chọn đều. Khi đó Pr(S là đơn màu ứng với χ) = (a n ) + (b n )(v n ) . Chúng ta giả sử v là chẵn cho tiện. Vì (y n ) là lồi, biểu thức này nhỏ nhất khi a = b. Vậy Pr(S là đơn màu ứng với χ) ≥ p ở đây chúng ta đặt p = 2 (v/2 n )(v n ) cho tiện trình bày. Bây giờ đặt S1, . . . , Sm là các n-tập được chọn đều và độc lập,m sẽ tính sau. Với mỗi cách tô màu χ đặt Aχ là sự kiện không có Si nào đơn màu. Bởi sự độc lập của các Si, Pr(Aχ) ≤ (1− p)m. Có 2v cách tô màu nên Pr( ∨ χ Aχ) ≤ 2v(1− p)m. Khi đại lượng này nhỏ hơn 1 thì tồn tại S1, . . . , Sm để không cóAχ nào đúng; nghĩa là S1, . . . , Sm không là hai sắc và như vậym(n) ≤ m. Chúng ta trước hết dùng bất đẳng thức 1 − p ≤ e−p. Cái này đúng với mọi số dương p và các vế hoàn toàn gần nhau khi p nhỏ. Khi m = [ v ln 2 p ] thì 2v(1 − p)m < 2ve−mp ≤ 1 nên m(n) ≤ m. Bây giờ chúng ta cần tìm v để cực tiểu v/p. Chúng ta có thể xem p như là xác suất để lấy n bi trắng từ một bình chứa v/2 bi đen và v/2 trắng, lấy mẫu không hoàn lại. Khi 28 ước lượng p bởi 2−n+1, xác suất cho lấy mẫu có hoàn lại, xấp xỉ này sẽ cho m ∼ v2n−1(ln 2). Khi v nhỏ hơn, xấp xỉ này trở nên kém chính xác và vì chúng ta muốn cực tiểum, sự tương đương trở thành thiết yếu. Chúng ta dùng xấp xỉ thứ hai p = 2 (v/2 n )(v n ) = 21−n n−1∏ i=0 v − 2i v − i ∼ 2 1−ne−n 2/2v vì khi v  n3/2, ước lượng v−2i v−i = 1− iv +O( i 2 v2 ) = e− i v +O( i 2 v2 ) . Tính toán sơ cấp đưa đến v = n2/2 cho giá trị tối ưu. Điều này đưa đến kết quả sau của Erdos (1964). Định lý 2.3.2 m(n) < (1 + o(1)) e ln 2 4 n22n. Cho F = {Ai, Bi}hi=1 là họ các tập con của tập tuỳ ý. Ta gọi F là một (k, l)-hệ nếu |Ai| = k, |Bi| = l với mọi 1 ≤ i ≤ h, Ai ∩ Bi = ∅ và Ai ∩ Bj 6= ∅ với mọi i, j phân biệt, 1 ≤ i, j ≤ h. Bollobás (1965) chứng minh kết quả sau, cái có nhiều mở rộng và ứng dụng thú vị. Định lý 2.3.3 Nếu F = {(Ai, Bi)}hi=1 là một (k, l)-hệ thì h ≤ (k+l k ) . Chứng minh. Đặt X = ⋃h i=1(Ai ∪ Bi) và xét một thứ tự ngẫu nhiên pi của X . Với mỗi i, 1 ≤ i ≤ h, gọi Xi là sự kiện tất cả phần tử của Ai đứng trước tất cả phần tử của Bi trong thứ tự này. Rõ ràng Pr(Xi) = 1/ (k+l k ) . Dễ kiểm tra rằng các sự kiện Xi là đôi một xung khắc. Giả sử khẳng định sai và pi là thứ tự trong đó mọi phần tử Ai đứng trước mọi phần tử của Bi và mọi phần tử của Aj đứng trước mọi phần tử của Bj . Không mất tổng quát có thể coi phần tử cuối củaAi không xuất hiện sau phần tử cuối củaAj . Nhưng trong trường hợp này, mọi phần tử của Ai đứng trước mọi phần tử của Bj trái giả thiết Ai∩Bj 6= ∅. Từ đó cácXi là đôi một xung khắc, như đã nêu. Kéo theo 1 ≥ Pr(∨hi=1Xi) = ∑hi=1 Pr(Xi) = h/(k+lk ), hoàn thành chứng minh.  Định lý 2.3.3 đẹp, chẳng hạn xét họ F = {(A,X \A) : A ⊂ X, |A| = k}, X = {1, 2, . . . , k + l}. 29 2.4. Lý thuyết Số Tổ hợp Một nhóm con A của nhóm abel G gọi là tổng tự do nếu (A+A)∩A = ∅, tức là không có a1, a2, a3 ∈ A để a1 + a2 = a3. Định lý 2.4.1 [Erdos (1965a)] Mỗi tập B = {b1, . . . , bn} gồm n số nguyên khác không chứa tập con A tổng tự do mà cỡ |A| > 13n. Chứng minh. Lấy p = 3k + 2 là nguyên tố, thỏa mãn p > 2max1≤i≤n|bi|, và đặt C = {k+ 1, k+ 2, . . . , 2k+ 1}. Nhận thấy rằng C là tập con tổng tự do của nhóm cyclic Zp và |C| p−1 = k+1 3k+1 > 1 3 . Ta chọn ngẫu nhiên số nguyên x, 1 ≤ x < p, theo phân phối đều trên tập {1, 2, . . . , p − 1}, và xác định {d1, . . . , dn} bởi di ≡ xbi (mod p), 0 ≤ di < p. Hiển nhiên, với mỗi i cố định, 1 ≤ i ≤ n, khi x chạy khắp các số 1, 2, . . . , p − 1 thì di chạy khắp các số khác không của Zp và có Pr(di ∈ C) = |C| p− 1 > 1 3 . Từ đó, kỳ vọng của số các phần tử bi sao cho di ∈ C lớn hơn n3 . Dẫn đến, có một x, 1 ≤ x n3 , sao cho xa (mod p) ∈ C với mọi a ∈ A. A rõ ràng tổng tự do bởi nếu a1 + a2 = a3 với a1, a2, a3 ∈ A thì xa1 + xa2 ≡ xa3 (mod p), trái tính chất là C là tổng tự do của Zp. Điều này hoàn thành chứng minh.  2.5 Các cặp rời nhau Cho F là họ các tập con rời nhau của X = {1, 2, . . . , n}. Ký hiệu d(F) là số các cặp rời nhau, tức là d(F) = |{(F, F ′) : F, F ′ ∈ F, F ∩ F ′ = ∅}|. Định lý 2.5.1ChoF là họm = 2(1/2+δ)n các tập con củaX = {1, 2, . . . , n}, với δ > 0. Thế thì d(F) < m2− δ2 2 (4) 30 Chứng minh. Giả sử (4) sai và lấy độc lập t thành viên A1, A2, . . . , At của F có lặp lại ngẫu nhiên, t là số dương lớn được chọn sau. Ta chỉ ra rằng với xác suất dương |A1 ∪ A2 . . . ∪ At| > n/2 và vẫn hợp này là rời với nhiều hơn 2n/2 tập con phân biệt của X . Sự mâu thuẫn chứng tỏ (4). Thực vậy, Pr(|A1 ∪ . . . ∪At| ≤ n/2) ≤ ∑ S⊂X,|S|≥n/2 Pr(Ai ⊂ S, i = 1, . . . , t) ≤ 2n(2n/2/2(1/2+δ)n)t = 2n(1−δt). (5) Xác định v(B) = |{A ∈ F : B ∩A = ∅}|. Rõ ràng ∑ B∈F v(B) = 2d(F) ≥ 2m2−δ2/2. Lấy Y là biến ngẫu nhiên giá trị của nó là số các thành viên B ∈ F mà rời với mọi Ai(1 ≤ i ≤ t). Bởi tính lồi của zt kỳ vọng của Y thỏa mãn E[Y ] = ∑ B∈F (v(B)/m)t = 1 mt .m( ∑ v(B)t m ) ≥ 1 mt .m( 2d(F) m )t ≥ 2m1−tδ2/2. (6) Do Y ≤ m ta kết luận rằng Pr(Y ≥ m1−tδ2/2) ≥ m−tδ2/2. (7) Ta có thể kiểm tra rằng với t = [1+1/δ],m1−tδ 2/2 > 2n/2 và vế phải của (7) lớn hơn vế phải của (5). Vì vậy, với xác suất dương, |A1∪A2 . . .∪At| > n/2 và vẫn tổng này là rời với nhiều hơn 2n/2 thành viên của F . Mâu thuẫn này chứng tỏ bất đẳng thức (4) là đúng.  31 Chương 3 Sựtuyếntínhcủakỳvọng 3.1 Cơ sở Cho X1, . . . , Xn là các biến ngẫu nhiên, X = c1X1 + . . . + cnXn. Sự tuyến tính của kỳ vọng cho biết: E[X] = c1E[X1] + . . .+ cnE[Xn]. Sức mạnh của tính chất này đến từ chỗ không bị hạn chế bởi sự phụ thuộc hay độc lập của các Xi. Trong nhiều trường hợp E[X] có thể tính dễ dàng bởi sự phân tích thành các biến ngẫu nhiênXi (thường là chỉ số). Cho σ là một phép thế ngẫu nhiên của {1, . . . , n}, được chọn đều. GọiX(σ) là số các điểm bất động của σ. Để tìm E[X] ta táchX = X1 + . . .+Xn vớiXi là biến ngẫu nhiên chỉ số của sự kiện σ(i) = i. Thế thì E[Xi] = Pr[σ(i) = i] = 1/n nên E[X] = 1/n+ . . .+ 1/n = 1. Trong ứng dụng ta thường dùng rằng có một điểm của không gian xác suất mà tại đó X ≥ E[X] và một điểm tại đó X ≤ E[X]. Ta nêu các kết quả với mục đích bày tỏ phương pháp cơ bản này. Kết quả sau của Szele (1943) nhiều lần được xem là cách dùng đầu tiên của phương pháp xác suất. Định lý 3.1.1 Có một giải đấu T với n người chơi và ít nhất n! 12n−1 đường Hamilton. Chứng minh. Trong một giải đấu ngẫu nhiên gọi X là số đường Hamilton. Với mỗi phép thế σ gọi Xσ là biến ngẫu nhiên chỉ số mà σ đưa đến một 32 đường Hamilton, tức là thoả mãn (σ(i), σ(i+ 1)) ∈ T với mọi 1 ≤ i < n. Thế thì X = ∑ Xσ và E[X] = ∑ E[Xσ] = n!2 −(n−1). Vì vậy, một giải đấu nào đó có ít nhất E[X] đường Hamilton.  3.2 Các đồ thị tách Định lý 3.2.1 Cho G = (V,E) là một đồ thị có n đỉnh và e cạnh. Thế thì G chứa một đồ thị hai nhánh với ít nhất e/2 cạnh. Chứng minh. Gọi T ⊆ V là một tập con ngẫu nhiên cho bởi Pr[x ∈ T ] = 1/2, các cách chọn này là độc lập. Đặt S = V − T . Gọi một cạnh {x, y} là cắt ngang nếu có đúng một trong hai đỉnh x, y ở trong T . Gọi X là số các cạnh cắt ngang, ta phân tích X = ∑ {x,y}∈E Xxy với Xxy là biến ngẫu nhiên chỉ số mà {x, y} là cắt ngang. Thế thì E[Xxy] = 1/2 nên E[X] = ∑ {x,y}∈E E[Xxy] = e/2. Vậy X ≥ e/2 với một T nào đó và tập các cạnh cắt ngang tạo nên một đồ thị hai nhánh.  Một không gian xác suất chặt chẽ hơn đưa đến một cải tiến nhỏ. Định lý 3.2.2 Nếu G là một đồ thị có 2n đỉnh và e cạnh thì nó chứa một đồ thị hai nhánh với ít nhất en 2n−1 cạnh. Nếu G là một đồ thị với 2n + 1 đỉnh và e cạnh thì nó chứa một đồ thị con hai nhánh với ít nhất e(n+1) 2n+1 cạnh. Chứng minh. Khi G có 2n đỉnh lấy T được chọn đều từ trong các tập con 33 n-phần tử của V . Cạnh tùy ý {x, y} có xác suất n2n−1 để là cắt ngang và phần cuối của chứng minh như trước. Khi G có 2n+ 1 phần tử chứng minh tương tự bẳng cách chọn T đều từ các tập con n phần tử của V .  Đây là một ví dụ phức tạp hơn. Gọi V = V1 ∪ . . . ∪ Vk với Vi là các các tập rời nhau cỡ n. Gọi h : [V ]k → {−1,+1} là cách tô hai màu các k-tập. Một k-tập E là cắt ngang nếu nó chứa đúng một điểm từ mỗi Vi. Cho S ⊆ V đặt h(S) = ∑ h(E), tổng quét hết các k-tập E ⊆ S. Định lý 3.2.3 Giả sử h(E) = +1 với mọi tập cắt ngang E. Thế thì có một S ⊆ V mà |h(S)| ≥ cknk, ở đây ck là hằng số dương, độc lập với n. Bổ đề 3.2.4 Gọi Pk kí hiệu tập tất cả các đa thức thuần nhất f(p1, . . . , pk) bậc k mà các hệ số có giá trị tuyệt đối nhiều nhất là một, p1p2 . . . pk có hệ số 1. Thế thì với mọi f ∈ Pk, tồn tại p1, . . . , pk ∈ [0, 1] với |f(p1, . . . , pk)| ≥ ck, ở đây ck dương và độc lập với f . Chứng minh. Đặt M(f) = max p1,...,pk∈[0,1] |f(p1, . . . , pk)|. Cho f ∈ Pk,M(f) > 0 khi f không là đa thức không. Vì Pk là compact và M : Pk → R là liên tục,M phải có giá trị nhỏ nhất ck. Chứng minh [Định lý 3.2.3] Xác định ngẫu nhiên S ⊆ V bằng cách: Pr[x ∈ S] = pi, x ∈ Vi, những cách chọn này là độc lập, pi đã biết. ĐặtX = h(S). Với mỗi k-tập E đặt XE = { h(E) nếu E ⊆ S 0 nếu khác. 34 Nói E có kiểu (a1, . . . , ak) nếu |E ∩ Vi| = ai, 1 ≤ i ≤ k. Với những E này E[XE] = h(E) Pr[E ⊆ S] = h(E)pa11 . . . pakk . Kết hợp các số hạng bởi kiểu: E[X] = ∑ a1+...+ak=k pa11 . . . p ak k . ∑ E có kiểu (a1,...,ak) h(E). Khi a1 = . . . = ak = 1 mọi h(E) = 1 bởi giả thiết nên∑ E có kiểu (1,...,1) h(E) = nk. Với những kiểu khác có ít hơn nk số hạng, mỗi cái ±1, nên | ∑ E có kiểu (a1,...,ak) h(E)| ≤ nk. Vậy E[X] = nkf(p1, . . . , pk), ở đây f ∈ Pk, như định nghĩa trong Bổ đề 3.2.4. Bây giờ chọn p1, . . . , pn ∈ [0, 1] với |f(p1, . . . , pk)| ≥ ck. Thế thì E[|X|] ≥ E[X] ≥ cknk. Giá trị cụ thể nào đó của |X| sẽ vượt quá hoặc bằng kỳ vọng của nó. Vậy có một tập cụ thể S ⊆ V mà |X| = |h(S)| ≥ cknk.  3.3 Hai kết quả nhanh Định lý 3.3.1 Có một cách tô hai màu củaKn với nhiều nhất( n a ) 21−( a 2) 35 đơn màuKa. Chứng minh [gợi ý] Lấy một cách tô màu ngẫu nhiên. Gọi X là số các đơn màu Ka và tìm E[X]. Với cách tô màu nào đó giá trị của X nhiều nhất kỳ vọng này.  Định lý 3.3.2 Có một cách tô hai màu củaKm,n với nhiều nhất( m a )( n b ) 21−ab các đơn màuKa,b. Chứng minh [gợi ý] Lấy một cách tô màu ngẫu nhiên. Gọi X là số các đơn màuKa,b và tìm E[X]. Với X nào đó sẽ lớn nhất là kỳ vọng này.  3.4 Vectơ cân bằng Sau đây |v| là chuẩn Euclide thông thường. Định lý 3.4.1Cho v1, . . . , vn ∈ Rn, mọi |vi| = 1. Thế thì tồn tại e1, . . . , en = ±1 sao cho |e1v1 + . . .+ envn| ≤ √ n, và cũng tồn tại e1, . . . , en = ±1 sao cho |e1v1 + . . .+ envn| ≥ √ n. Chứng minh. Lấy e1, . . . , en được chọn đều và độc lập từ {−1,+1}. Đặt X = |e1v1 + . . .+ envn|2 Thế thì X = n∑ i=1 n∑ j=1 eiejvi.vj. 36 Vì vậy E[X] = n∑ i=1 n∑ j=1 vi.vjE[eiej]. Khi i 6= j,E[eiej] = E[ei].E[ej] = 0. Khi i = j, e2i = 1 nênE[e2i ] = 1. Vậy E[X] = n∑ i=1 vi.vi = n. Vậy có những e1, . . . , en = ±1 cụ thể để X ≥ n và X ≤ n. Lấy căn bậc hai hoàn thành chứng minh.  Kết quả sau bao gồm Định lý 3.4.1 ứng với trường hợp p1 = . . . = pn = 1/2. Định lý 3.4.2 Cho v1, . . . , vn ∈ Rn, mọi |vi| ≤ 1. Lấy p1, . . . , pn ∈ [0, 1] tuỳ ý và đặt ω = p1v1 + . . . + pnvn. Thế thì tồn tại e1, . . . , en ∈ {0, 1} để, với v = e1v1 + . . .+ envn, ta có |ω − v| ≤ √ n 2 . Chứng minh. Chọn các ei độc lập với Pr[ei = 1] = pi,Pr[ei = 0] = 1− pi. Chọn ngẫu nhiên ei đưa đến v ngẫu nhiên và biến ngẫu nhiên X = |ω − v|2 Ta tường minh X = | n∑ i=1 (pi − ei)vi|2 = n∑ i=1 n∑ j=1 vi.vj(pi − ei)(pj − ej) nên có E[X] = n∑ i=1 n∑ j=1 vi.vj‘E[(pi − ei)(pj − ej)] 37 Cho i 6= j, E[(pi − ei)(pj − ej)] = E[pi − ei]E[pj − ej] = 0. Cho i = j, E[(pi − ei)2] = pi(pi − 1)2 + (1− pi)p2i = pi(1− pi) ≤ 1 4 , (E[(pi − ei)2] = Var[ei]). Vậy E[X] = n∑ i=1 pi(1− pi)|vi|2 ≤ 1 4 n∑ i=1 |vi|2 ≤ n 4 và chứng minh tiếp tục như Định lý 3.4.1.  3.5 Đèn nhấp nháy Định lý 3.5.1 Cho aij = ±1 với mọi 1 ≤ i, j ≤ n. Thế thì tồn tại xi, yj = ±1, 1 ≤ i, j ≤ n sao cho n∑ i=1 n∑ j=1 aijxixj ≥ (√ 2 pi + o(1) ) n3/2. Kết quả này có một ứng dụng thú vị. Cho một mảng nìn các bóng đèn được chọn, mỗi cái hoặc bật (aij = +1) hoặc tắt (aij = −1). Giả sử mỗi dòng và mỗi cột có một sự chuyển sao cho nếu sự chuyển được xảy ra (xi = −1 cho dòng i và yj = −1 cho cột j) tất cả đèn ở hàng này sẽ chuyển: bật thành tắt và tắt thành bật. Thế thì có thời điểm số đèn bật trừ đi số đèn tắt ít nhất là ( √ 2 pi + o(1))n3/2. Chứng minh [Định lý 3.5.1] Quên các x. Lấy y1, . . . , yn = ±1 được chọn độc lập, đều và đặt Ri = n∑ j=1 aijyj, 38 R = n∑ i=1 |Ri|. Cố định i. Giá trị của aijyj là +1 hoặc −1 với xác suất 1/2 và giá trị của chúng (quét qua j) là độc lập. Vậy Ri có phân phối Sn - phân phối của tổng n biến ngẫu nhiên {−1,+1} đều, độc lập - nên E[|Ri|] = E[|Sn|] = (√ 2 pi + o(1) ) √ n. Tiệm cận này tìm bằng cách ước lượng Sn bởi √ nN , N là phân phối chuẩn thông thường theo định lý giới hạn trung tâm và dùng tính toán sơ cấp. (Mặt khác, có thể: E[|Sn|] = n21−n ( n− 1 b(n− 1)/2c ) và dùng công thức Stirling). Bây giờ áp dụng sự tuyến tính của kỳ vọng cho R, E[R] = n∑ i=1 E[|Ri|] = (√ 2 pi + o(1) ) n3/2. Có tồn tại y1, . . . , yn = ±1 để R đạt ít nhất giá trị này. Cuối cùng, lấy xi với dấu giống như Ri để có n∑ i=1 xi n∑ j=1 aijyj = n∑ i=1 xiRi = n∑ i=1 |Ri| = R ≥ (√ 2 pi + o(1) ) n3/2.  39 Chương 4 Bổđềđịaphương 4.1 Bổ đề Trong chứng minh kiểu xác suất của một kết quả tổ hợp, ta thường phải chỉ ra rằng xác suất của một sự kiện nào đó là dương. Tuy nhiên, nhiều chứng minh cho thấy xác suất để các sự kiện đang xét xảy ra không chỉ dương mà còn lớn. Thực tế, nhiều chứng minh xác suất cho thấy các sự kiện đúng với xác suất cao, xác suất dần tới một khi số chiều của bài toán tăng. Chẳng hạn, xét xác suất cho trong chương 1 rằng cho mỗi k ≤ 1 có một giải đấu trong đó cho mọi tập k người chơi có một người đánh bại tất cả người đó. Chứng minh chỉ rõ rằng cho mỗi k cố định nếu số người chơi n đủ lớn thì thì hầu hết các giải đấu của n người chơi thỏa mãn tính chất này; nghĩa là, xác suất để một giải đấu ngẫu nhiên với n người chơi có tính chất mong muốn dần tới 1 khi n dần tới vô cùng. Mặt khác, có một trường hợp tầm thường trong đó ta có thể chỉ ra sự kiện nào đó xảy ra với xác suất dương, dù rất nhỏ. Thực vậy, nếu chúng ta có n sự kiện độc lập lẫn nhau và mỗi sự kiện đúng với xác suất ít nhất p > 0, thì xác suất để tất cả các sự kiện đúng hiển nhiên ít nhất là pn, nó là dương dù có lẽ là lũy thừa nhỏ với số mũ n. Thật tự nhiên để dự đoán rằng từ trường hợp độc lập có thể tổng quát cho những trường hợp mà sự phụ thuộc là hiếm, và đưa ra một cách tổng quát hơn để chứng minh rằng các sự kiện nào đó là đúng với xác suất dương, dù nhỏ. Một cách tổng quát như thế là, thực sự, có thể, và được phát biểu trong bổ đề sau, gọi là Bổ đề Địa phương Lovász. Bổ đề đơn giản này, được chứng minh đầu tiên trong Erdos và Lovász (1975), là một công cụ mạnh hàng đầu, vì nó cung cấp một cách để đối phó với các sự kiện hiếm. 40 Bổ đề 4.1.1 [Bổ đề địa phương; Trường hợp tổng quát] Cho A1, A2, . . . , An là các sự kiện của một không gian xác suất tùy ý. Một đồ thị có hướng D = (V,E) trên tập các đỉnh V = {1, 2, . . . , n} được gọi là đồ thị có hướng phụ thuộc vào các sự kiệnA1, A2, . . . , An nếu cho mỗi i, 1 ≤ i ≤ n, sự kiện Ai là độc lập với mọi sự kiện {Aj : (i, j) /∈ E}. Giả sử rằngD = (V,E) là đồ thị có hướng phụ thuộc vào các sự kiện nêu trên và giả sử rằng có các số thực x1, x2, . . . , xn sao cho 0 ≤ xi < 1 và Pr(Ai) ≤ xi ∏ (i,j)∈E(1− xj) với mọi 1 ≤ i ≤ n. Thế thì Pr(∧ni=1Ai) ≥ ∏ni=1(1 − xi). Đặc biệt, với xác suất dương, không có sự kiện Ai nào đúng. Chứng minh. Trước hết chúng ta chứng minh, bằng quy nạp cho s, rằng cho S ⊆ {1, 2, . . . , n}, |S| = s < n nào đó và i /∈ S nào đó, Pr(Ai| ∧ j∈S Aj) ≤ xi. (8) Điều này chắc chắn đúng cho s = 0. Giả sử rằng nó đúng cho mọi s′ < s, chúng ta chứng minh nó cho s. Đặt S1 = {j ∈ S : (i, j) ∈ E}, S2 = S \ S1. Thế thì Pr(Ai| ∧ j∈S Aj) = Pr(Ai ∧ ( ∧ j∈S1 Aj)| ∧ l∈S2 Al) Pr( ∧ j∈S1 Aj)| ∧ l∈S2 Al) . (9) Để đánh giá tử thức nhận xét rằng do Ai là độc lập với các sự kiện {Al : l ∈ S2}, Pr(Ai ∧ ( ∧ j∈S1 Aj)| ∧ l∈S2 Al) ≤ Pr(Ai| ∧ l∈S2 Al) = Pr(Ai) ≤ xi ∏ (i,j)∈E (1− xj). (10) Mẫu thức, mặt khác, có thể được đánh giá dựa theo giả thiết quy nạp. Thực vậy, giả sử S1 = {j1, j2, . . . , jr}. Nếu r = 0 thì mẫu thức là 1 và dẫn đến 41 (8). Trường hợp khác Pr(Aj1 ∧Aj2 ∧ . . . ∧Ajr| ∧ l∈S2 Al) = (1− Pr(Aj1| ∧ l∈S2 Al)).(1− Pr(Aj2|Aj1 ∧ ∧ l∈S2 Al)). . . . . . . .(1− Pr(Ajr|Aj1 ∧Aj2 ∧ . . . ∧Ajr−1 ∧ ∧ l∈S2 Al)) ≥ (1− xj1)(1− xj2) . . . (1− xjr) ≥ ∏ (i,j)∈E (1− xj). (11) Kết hợp (10) và (11) vào (8), chúng ta kết luận rằngPr(Ai| ∧ j∈S Aj) ≤ xi, hoàn thành chứng minh quy nạp. Bây giờ dễ dàng suy ra khẳng định của Bổ đề 4.1.1, vì Pr( n∧ i=1 Ai) = (1− Pr(A1)).(1− Pr(A2|A1)). . . . . . . .(1− Pr(An| n−1∧ i=1 Ai)) ≥ n∏ i=1 (1− xi), (12) hoàn thành chứng minh.  Hệ quả 4.1.2 [Bổ đề Địa phương; Trường hợp đối xứng] Cho các sự kiện A1, A2, . . . , An trong một không gian xác suất tùy ý. Giả sử rằng mỗi sự kiện Ai là độc lập với tập tất cả các sự kiệnAj khác ngoại trừ nhiều nhất d, và rằng Pr(Ai) ≤ p cho mọi 1 ≤ i ≤ n. Nếu ep(d+ 1) ≤ 1 (13) thì Pr( ∧n i=1Ai) > 0. Chứng minh. Nếu d = 0 thì kết quả là tầm thường. Nếu khác, theo giả thiết có một đồ thị có hướngD = (V,E) phụ thuộc vào các sự kiệnA1, A2, . . . , An trong đó cho mỗi i, |{j : (i, j) ∈ E}| ≤ d. Bây giờ kết quả suy ra từ Bổ đề 4.1.1 bằng cách lấy xi = 1/(d+ 1)(< 1) cho mọi i và tính chất cho d ≥ 1 nào đó, (1− 1 d+1) d > 1/e.  42 Như được chỉ ra bởi Shearer vào 1985, đáng để chú ý rằng hằng số 'e' là tốt nhất có thể trong bất đẳng thức (13). Cũng chú ý rằng chứng minh của Bổ đề 5.1.1 chỉ ra rằng kết luận vẫn còn đúng nếu thay các giả thiết Ai độc lập với các {Aj : (i, j) /∈ E} và Pr(Ai) ≤ xi ∏ (i,j)∈E(1 − xj) bởi giả thiết yếu hơn Pr(Ai| ∧ j∈S2 Aj) ≤ xi ∏ (i,j)∈E(1 − xj), cho mỗi i và mỗi S2 ⊂ {1, 2, . . . , n} \ {j : (i, j) ∈ E}, điều này có ích trong một số áp dụng. Trong các mục sau chúng ta giới thiệu các áp dụng khác nhau của Bổ đề Địa phương để nhận một số kết quả tổ hợp. Không có chứng minh của kết quả nào mà không sử dụng Bổ đề Địa phương. 4.2 Tính chất B và các tập đa sắc của các số thực Nhắc lại rằng một siêu đồ thịH = (V,E) có tính chấtB (tức là hai sắc), nếu có một cách tô màu cho V bằng hai màu sao cho không có cạnh f ∈ E nào là đơn màu. Định lý 4.2.1 Cho H = (V,E) là một siêu đồ thị trong đó mỗi cạnh có ít nhất k phần tử, và giả sử rằng mỗi cạnh củaH giao với nhiều nhất d cạnh khác. Nếu e(d+ 1) ≤ 2k−1 thìH có tính chất B. Chứng minh. Tô màu mỗi đỉnh v của H , độc lập và ngẫu nhiên, hoặc xanh hoặc đỏ (với xác suất bằng nhau). Cho mỗi cạnh f ∈ E, đặt Af là sự kiện rằng f là đơn màu. Rõ ràng Pr(Af) = 2/2 |f | ≤ 1/2k−1. Hơn nữa, rõ ràng là mỗi sự kiện Af là độc lập với tất cả các sự kiện Af ′ khác cho mọi cạnh f ′ mà không giao f . Bây giờ kết quả suy ra từ Hệ quả 4.1.2.  Định lý 4.2.2 Chom và k là hai số nguyên dương thỏa mãn e(m(m− 1) + 1)k(1− 1 k )m ≤ 1. (14) Thế thì, cho mọi tập S củam số thực nào đó có một k-cách tô màu sao cho mỗi phép tịnh tiến x+ S (cho x ∈ R) là đa sắc. Chú ý rằng (14) đúng mỗi khim > (3 + o(1))k log k. 43 Chứng minh. Chúng ta trước hết cố định một tập hữu hạn X ⊆ R và chỉ ra sự tồn tại của một k-cách tô màu sao cho mỗi phép tịnh tiến x + S (cho x ∈ X) là đa sắc. Đây là một hệ quả dễ của Bổ đề Địa phương. Thật vậy, đặt Y = ∪x∈X(x + S) và cho c : Y → {1, 2, . . . , k} là một cách tô k màu của Y nhận được theo cách chọn, cho mỗi y ∈ Y , độc lập và ngẫu nhiên, c(y) ∈ {1, 2, . . . , k} theo phân phối đều trên {1, 2, . . . , k}. Cho mỗi x ∈ X , lấy Ax là sự kiện rằng x + S là không đa sắc (ứng với c). Rõ ràng Pr(Ax) ≤ k(1 − 1k)m. Hơn nữa, mỗi sự kiện Ax là độc lập với tất cả các sự kiện Ax′ khác trừ ra những sự kiện mà (x + S) ∩ (x′ + S) 6= ∅. Vì có nhiều nhất m(m − 1) sự kiện như vậy, kết quả mong muốn suy ra từ Hệ quả 4.1.2. Bây giờ chúng ta có thể chỉ ra sự tồn tại của một cách tô màu của tập gồm tất cả các số thực với tính chất mong muốn, bởi một lập luận compact chuẩn. Do một không gian rời rạc với k điểm là compact (tầm thường), Định lý Tikhonov (cái mà tương đương với tiên đề chọn) chứng tỏ rằng một tích tùy ý của các không gian như thế là compact. Đặc biệt, không gian của tất cả các hàm từ R vào {1, 2, . . . , k}, với tích tôpô thông thường, là compact. Trong không gian này cho mọi x ∈ R cố định, tập Cx của tất cả các cách tô màu c, sao cho x + S là đa sắc, là đóng. (Thực tế, nó là vừa đóng vừa mở, do một cơ sở của các tập mở là tập của tất cả các cách tô màu mà giá trị của chúng là trong một số hữu hạn của các vị trí). Vì chúng ta đã chứng minh ở trên, giao của một số hữu hạn các tập Cx nào đó là khác rỗng. Vì vậy suy ra, từ tính compact, rằng giao của tất cả các tập Cx là không rỗng. Một cách tô màu nào đó trong giao này có tính chất như trong kết luận của Định lý 4.2.2.  4.3 Cận dưới cho các số Ramsey Tìm ra cận dưới cho các số Ramsey bởi Erdos vào 1947 là một trong những áp dụng đầu tiên của phương pháp xác suất. Bổ đề Địa phương cung cấp một cách để cải tiến những cận dưới này. Chúng ta nhận được, trước tiên, cận dưới cho số Ramsey chéoR(k, k). Xét một cách tô hai màu các cạnh củaKn. Cho mỗi tập S của k đỉnh của Kn, gọi AS là sự kiện rằng đồ thị đầy đủ trên S là đơn màu. Rõ ràng Pr(AS) = 2 1−(k2) . Hiển nhiên mỗi AS là độc lập với các 44 sự kiện AT , trừ khi chúng thỏa mãn |S ∩T | ≥ 2, do ít nhất thì các đồ thị đầy đủ tương ứng có chung một cạnh. Do đó chúng ta có thể áp dụng Hệ quả 4.1.2 với p = 21−( k 2) và d = (k 2 )( n k−2 ) để kết luận: Mệnh đề 4.3.1 Nếu e( (k 2 )( n k−2 ) + 1).21−( k 2) n. Một tính toán ngắn đưa đến R(k, k) > √ 2 e (1 + o(1))k2k/2, chỉ cải tiến một nhân tử 2 so với áp dụng phương pháp xác suất trực tiếp. Dù cải tiến này là nhỏ nhưng điều đó không khiến phải băn khoăn; Bổ đề Địa phương là công cụ mạnh nhất cho những trường hợp sự phụ thuộc giữa các sự kiện là hiếm, điều không xảy ra với trường hợp đang xét. Thực vậy, tổng số các sự kiện đang xét là K = (n k ) , và bậc ngoài lớn nhất d trong đồ thị có hướng phụ thuộc là(k 2 )( n k−2 ) . Cho k lớn và n lớn hơn nhiều, ta có d > K1−O(1/k), như thế sự phụ thuộc là nhiều. Mặt khác, nếu ta xét những tập S nhỏ, chẳng hạn, những tập có cỡ 3, chúng ta nhận thấy rằng mỗi cái trong tổng số K = (n 3 ) của chúng chung nhau một cạnh với chỉ 3(n − 3) ≈ K1/3. Điều này cho biết rằng Bổ đề Địa phương có lẽ đáng chú ý hơn để cải tiến cho các số Ramsey không chéo R(k, l), đặc biệt khi một tham số là nhỏ. Tất nhiên ở đây chúng ta phải áp dụng dạng không đối xứng của Bổ đề Địa phương. Chúng ta xét một ví dụ, theo Spencer (1977), số Ramsey R(k, 3). Chúng ta tô hai màu các cạnh của Kn độc lập và ngẫu nhiên, mỗi cạnh được tô màu xanh với xác suất p. Cho mỗi tập T ba đỉnh, gọi AT là sự kiện rằng tam giác trên T là màu xanh. Tương tự, cho mỗi tập k đỉnh S, gọi BS là sự kiện đồ thị đầy đủ trên S màu đỏ. Rõ ràng Pr(AT ) = p 3 và Pr(BS) = (1− p)( k 2) . Xây dựng một đồ thị có hướng phụ thuộc vào các sự kiện AT và BS bằng cách nối hai đỉnh bằng các cạnh, với cả hai hướng, nếu và chỉ nếu đồ thị đầy đủ tương ứng chung một cạnh. Rõ ràng, mỗi AT -nút của đồ thị phụ thuộc là kề với 3(n − 3) < 3n AT ′-nút và với nhiều nhất là (n k ) BS-nút. Tương tự, mỗi BS-nút là kề với(k 2 ) (n− k) < k2n/2 AT -nút và với nhiều nhất (n k ) BS′-nút. Ta suy ra từ Bổ đề Địa phương (Bổ đề 4.1.1) rằng nếu ta có thể tìm thấy một 0 < p < 1 và hai số thực 0 ≤ x < 1 và 0 ≤ y < 1 sao cho p3 ≤ x(1− x)3n(1− y)(nk) 45 và (1− p)(k2) ≤ y(1− x)k2n/2(1− y)(nk) thì R(k, 3) > n. Vấn đề của chúng ta là tìm số lớn nhất có thể k = k(n) để có một cách chọn p, x và y như thế. Một tính toán sơ cấp chỉ ra rằng cách chọn là tốt nhất khi p = c1n −1/2, k = c2n1/2 logn, x = c3/n3/2 và y = c4 en 1/2 log2 n . Điều này đưa đến R(k, 3) > c5k 2/ log2 k. Lập luận tương tự đưa đến R(k, 4) > k5/2+o(1). Cả hai trường hợp đều yêu cầu một khối lượng tính toán lớn. Tuy nhiên, gái có công chồng chẳng phụ; đánh giá R(k, 3) > c5k 2/ log2 k tốt hơn so với cận dưới của Erdos (1961) với những lập luận rất phức tạp. Cái này được cải tiến bởi Kim (1995) tới R(k, 3) > c6k 2/ log k. Đánh giá bên trên cho R(k, 4) là tốt nhất so với tất cả các đánh giá khác được biết mà không dùng Bổ đề Địa phương. 4.4 Một kết quả hình học Một họ các hình cầu đơn vị mở F trong không gian Euclide ba chiều R3 được gọi là một phủ cơ số k của R3 nếu một điểm tùy ý x ∈ R3 thuộc ít nhất k hình cầu. Một phủ cơ số 1 được gọi đơn giản là một phủ. Một phủ cơ số k F được gọi là tách được nếu có một phân hoạch thành (các họ đôi một rời nhau) F1 và F2, mỗi họ là một phủ của R3. Mani-Levitska và Pach (1988) xây dựng một phủ cơ số k không tách được, cho số nguyên k ≥ 1 tùy ý, bởi các hình cầu đơn vị mở. Mặt khác chúng ta chứng minh được rằng một phủ cơ số k của R3 trong đó không có điểm nào bị phủ bởi nhiều hơn c2k/3 hình cầu là tách được. Điều này tiết lộ một tính chất thú vị: khó tách các phủ mà phủ các điểm nào đó của R3 nhiều lần hơn là tách các phủ mà mỗi điểm bị phủ bởi cùng một số hình cầu. Phát biểu chính xác của Định lý Mani-Levitska và Pach là như sau. Định lý 4.4.1 Cho F = {Bi}i∈I là một phủ cơ số k của một không gian Euclide ba chiều bởi các hình cầu đơn vị mở. Giả sử, thêm nữa, rằng không có điểm nào của R3 được chứa trong nhiều hơn t thành viên của F. Nếu e.t3218/2k−1 ≤ 1 thì F là tách được. 46 Chứng minh. Xác định một siêu đồ thị vô hạnH = (V (H), E(H)) như sau. Tập các đỉnh củaH , V (H), đơn giản là F = {Bi}i∈I . Cho mỗi x ∈ R3 đặt Ex là tập của các hình cầu Bi ∈ F mà chứa x. Tập các cạnh củaH , E(H), đơn giản là tập các Ex, với cách hiểu rằng khi Ex = Ey cạnh chỉ lấy một lần. Chúng ta khẳng định rằng mỗi cạnh Ex giao với ít hơn t 3218 cạnh Ey khác của H . Nếu x ∈ Bi tâm của Bi là trong khoảng cách một từ x. Bây giờ nếu Bj ∩ Bi 6= ∅ tâm của Bj là trong khoảng cách ba từ x nên Bj nằm hoàn toàn trong hình cầu bán kính bốn tâm tại x. Một Bj như thế phủ đúng 4−3 = 2−6 thể tích của hình cầu đó. Vì không có đỉnh nào bị phủ nhiều hơn t lần có thể có nhiều nhất 26t hình cầu như thế. Không khó để kiểm tra rằngm hình cầu trong R3 cắt R3 thành ít hơnm3 thành tố liên thông do đó có nhiều nhất (26t)3 Ey phân biệt giao với Ex. Bây giờ, xét, siêu đồ thị con hữu hạn L nào đó của H . Mỗi cạnh của L có ít nhất k đỉnh, và nó giao với nhiều nhất d < t3218 cạnh khác của L. Do, theo giả thiết, e(d + 1) ≤ 2k−1, Định lý 4.2.1 (cái mà là một hệ quả đơn giản của bổ đề địa phương), chứng tỏ rằng L là hai sắc. Điều này có nghĩa là ta có thể tô màu các đỉnh của L xanh và đỏ sao cho không có cạnh nào của L là đơn màu. Do điều này đúng cho L hữu hạn nào đó, một lập luận về sự compact, lập luận như trong Định lý 4.2.2, chỉ ra rằng H là hai sắc. Cho một cách tô hai màu của H mà không có cạnh nào đơn màu, chúng ta đơn giản lấy F1 là tập tất cả các hình cầu màu xanh, và F2 là tập tất cả các hình cầu màu đỏ. Rõ ràng, mỗi Fi là một phủ của R3, hoàn thành chứng minh định lý.  4.5 Số arboricity tuyến tính của đồ thị Một rừng tuyến tính là một rừng (tức là một đồ thị không có vòng) trong đó mỗi thành phần liên thông là một đường. Số arboricity tuyến tính la(G) của đồ thị G là số nhỏ nhất các rừng tuyến tính trong G, mà hợp của chúng là tập của tất cả các cạnh của G. Khái niệm này được giới thiệu bởi Harary. Giả thuyết sau, biết đến như là Giả thuyết số arboricity tuyến tính, được nảy sinh trong Akiyama, Exoo và Harary (1981). Giả thuyết 4.5.1 [Giả thuyết số arboricity tuyến tính] Số arboricity tuyến tính 47 của mọi đồ thị d-chính quy là d(d+ 1)/2e. Chú ý rằng mỗi đồ thị đầy đủ d-chính quy có nd/2 cạnh, và mỗi rừng tuyến tính trong nó có nhiều nhất n− 1 cạnh, có ngay bất đẳng thức la(G) ≥ nd 2(n− 1) > d 2 . Do la(G) là một số nguyên nó đưa đến la(G) ≥ d(d+ 1)/2e. Điều khó của Giả thuyết 4.5.1 nằm ở bất đẳng thức ngược lại: la(G) ≤ d(d+ 1)/2e. Cũng chú ý rằng mỗi đồ thị G với bậc lớn nhất ∆ là một đồ thị con của một đồ thị ∆-chính quy (cái mà có thể có nhiều đỉnh cũng như cạnh hơn G), Giả thuyết số arboricity tuyến tính tương đương với phát biểu rằng số arboricity tuyến tính của mọi đồ thị bậc lớn nhất ∆ nhiều nhất là d(∆ + 1)/2e. Mặc dù Giả thuyết này nhận được sự quan tâm lớn, kết quả tổng quát tốt nhất liên quan đến nó, được chứng minh mà không dùng lập luận xác suất, là la(G) ≤ d3∆/5e cho ∆ chẵn và la(G) ≤ d(3∆ + 2)/5e cho ∆ lẻ. Trong phần này chúng ta chứng minh rằng cho mỗi  > 0 có một ∆0 = ∆0() sao cho cho mọi ∆ ≥ ∆0(), số arboricity tuyến tính của mọi đồ thị với bậc lớn nhất ∆ nhỏ hơn là (12 + )∆. Kết quả này xuất hiện trong Alon (1988) và chứng minh của nó liên quan mật thiết đến Bổ đề Địa phương. Từ kết quả cho đồ thị có hướng chuyển sang đồ thị vô hướng là rất tiện lợi. Một đồ thị có hướng d-chính quy là một đồ thị có hướng trong đó bậc trong và bậc ngoài của mọi đỉnh đúng là d. Một rừng có hướng tuyến tính là một rừng trong đó mọi thành tố liên thông là một đường có hướng. Số arboricity tuyến tính có hướng dla(G) của một đồ thị có hướng G là số nhỏ nhất các rừng có hướng tuyến tính củaG. Bản có hướng của Giả thuyết số arboricity tuyến tính, được phát biểu đầu tiên trong Nakayama và Peroche (1987) là: Giả thuyết 4.5.2 Cho mọi đồ thị có hướng d-chính quyD, dla(D) = d+ 1. Chú ý rằng do các cạnh của một đồ thị vô hướng 2d-chính quy (liên thông) tùy ý G có thể được định hướng dọc theo một vòng Euler, sao cho đồ thị định 48 hướng kết quả là d-chính quy, sự đúng đắn của Giả thuyết 4.5.2 cho d sẽ chuyển sang Giả thuyết 4.5.1 cho 2d. Dễ dàng chứng minh được một đồ thị tùy ý với n đỉnh và bậc lớn nhất d chứa một tập độc lập với cỡ ít nhất là n/(d+ 1). Chúng ta có Mệnh đề sau. Mệnh đề 4.5.3 Cho H = (V,E) là một đồ thị với bậc lớn nhất d, và cho V = V1 ∪ V2 ∪ . . . ∪ Vr là một phân hoạch của V thành r các tập đôi một rời nhau. Giả sử mỗi tập Vi có lực lượng |Vi| ≥ 2ed, ở đây e là cơ số của logarithm tự nhiên. Thế thì có một tập các đỉnh độc lậpW ⊆ V (tức là dồ thị cảm sinh của V trênW không có cạnh nào), mà chứa một đỉnh từ mỗi Vi. Chứng minh. Rõ ràng ta có thể giả sử rằng mỗi tập Vi có lực lượng là đúng g = d2ede (nếu khác, đơn giản thay mỗi Vi bởi tập con có lực lượng g của nó, và thayH bởi đồ thị con cảm sinh của nó trên hợp của r các tập mới này). Chúng ta lấy độc lập và ngẫu nhiên từ mỗi Vi một đỉnh đơn theo phân phối đều. Lấy W là tập ngẫu nhiên của các đỉnh được lấy. Để hoàn thành chứng minh chúng ta chỉ ra rằng với xác suất dươngW là một tập các đỉnh độc lập trongH . Cho mỗi cạnh f củaH , đặtAf là sự kiện rằngW chứa cả hai đỉnh cuối của f . Rõ ràng, Pr(Af) ≤ 1/g2. Hơn nữa, nếu các đỉnh cuối của f nằm trong Vi và trong Vj , thì sự kiệnAf là độc lập với tất cả các sự kiện tương ứng với các cạnh mà các đỉnh cuối của chúng không nằm trong Vi∪Vj . Từ đó, có một đồ thị có hướng phụ thuộc vào các sự kiện trên trong đó bậc lớn nhất là ít hơn 2gd, và do e.2gd.(1/g2) = 2ed/g < 1, theo Hệ quả 4.1.2, chúng ta kết luận rằng với xác suất dương không có sự kiện Af nào đúng. Nhưng điều này chứng tỏ rằngW là một tập độc lập chứa một đỉnh từ mỗi Vi, hoàn thành chứng minh.  Định lý 4.5.4 Cho G = (U, F ) là một đồ thị có hướng d-chính quy, chu vi có hướng g ≥ 8ed. Thế thì dla(G) = d+ 1. Chứng minh. Như đã biết, F có thể phân hoạch thành d đồ thị con dẫn xuất 1-chính quy đôi một rời nhau F1, F2, . . . , Fd của G. [Đây là một hệ quả dễ 49 của Định lý Hall-Konig; cho H là một đồ thị hai nhánh mà hai lớp đỉnh của nó A,B là hai bản sao của U , trong đó u ∈ A nối với v ∈ B nếu và chỉ nếu (u, v) ∈ F . Do H là d-chính quy các cạnh của nó có thể phân chia thành d các tương xứng hoàn hảo, cái mà tương ứng với d đồ thị con dẫn xuất 1-chính quy của G.] Mỗi Fi là một hợp của các vòng có hướng các đỉnh rời nhau Ci1, Ci2, . . . , Ciri. Gọi V1, V2, . . . , Vr là các tập của các cạnh của tất cả các vòng {Cij : 1 ≤ i ≤ d, 1 ≤ j ≤ ri}. Rõ ràng các tập V1, V2, . . . , Vr là một phân hoạch của tập F chứa tất cả các cạnh của G, và do điều kiện chu vi, |Vi| ≥ g ≥ 8ed cho mọi 1 ≤ i ≤ r. Gọi H là đồ thị đường của G, nghĩa là, đồ thị mà tập đỉnh của nó là tập F gồm các cạnh của G, trong đó hai cạnh là kề nhau nếu và chỉ nếu chúng có chung một đỉnh trong G. Rõ ràng H là (4d− 2)-chính quy. Vì lực lượng của mỗi Vi ít nhất là 8ed ≥ 2e(4d− 2), nên có, theo Mệnh đề 4.5.3, một tập độc lập của H mà chứa một thành viên từ mỗi Vi. Nhưng điều này có nghĩa là có một tương xứngM trong G, chứa ít nhất một cạnh từ mỗi vòng Cij của các 1-nhân tố F1, F2, . . . , Fd. Do đó M,F1 \M,F2 \M, . . . , Fd \M là d+ 1 các rừng có hướng trongG (mỗi một trong đó là một tương xứng) mà phủ tất cả các cạnh của nó. Vậy dla(G) ≤ d+ 1. Vì G có |U |.d cạnh và mỗi rừng tuyến tính có hướng có thể có nhiều nhất là |U | − 1 cạnh, dla(G) ≥ |U |d/(|U | − 1) > d. Vì vậy dla(G) = d+ 1, hoàn thành chứng minh.  Bổ đề 4.5.5 Cho G = (V,E) là một đồ thị có hướng d-chính quy, và p là một số nguyên thỏa mãn 10 √ d ≤ p ≤ 20√d. Thế thì, có một cách tô p màu các đỉnh của G bởi các màu 0, 1, . . . , p − 1 với tính chất sau; cho mỗi cạnh v ∈ V và mỗi màu i, số N+v,i = |{(v, u) ∈ E : u có màu i}| và N−v,i = |{(u, v) ∈ E : u có màu i}| thỏa mãn: |N+(v, i)− d p | ≤ 3 √ d p √ log d, |N−(v, i)− d p | ≤ 3 √ d p √ log d. (15) 50 Chứng minh. Gọi f : V → {0, 1, . . . , p − 1} là một cách tô p màu ngẫu nhiên các đỉnh của V bởi p màu, ở đây cho mỗi v ∈ V , f(v) ∈ {0, 1, . . . , p − 1} được chọn theo phân phối đều. Cho mỗi đỉnh v ∈ V và mỗi màu i, 0 ≤ i < p, gọi A+v,i là sự kiện rằng sốN+v,i của các lân cận của v trong G mà màu của nó là i sẽ không thỏa mãn bất đẳng thức (15). Rõ ràng, N+v,i là một biến ngẫu nhiên Nhị thức với kỳ vọng d/p và phương sai chuẩn√ d p (1− d p ) < √ d p . Vậy, theo ước lượng chuẩn cho phân phối Nhị thức, cho mọi v ∈ V và 0 ≤ i < p, Pr(A+v,i) < 1/d 4. Tương tự, nếu gọi A−v,i là sự kiện số N − v,i vi phạm (15) thì Pr(A−v,i) < 1/d 4. Rõ ràng, mỗi sự kiệnA+v,i hoặcA − v,i là độc lập với tất cả các sự kiệnA + u,j hoặc A−u,j cho mọi đỉnh u ∈ V mà không có lân cận chung với v trong G. Do đó, có một đồ thị có hướng phụ thuộc vào tất cả các sự kiện của chúng ta ở trên với bậc lớn nhất ≤ (2d)2.p. Do e 1 d4 ((2d)2p + 1) < 1, Hệ quả 4.1.2 (dạng đối xứng của Bổ đề Địa phương) chứng tỏ rằng với xác suất dương không sự kiện A+v,i hoặc A − v,i nào đúng, nghĩa là có một cách tô p màu thỏa mãn (15) cho mọi v ∈ V và 0 ≤ i < p, hoàn thành chứng minh.  Bây giờ chúng ta đã sẵn sàng để đối phó với đồ thị có hướng chính quy tổng quát. Gọi G = (V,E) là một đồ thị có hướng d-chính quy tùy ý. Trong suốt các lập luận chúng ta giả sử, mỗi khi cần đến, rằng d là đủ lớn. Lấy p là một số nguyên tố thỏa mãn 10 √ d ≤ p ≤ 20√d (đã biết luôn có một số nguyên tố nằm giữa n và 2n với mọi n). Theo Bổ đề 4.5.5 có một cách tô màu các đỉnh f : V → {0, 1, . . . , p − 1} thỏa mãn (15). Cho mỗi i, 0 ≤ i < p, gọi Gi = (V,Ei) là đồ thị con có hướng dẫn xuất của G xác định bởi Ei = {(u, v) ∈ E : f(v) ≡ f(u) + i (mod p)}. Theo bất đẳng thức (15) bậc trong lớn nhất ∆−i và bậc ngoài lớn nhất ∆ + i trong mỗi Gi nhiều nhất là d p + 3 √ d p √ log d. Hơn nữa, cho mỗi i > 0, độ dài của mọi vòng có hướng trongGi chia hết cho p. Như vậy, chu vi có hướng gi củaGi ít nhất là p. Do mỗiGi có thể trở thành, do thêm vào các đỉnh và cạnh, đồ thị có 51 hướng ∆i-chính quy với cùng chu vi gi và bậc ∆i = max(∆ + i ,∆ − i ), và do gi > 8e∆i (cho tất cả d đủ lớn), chúng ta kết luận, theo Định lý 4.5.4, rằng dlaGi ≤ ∆i + 1 ≤ dp + 3 √ d p √ log d + 1 cho mọi 1 ≤ i < p. Cho G0, chúng ta chỉ cần áp dụng bất đẳng thức tầm thường dlaG0 ≤ 2∆0 ≤ 2 d p + 6 √ d p √ log d nhận bằng cách, chẳng hạn, nhúngG0 như một đồ thị con của đồ thị∆0-chính quy, tách các cạnh của đồ thị này vào ∆0 các đồ thị con 1-chính quy, và phá mỗi đồ thị con dẫn xuất 1-chính quy này thành hai rừng có hướng liên thông. Hai bất đẳng thức cuối, kết hợp với giả thiết rằng 10 √ d ≤ p ≤ 20√d, chứng tỏ dla(G) ≤ d+ 2d p + 3 √ pd √ log d+ 3 √ d p √ log d+ p− 1 ≤ d+ c.d3/4(log d)1/2. Như vậy chúng ta vừa chứng minh: Định lý 4.5.6 Có một hằng số tuyệt đối c > 0 sao cho với mọi đồ thị có hướng d-chính quy G, dla(G) ≤ d+ c.d3/4(log d)1/2. Định lý 4.5.7 Có một hằng số tuyệt đối c > 0 sao cho với mọi đồ thị vô hướng d-chính quy G, dla(G) ≤ d 2 + c.d3/4(log d)1/2. 4.6 Bước chuyển Latin Trong mục này chúng ta trình bày một áp dụng thú vị, theo Erdos và Spencer (1991). Gọi A = (aij) là một ma trận cấp n ì n với các phần tử nguyên. 52 Một phép thế pi được gọi là một bước chuyển Latin của A nếu các phần tử aipi(i) (1 ≤ i ≤ n) đều phân biệt với nhau. Định lý 4.6.1 Giả sử k ≤ (n−1)/(4e) và giả sử không có số nguyên nào xuất hiện trong nhiều hơn k phần tử của A, Thế thì A có một Bước chuyển Latin. Chứng minh. Gọi pi là một phép thế ngẫu nhiên của {1, 2, . . . , n}, được chọn theo phân phối đều trong số tất cả n! phép thế. Kí hiệu bởi T tập tất cả các bộ bốn có thứ tự (i, j, i′, j′) thỏa mãn i < i′, j 6= j′ và aij = ai′j′. Cho mỗi (i, j, i′, j′) ∈ T , kí hiệu Aiji′j′ là sự kiện pi(i) = j và pi(i′) = j′. Sự tồn tại của Bước chuyển Latin tương đương với phát biểu rằng không có sự kiện nào trong số các sự kiện này là đúng với xác suất dương. Chúng ta xác định một đồ thị có hướng đối xứng G trên tập đỉnh T bằng cách tạo (i, j, i′, j′) kề với (p, q, p′, q′) nếu và chỉ nếu {i, i′} ∩ {p, p′} 6= ∅ hoặc {j, j′} ∩ {q, q′} 6= ∅ hoặc aj = apq. Như vậy, hai bộ bốn mà không kề nhau nếu và chỉ nếu bốn ô {i, i′}, {p, p′}, {j, j′}, {q, q′} nằm ở bốn hàng và bốn cột phân biệt của A và aj 6= apq. Bậc lớn nhất của G là nhỏ hơn 4nk; thực vậy, với một (i, j, i′, j′) ∈ T đã cho có nhiều nhất 4n cách chọn (s, t) với hoặc s ∈ {i, i′} hoặc t ∈ {j, j′}, và với mỗi cách chọn (s, t) này có ít hơn k cách chọn cho (s′, t′) 6= (s, t) với ast = as′t′. Mỗi bộ bốn (s, t, s′, t′) như thế có thể viết duy nhất dạng (p, q, p′, q′) với p < p′. Do e.4nk. 1 n(n−1) ≤ 1, kết quả mong muốn suy ra từ chú ý đối với bản đối xứng của Bổ đề Địa phương, nếu chúng ta chỉ ra được Pr(Aiji′j′| ∧ S Apqp′q′) ≤ 1 n(n− 1) (16) cho (i, j, i′, j′) ∈ T tùy ý và tập S tùy ý của các thành viên của T mà không kề với (i, j, i′, j′) trong G. Bởi đối xứng, chúng ta có thể giả sử rằng i = j = 1, i′ = j′ = 2 và các giá trị của p và q không là 1 hoặc 2. Chúng ta gọi một phép thế pi tốt nếu nó thỏa mãn ∧ S Apqp′q′, và gọi Sij là tập tất cả các phép thế tốt pi thỏa mãn pi(1) = i và pi(2) = j. Chúng ta khẳng định rằng |S12| ≤ |Sij| cho tất cả i 6= j. Thực vậy, trước hết giả sử rằng i, j > 2. Cho mỗi pi ∈ S12 tốt xác định một phép thế pi∗ như sau. Giả sử pi(x) = i, pi(y) = j. Thế thì xác định pi∗(1) = i, pi∗(2) = j, pi∗(x) = 1, 53 pi∗(y) = 2 và pi∗(t) = pi(t) cho tất cả t 6= 1, 2, x, y. Chúng ta có thể kiểm tra dễ dàng rằng pi∗ là tốt, do các ô (1, i), (2, j), (x, 1), (y, 2) không là thành phần của (p, q, p′, q′) ∈ S. Như vậy pi∗ ∈ Sij , và do ánh xạ pi → pi∗ là đơn ánh |S12| ≤ |Sij|, như đã khẳng định. Tương tự chúng ta có thể xác định một đơn ánh chỉ ra rằng |S12| ≤ |Sij| thậm chí khi {1, 2} ∩ {i, j} 6= ∅ . Nó suy ra rằng Pr(A1122 ∧ ∧ S Apqp′q′) ≤ Pr(A1i2j ∧ ∧ S Apqp′q′) cho tất cả i 6= j và như thế Pr(A1122| ∧ S Apqp′q′) ≤ 1 n(n− 1). Bởi tính đối xứng, điều này chứng tỏ (16) và hoàn thành chứng minh.  4.7 Khía cạnh giải thuật Cho (n, d) là những số nguyên dương. Chúng ta mô tả bài toán (n, d) như sau: cho các tập A1, . . . , AN ⊆ Ω với mọi |Ai| = n, sao cho không có tập Ai nào giao với nhiều hơn d tập Aj khác, tìm một cách tô hai màu của Ω sao cho không có tập Ai nào đơn màu. Khi e(d + 1) < 2 n−1 , Định lý 4.2.1 khẳng định bài toán có lời giải. Chúng ta có thể tìm một cách tô màu trong số lần đa thức (của N khi n, d cố định)? Beck đưa ra câu trả lời khẳng định với một số giả thiết nghiêm ngặt hơn. Chúng ta giả sử Ω có dạng Ω = {1, . . . ,m},m ≤ Nn, và danh sách các cấu trúc dữ liệu ban đầu bao gồm danh sách các phần tử của các tập Ai và danh sách cho mỗi i các j mà j ∈ Ai. Chúng ta gọi G kí hiệu đồ thị phụ thuộc với các đỉnh là các tập Ai và Ai, Aj kề nhau nếu chúng giao nhau. Định lý 4.7.1 Cho n, d như thế, đặt D = d(d − 1)3 có tồn tại một phân tích n = n1 + n2 + n3 với 16D(1 + d) < 2n1, 16D(1 + d) < 2n2, 2e(1 + d) < 2n3. 54 Thế thì có một giải thuật ngẫu nhiên với số lần chạy trung bình O(N(lnN)c) cho bài toán (n, d), ở đây c là một hằng số (chỉ phụ thuộc vào n và d). Chứng minh. Bước Một. Trong suốt bước này, các điểm hoặc đỏ, xanh, không màu hoặc giữ lại. Chúng ta xếp các điểm j ∈ Ω thành dãy, tô màu chúng đỏ hoặc xanh ngẫu nhiên, tung một đồng xu. Sau khi mỗi j được tô màu chúng ta kiểm tra tất cả Ai 3 j. Nếu bây giờ Ai có n1 điểm trong một màu và không có điểm nào trong màu khác ta gọiAi là nguy hiểm. Tất cả các k ∈ Ai không màu bây giờ được xem là giữ lại. Khi các điểm giữ lại k được chọn trong dãy chúng sẽ không bị tô màu mà đơn giản là bỏ qua. Khi kết thúc Bước Một các điểm là đỏ, xanh hay giữ lại. Chúng ta nói một tập Ai sống sót nếu chúng không chứa các điểm cả xanh và đỏ. Kí hiệu S ⊆ G tập ngẫu nhiên của các tập sống sót. Khẳng định 4.7.2 Tất cả các thành tố C của G|S có cỡ O(lnN), hầu chắc chắn. Chứng minh. Một Ai ∈ S có thể là nguy hiểm hay, có thể, nhiều điểm của nó được giữ lại vì tập các lân cận của nó đã nguy hiểm. Xác suất để một Ai cụ thể trở thành nguy hiểm nhiều nhất là 2 1−n1 do khi tô màu n1 điểm đầu tiên thì chúng phải cùng màu. (Chúng ta có bất đẳng thức do n1 điểm của Ai phải được tô màu trước khi chúng bị giữ lại.) Gọi V là một tập độc lập trong G; nghĩa là, tập mà các Ai là đôi một rời nhau. Thế thì xác suất để tất cả các Ai ∈ V trở thành nguy hiểm nhiều nhất là (21−n1)|V |. Bây giờ lấy V ⊆ G như vậy mà khoảng cách của tất cả các Ai ∈ V ít nhất là bốn, khoảng cách được tính là độ dài đường ngắn nhất trong G. Chúng ta khẳng định rằng Pr[V ⊆ S] ≤ (d+ 1)|V |(21−n1)|V |. Đây là vì cho mỗi Ai ∈ V có nhiều nhất d + 1 cách chọn cho một lân cận nguy hiểmAi′, đưa đến (d+ 1) |V | cách chọn choAi′. Vì cácAi cách nhau ít nhất bốn nên Ai′ không thể là kề và có xác suất để tất cả chúng là nguy hiểm nhiều nhất là (21−n1)|V |, như đã khẳng định. Gọi T ⊆ G là một 4-cây nếu khoảng cách giữa tất cả cácAi ∈ T với nhau là ít nhất bốn và sao cho, vẽ một cung giữaAi, Aj và nếu khoảng cách giữa chúng 55 đúng là bốn thì đồ thị kết quả là liên thông. Chúng ta trước hết đánh giá số các 4-cây có cỡ u. Đồ thị khoảng cánh bốn xác định trên T phải chứa một cây. Có ít hơn 4j cây (theo nghĩa đẳng cấu) trên j đỉnh, bây giờ cố định một cái. Chúng ta có thể dán nhãn cây 1, . . . , u sao cho mỗi j > 1 là kề với một i < j nào đó. Bây giờ xét số các (A1, . . . , Au) mà đồ thị khoảng cách bốn của nó tương ứng với cây này. Có N cách chọn cho A1. Với Ai đã chọn cho tất cả i < j tập Aj phải có khoảng cách bốn từ Ai trong G và có nhiều nhất D điểm như vậy. Vậy số các 4-cây có cỡ u nhiều nhất là 4uNDu−1 < N(4D)u. Cho 4-cây T cụ thể nào đó chúng ta có Pr[T ⊆ S] ≤ [(d + 1)21−n1]u. Vậy số kì vọng các 4-cây T ⊆ S nhiều nhất là N [8D(d+ 1)2−n1]u. Vì số hạng trong ngoặc nhỏ hơn 1/2 theo giả thiết, cho u = c1 lnN số hạng này là o(1). Như vậy G|S sẽ không chứa 4-cây có cỡ lớn hơn c1 lnN hầu chắc chắn. Chúng ta đang muốn đánh giá cỡ của các thành tố C trong G|S. Một 4-cây T trong một thành tố C phải có tính chất rằng mỗi Ai ∈ C nằm trong khoảng cách ba của một Aj ∈ T . Có ít hơn d3 (một hắng số) Ai trong khoảng cách ba củaAj nào đó dã cho sao cho c1 lnN ≥ |T | ≥ |C|d−3 nên, |C| ≤ c2 lnN chứng minh khẳng định. Trong số thời gian tuyến tính trung bình Bước Một sẽ thành công. Bây giờ cố định các điểm đỏ hoặc xanh. Bỏ qua các tập chứa cả các điểm màu đỏ và màu xanh. Cho mỗi Ai sống sót cố dịnh một tập con Bi gồm n − n1 điểm giữ lại. Bây giờ tô màu các điểm giữ lại sao cho không có Bi nào đơn màu là xong. Bi tách vào các thành tố có cỡ O(lnN) và tô màu mỗi thành tố này riêng biệt là xong. Trong Bước Hai chúng ta áp dụng phương pháp của Bước Một đối với mỗi thành tố của Bi. Bây giờ chúng ta gọi một tập Bi là nguy hiểm nếu nó chứa đúng n2 điểm cùng một màu và các điểm khác được giữ lại. Bước Hai tốn thời gian trung bình O(lnM) để tô màu một thành tố cỡM , vậy một thời gian trung bình O(N) để tô màu tất cả các thành tố. (Để thành công chúng ta yêu cầu rằng một thành tố cỡM bị phá thành các thành tố cỡ c2 lnM . Để tránh tầm thường, nếuM < ln lnN thì chúng ta bỏ qua Bước Hai với thành tố tương ứng.) Khi kết thúc Bước Hai (vẫn trong thời gian tuyến 56 tính!) có một họ các tập sống sót hai lần Ci ⊂ Bi ⊂ Ai có cỡ n3, thành tố lớn nhất của chúng có cỡ O(ln lnN). Chúng ta vẫn cần tô màu O(N) thành tố cỡ O(ln lnN) này, mỗi thành tố có cỡ n3. Theo Bổ đề Địa Phương (hay trực tiếp theo Định lý 4.2.1), mỗi thành tố này có thể là hai sắc. Chúng ta đã tìm được một cách tô hai màu bằng cách tô màu nhiều chặng! Kiểm tra tất cả các cách tô hai màu của một thành tố có cỡM tốn O(M2nM) lần, ứng với O((lnN)c) trong trường hợp của chúng ta. Làm điều này cho tất cả các thành tố tốn O(N(lnN)c) lần. Đến đây hoàn thành cách tô màu.  57 Chương 5 ChứngminhđịnhlýWeierstrasstheophươngphápxácsuất Trong giải tích cơ sở ta biết nếu một hàm số thực f(x) có đạo hàm mọi cấp trong lân cận của điểm x = 0 thì có thể biểu diễn nó thành chuỗi lũy thừa dạng ∑∞ n=0 anx n . Gọi K là bán kính hội tụ của chuỗi lũy thừa này thì chuỗi hội tụ với mọi |x| ≤ R, (0 0 cho trước, ta có thể lấy một tổng riêng đủ lớn của chuỗi là Pn(x) = ∑n k=0 akx k (là một đa thức bậc n) sao cho |Pn(x)− f(x)| < , |x| ≤ R. Tuy nhiên nếu f không có đạo hàm mọi cấp thì không tồn tại biểu diễn của f thành dạng chuỗi lũy thừa như trên. Nhưng với f là hàm liên tục trên [a, b] ta vẫn có thể xấp xỉ đều f bởi các đa thức trên đoạn [a, b] một cách tùy ý gần. Khẳng định này là một kết quả của một định lý cơ sở quan trọng trong giải tích: Định lý xấp xỉ Weierstrass. Chương này trình bày phương pháp chứng minh định lý quan trọng đó theo công cụ xác suất và cũng cho một đánh giá về tốc độ hội tụ của xấp xỉ. Xin chú ý rằng cách dùng xác suất ở đây khác với phương pháp xác suất trình bày trong những chương trước. 5.1 Một số kiến thức xác suất cơ sở chuẩn bị Trong toàn bộ chương này ta giả sử (Ω,F,Pr) là không gian xác suất và các biến ngẫu nhiên xét đến là xác định trên Ω và nhận giá trị trong R. Biến ngẫu nhiên nhị thức Biến ngẫu nhiên X gọi là nhị thức B(n, p), p ∈ [0, 1] (chính xác là biến ngẫu nhiên có phân phối nhị thức B(n, p)) nếu như phân bố xác suất của nó 58 có dạng Pr(X = k) = ∫ {ω:X(ω)=k} Pr(dω) = ( n k ) pk(1− p)n−k, trong đó k = 0, 1, . . . , n. Hàm đặc trưng của biến ngẫu nhiên nhị thức Cho X là biến ngẫu nhiên, hàm đặc trưng ϕ(t) của X được định nghĩa như sau: ϕ(t) = E[eitX], t ∈ R (kỳ vọng lấy theo độ đo xác suất Pr). VớiX là biến ngẫu nhiên nhị thức ta có ϕ(t) = E[eitX] = n∑ k=0 eitk Pr(X = k) = n∑ k=0 eitk ( n k ) pk(1− p)n−k = n∑ k=0 ( n k ) (peit)k(1− p)n−k = [peit + (1− p)]n. Vậy hàm đặc trưng của biến ngẫu nhiên nhị thức là ϕ(t) = [peit + q]n, q = 1− p. (17) Nếu X1, . . . , Xn là các biến ngẫu nhiên độc lập và có cùng phân phối nhị thức B(1, p) thì ∑n k=1Xk là biến ngẫu nhiên nhị thức B(n, p). Thật vậy, đặt Sn = n∑ k=1 Xk, ta có hàm đặc trưng của Sn là ϕSn(t) = E[e itSn] = E[ei