Tài liệu Lý thuyết đồ thị và một số dạng toán thi olympic

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NÔNG THANH LOAN LÝ THUYẾT ĐỒ THỊ VÀ MỘT SỐ DẠNG TOÁN THI OLYMPIC LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2016 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NÔNG THANH LOAN LÝ THUYẾT ĐỒ THỊ VÀ MỘT SỐ DẠNG TOÁN THI OLYMPIC Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số : 60.46.01.13 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: TS. TRẦN NGUYÊN AN THÁI NGUYÊN - 2016 Mục lục Lời mở đầu 1 1 Một số khái niệm, kết quả cơ bản và ứng dụng 1.1 Các định nghĩa cơ bản và ứng dụng . . . . . . . . . . . . 1.2 Hành trình, đường, chu trình, vết và mạch . . . . . . . . 1.3 Tô màu đồ thị và ứng dụng . . . . . . . . . . . . . . . . 3 3 16 24 2 Một số lớp đồ thị đặc biệt và ứng dụng 2.1 Cây và ứng dụng . . . . . . . . . . . . . 2.2 Đồ thị Euler và ứng dụng . . . . . . . . 2.3 Đồ thị Hamilton và ứng dụng . . . . . . 2.4 Đồ thị phẳng và ứng dụng . . . . . . . . 37 37 43 47 55 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 i LỜI MỞ ĐẦU Lý thuyết đồ thị là một ngành toán học hiện đại, tuy có lịch sử phát triển mới hơn một thế kỷ nhưng có ứng dụng quan trọng vào nhiều ngành khoa học, kĩ thuật hiện đại: Vật lí, hoá học, sinh học, tin học, điều khiển học, vv... Trên thực tế có nhiều bài toán liên quan tới một tập các đối tượng và những mối liên hệ giữa chúng, đòi hỏi toán học phải đặt ra một mô hình biểu diễn một cách chặt chẽ và tổng quát bằng ngôn ngữ kí hiệu, đó là đồ thị. Trong khoảng mấy chục năm gần đây, người ta đã quan tâm nhiều tới lý thuyết đồ thị và các ứng dụng của nó. Đó là do lý thuyết đồ thị đã chứng tỏ được là một mô hình hữu hiệu cho tính toán tối ưu. Lý thuyết đồ thị còn là đối tượng nghiên cứu của Hình học đại số và Đại số giao hoán. Ngày nay khái niệm lý thuyết đồ thị đã xâm nhập không chỉ vào các lĩnh vực khoa học tự nhiên truyền thống như toán học, vật lý học hay hoá học, mà còn vào nhiều lĩnh vực khoa học tự nhiên và xã hội khác. Các bài toán đồ thị ngày càng xuất hiện nhiều hơn trong các kì thi Olympic Toán của các quốc gia cũng như các kì thi Toán quốc tế. Thông thường đây là các bài toán khó không chỉ với học sinh Việt Nam mà cả đối với cả học sinh quốc tế nói chung. Đề tài “Lý thuyết đồ thị và một số dạng toán thi Olympic” nhằm tìm hiểu một số vấn đề về lý thuyết đồ thị và ứng dụng, đặc biệc là ứng dụng trong việc giải một số dạng toán thi học sinh giỏi. Luận văn được viết dựa chủ yếu trên tài liệu chính để tham khảo là [6] và một số đề thi Olympic của các nước ... Bên cạnh việc tìm hiểu ứng dụng của lý thuyết đồ thị trong toán sơ cấp thì việc tìm hiểu những vấn đề cơ bản của lý thuyết đồ thị cũng là một mục đích chính của luận văn. Luận văn là sự tổng hợp, phân tích các dạng toán, sưu tầm các ví dụ từ nhiều nguồn tài liệu. Cấu trúc luận văn gồm hai chương: 1 Chương 1 Một số khái niệm, kết quả cơ bản và ứng dụng. Chương 1 trình bày tóm tắt một số khái niệm, kết quả cơ bản và ứng dụng, các định nghĩa cơ bản và ứng dụng, hành trình, đường, chu trình, vết và mạch, tô màu đồ thị và ứng dụng. Chương 2 Một số lớp đồ thị đặc biệt và ứng dụng. Chương 2 trình bày một số lớp đồ thị đặc biệt như cây, đồ thị Euler, đồ thị Hamilton, đồ thị phẳng và ứng dụng chủ yếu trong các bài toán Olympic. Trong suốt quá trình làm luận văn, tác giả nhận được sự hướng dẫn và giúp đỡ tận tình của Tiến sĩ Trần Nguyên An. Tác giả xin bày tỏ lòng biết ơn chân thành và sâu sắc nhất tới thầy. Tác giả xin gửi lời cảm ơn chân thành đến quý thầy cô giảng dạy lớp Cao học toán khoá 8 đã truyền thụ đến cho tác giả nhiều kiến thức và kinh nghiệm nghiên cứu khoa học. Tác giả xin chân thành cảm ơn bạn bè, đồng nghiệp và gia đình đã tạo mọi điều kiện giúp đỡ, động viên tác giả trong suốt quá trình học tập và hoàn thành luận văn này. Thái Nguyên, tháng 5 năm 2016 Tác giả Nông Thanh Loan 2 Chương 1 Một số khái niệm, kết quả cơ bản và ứng dụng Trong chương này, ta sẽ đề cập tới các mô hình đồ thị khác nhau, các khái niệm cơ bản trong lý thuyết đồ thị như hành trình, đường, chu trình, liên thông và một vài ứng dụng trong giải toán phổ thông. Lý thuyết đồ thị được bắt đầu như một lĩnh vực toán học từ những lập luận nổi tiếng của Euler về bảy chiếc cầu ở Königsberg trong một bài báo công bố vào năm 1736. Nhưng bài báo này của Euler là công trình duy nhất về lý thuyết đồ thị trong suốt gần một trăm năm sau đó. Khoảng giữa thế kỷ 19 người ta mới quay trở lại với các vấn đề của lý thuyết đồ thị, đặc biệt là ở nước Anh. Nguyên nhân của sự quay trở lại đó xuất phát từ những nghiên cứu về mạng điện, về các mô hình tinh thể và về các cấu trúc phân tử của các chất. Sự phát triển của logic hình thức đã đẩy đến việc nghiên cứu các quan hệ hai ngôi dưới dạng lý thuyết đồ thị. Sau đó nhiều bài toán khác cũng đã được phát triển trên ngôn ngữ lý thuyết đồ thị. 1.1 Các định nghĩa cơ bản và ứng dụng Như ta đã thấy ở trên, khái niệm đồ thị xuất hiện từ nhiều lĩnh vực khác nhau trong cuộc sống. Trong mỗi lĩnh vực riêng của mình, người ta cần tới một kiểu đồ thị nào đó. Vì vậy mà cũng xuất hiện nhiều loại 3 đồ thị khác nhau. Song tựu chung lại ta có thể xếp chúng vào các loại chính sau đây: đồ thị có hướng, đồ thị vô hướng, đa đồ thị có hướng, đa đồ thị vô hướng. Định nghĩa 1.1.1 (Đồ thị có hướng). Một đồ thị có hướng G là một cặp có thứ tự G = (V, E), ở đây V là một tập, còn E là một tập con của tích Đề các V × V. Các phần tử của V được gọi là đỉnh, còn các phần tử của E được gọi là các cung của đồ thị có hướng G. Cụ thể hơn, nếu (a, b) ∈ E thì (a, b) được gọi là cung của G với đỉnh đầu là a, đỉnh cuối là b và có hướng đi từ a tới b. Để được trực quan người ta thường biểu diễn đồ thị có hướng G trên mặt phẳng như sau. Các đỉnh của G được biểu diễn bằng các chấm tròn, còn các cung thì được biểu diễn bằng các đường cong nối đỉnh đầu với đỉnh cuối và có mũi tên hướng từ đỉnh đầu tới đỉnh cuối. a e f b c d Hình 1.1: Ví dụ một đồ thị có hướng Ví dụ 1.1.2. Cho G = (V, E) với V = {a, b, c, d, e, f } và E = {(a, a), (a, b), (b, d), (d, b)(c, e), (e, a)}. Khi đó G là đồ thị có hướng được biểu diễn bằng Hình 1.1. Định nghĩa 1.1.3. Giả sử G = (V, E) là một đồ thị có hướng. Nếu (a, b) ∈ E thì các đỉnh a và b được gọi là liên thuộc với cung (a, b). Khi đó a và b cũng được gọi là kề nhau. Hai cung bất kỳ của G được gọi là 4 kề nhau nếu chúng có đỉnh chung. Cung dạng (a, a) với a ∈ V được gọi là khuyên. Đỉnh không liên thuộc với một cung nào được gọi là đỉnh cô lập. Số các đỉnh của G, tức là |V |, được gọi là cấp của G, còn số các cung của G, tức là |E|, được gọi là cỡ của G. Trước khi đưa ra định nghĩa đồ thị vô hướng, ta giới thiệu khái niệm đa tập. Một sự tụ tập các vật có bản chất tùy ý, trong đó có thể có những vật không phân biệt được với nhau (và có thể coi như là sự lặp lại của cùng một vật), được gọi là đa tập hợp hay ngắn gọn là đa tập. Các vật trong đa tập cũng được gọi là các phần tử. Ta cũng dùng các phương pháp xác định tập hợp để xác định đa tập. Nhưng đối với đa tập, ta cần xác định số các phần tử không phân biệt được với nhau, số lượng các phần tử của một đa tập A cũng được gọi là lực lượng của A và được ký hiệu là |A|. Ví dụ 1.1.4. A = {a, a, a, b, c, c} là một đa tập với |A| = 6. Theo định nghĩa, hiển nhiên mỗi tập cũng là đa tập, nhưng ngược lại, một đa tập có thể không là tập hợp. Chẳng hạn, đa tập A ở trên không là tập hợp. Nếu các phần tử của một đa tập A đều là phần tử của một tập B, thì ta sẽ nói rằng A là đa tập trên B. Chẳng hạn, đa tập A ở trên là một đa tập trên tập B = {a, b, c}. Định nghĩa 1.1.5 (Đồ thị vô hướng). Một đồ thị vô hướng G là một cặp có thứ tự G = (V, E), ở đây V là một tập, còn E là tập với các phần tử là các đa tập lực lượng 2 trên V . Các phần tử của V cũng được gọi là các đỉnh, còn các phần tử của E được gọi là các cạnh của đồ thị có hướng G. Nếu e = {a, b} là một cạnh của G thì a và b được gọi là các đỉnh đầu mút của cạnh e hay các đỉnh liên thuộc với e. Ta cũng thường ký hiệu cạnh {a, b} ngắn gọn là ab. Người ta cũng thường biểu diễn đồ thị vô hướng trên mặt phẳng tương 5 tự như ta biểu diễn đồ thị có hướng: các đỉnh của đồ thị được biểu diễn bằng các chấm tròn, còn các cạnh thì được biểu diễn bằng một đường cong nối các đỉnh của cạnh. Điểm khác biệt ở đây là không có mũi tên chỉ hướng trên các đường cong đó. a b d c Hình 1.2: Ví dụ một đồ thị vô hướng Ví dụ 1.1.6. Cho G = (V, E) với V = {a, b, c, d} và E = {{a, a}, {a, b}, {b, d}, {b, c}, {c, d}}. Khi đó G là đồ thị vô hướng được biểu diễn bằng Hình 1.2. Đồ thị có hướng được định nghĩa ở trên cũng thường được gọi là đơn đồ thị có hướng. Lý do là vì với hai đỉnh a và b bất kỳ tồn tại duy nhất một cung với đỉnh đầu là a và đỉnh cuối là b. Với lý do tương tự, đồ thị vô hướng được định nghĩa ở trên cũng thường được gọi là đơn đồ thị vô hướng. Tuy nhiên, trong một số ứng dụng ta cần có nhiều cung với cùng đỉnh đầu và đỉnh cuối hay cần có nhiều cạnh cùng liên thuộc với hai đỉnh đã cho. Vì vậy, người ta đưa ra khái niệm đa đồ thị có hướng và đa đồ thị vô hướng. Định nghĩa 1.1.7 (Đa đồ thị có hướng và đa đồ thị vô hướng). Một đa đồ thị có hướng G là một cặp có thứ tự G = (V, E), ở đây V là một 6 tập, còn E là một đa tập với các phần tử đều thuộc tích Đề các V × V. Đa đồ thị có hướng cũng được biểu diễn trên mặt phẳng tương tự như đồ thị có hướng, trong đó các cung có cùng đỉnh đầu và đỉnh cuối phải được biểu diễn bằng các đường cong khác nhau. Tương tự một đa đồ thị vô hướng G là một cặp có thứ tự G = (V, E), ở đây V là một tập, còn E là một đa tập với các phần tử đều là đa tập lực lượng 2 trên V . Trong biểu diễn trên mặt phẳng của đa đồ thị vô hướng, các cạnh khác nhau nhưng có các đỉnh đầu mút như nhau phải được biểu diễn bằng các đường cong khác nhau. a b c d Hình 1.3: Ví dụ một đa đồ thị có hướng a d b Hình 1.4: Ví dụ một đa đồ thị vô hướng 7 c Ví dụ 1.1.8. Cho G1 = (V, E1 ) với V = {a, b, c, d, e, f } và E1 = {(a, c), (a, c), (c, a), (d, c)(a, d), (d, a), (b, a), (d, b), (d, b)} là một đa đồ thị có hướng, còn cặp G2 = (V, E2 ) với V = {a, b, c, d} và E2 = {{a, d}, {a, d}, {d, a}, {c, d}, {a, c}, {c, a}, {b, a}, {c, b}, {c, b}} là một đa đồ thị vô hướng. G1 và G2 được biểu diễn trên mặt phẳng tương ứng như trên Hình 1.3 và Hình 1.4. Đồ thị G′ = (V ′ , E ′ ) được gọi là đồ thị con của đồ thị G = (V, E) nếu V ′ ⊆ V và E ′ ⊆ E. Đồ thị con G′ = (V ′ , E ′ ) của đồ thị G = (V, E) được gọi là đồ thị con bao trùm của G nếu V ′ = V . Nếu E ′ chứa tất cả các cung hay cạnh của G, mà cả hai đỉnh liên thuộc với nó đều thuộc V ′ , thì G′ = (V ′ , E ′ ) được gọi là đồ thị con của G = (V, E) cảm sinh bởi tập đỉnh V ′ hay cũng được gọi là đồ thị con cảm sinh bởi G = (V, E) trên tập đỉnh V ′ . Khi đó G′ cũng được ký hiệu là G′ = G[V ′ ]. Ta thường phải xây dựng các đồ thị mới từ các đồ thị đã cho bằng cách xóa hay thêm một số đỉnh hoặc cạnh. Nếu W ⊆ V , thì G − W = G [V \ W ], tức là đồ thị con của G nhận được từ G bằng cách xóa đi cách đỉnh thuộc W và mọi cung (hay cạnh) liên thuộc với các đỉnh trong W . Tương tự, nếu E ′ ⊆ E thì G − E ′ = (V, E \ E ′ ). Nếu W = {w} và E ′ = {(x, y)} (hay E ′ = {x, y} ) thì ký hiệu ở trên được đơn giản viết thành (G − w) và G − (x, y) (hay (G − xy) ). Tương tự, nếu x và y không kề nhau trong G thì G + (x, y) (hay G + xy ) là đồ thị nhận được từ G bằng cách nối x với y bằng cung (x, y) (tương ứng, bằng cạnh xy). Nếu G1 = (V1 , E1 ) và G2 = (V2 , E2 ) là hai đồ thị đã cho, thì hợp của hai đồ thị này, ký hiệu là G1 ∪ G2 , là đồ thị với tập đỉnh là V1 ∪ V2 và tập cung (hay cạnh) E1 ∪ E2 . Nếu cả hai đồ thị G1 và G2 là đồ thị vô hướng, thì kết nối của hai đồ thị G1 và G2 , ký hiệu là G1 + G2 , là đồ thị nhận được từ G1 ∪ G2 bằng cách thêm vào tất cả các cạnh dạng xy với x ̸= y và x ∈ V1 , y ∈ V2 . Hiển nhiên là nếu một đồ thị vô hướng không có khuyên có cấp bằng 8 n thì cỡ m của nó thỏa mãn 0 ≤ m ≤ (n) 2 . Đồ thị vô hướng cấp n và cỡ m = 0 được gọi là n-đồ thị rỗng hay n-đồ thị hoàn toàn rời rạc và được kí hiệu là On hay En . Còn đồ thị vô hướng không có khuyên cấp n và cỡ ( ) m = n2 được gọi là n-đồ thị đầy đủ và thường được ký hiệu là Kn . Giả sử G = (V, E) là đồ thị vô hướng không có khuyên với |V | = n. Ta định nghĩa đồ thị bù của G, ký hiệu là G , là đồ thị vô hướng với tập đỉnh cũng là V , còn tập cạnh là E(Kn )\E. Lớp đồ thị đặc biệt sau đây gọi là đồ thị m-phần cũng thường được chú ý. Một đồ thị vô hướng không có khuyên G = (V, E) được gọi là đồ thị m-phần nếu ta có thể phân hoạch V thành dạng V = V1 ∪V2 ∪...∪Vm với Vi ̸= ∅, i = 1, 2, ..., m sao cho các đỉnh trong cùng Vi , i = 1, 2, ..., m, là không kề nhau. Nếu G là đồ thị m-phần và tồn tại cạnh nối một đỉnh bất kỳ của Vi với một đỉnh bất kỳ của Vj cho mọi i ̸= j thì G được gọi là m-phần đầy đủ. Đồ thị 2-phần đầy đủ, trong đó các phần V1 và V2 có |V1 | = m, |V2 | = n được ký hiệu là Km,n . Giả sử G = (V, E) là một đồ thị có hướng và v ∈ V . Ký hiệu N + (v) = {x ∈ V |(v, x) ∈ E}, N − (v) = {y ∈ V |(y, v) ∈ E}. Khi đó |N + (v)| được gọi là bậc đi ra, còn |N − (v)| được gọi là bậc đi vào của v. Bây giờ giả sử G = (V, E) là một đồ thị vô hướng và v ∈ V . Ký hiệu NG (v) = {x ∈ V |x ̸= v, và {x, v} ∈ E} Khi đó NG (v) được gọi là tập các láng giềng của v. Trong trường hợp đồ thị G được hiểu ngầm, ta ký hiệu NG (v) đơn giản bằng N (v). Định nghĩa 1.1.9. Ta định nghĩa bậc của đỉnh v trong đồ thị vô hướng G, ký hiệu là degG (v) hay ngắn gọn là deg(v) nếu như G được hiểu ngầm, 9 { |N (v)|, nếu {v, v} ∈ /E deg(v) = |N (v)| + 2, nếu {v, v} ∈ E . như sau: (1.1) Ta cũng kí hiệu δ(G) = min deg(v), v∈V ∆(G) = max deg(v), v∈V và gọi chúng tương ứng là bậc nhỏ nhất và bậc lớn nhất của các đỉnh của G. Nếu δ(G) = ∆(G) = k, thì mọi đỉnh của G đều có bậc là k và G được gọi là đồ thị chính qui bậc k hay ngắn gọn là k-chính qui. Một đồ thị vô hướng được gọi là chính qui nếu nó là k-chính qui với một k nào đấy. Đồ thị vô hướng k-chính qui cũng được gọi là đồ thị bậc k. Có những đồ thị khác nhau nhưng khi đổi tên các đỉnh của các đồ thị đó thì chúng lại có thể trùng nhau. Những đồ thị như thế được đọi là đẳng cấu và trong lý thuyết đồ thị người ta thường đồng nhất chúng. Cụ thể hơn, đồ thị có hướng (tương ứng, vô hướng) G = (V, E) và G′ = (V ′ , E ′ ) được gọi là đẳng cấu với nhau nếu tồn tại song ánh φ : V → V ′ sao cho (a, b) ∈ E (tương ứng, {a, b} ∈ E) khi và chi khi (φ(a), φ(b)) ∈ E (tương ứng, {φ(a), φ(b)} ∈ E). Song ánh φ như trên được gọi là đẳng cấu của G và G′ . Hai đồ thị đẳng cấu với nhau G và G′ được kí hiệu là G ∼ = G′ . G′ = (V ′ , E ′ ) G = (V, E) 1 4 a 3 2 f b e c d 6 5 Hình 1.5: Ví dụ hai đồ thị vô hướng đẳng cấu 10 Ví dụ 1.1.10. Giả sử G = (V, E) và G′ = (V ′ , E ′ ) là các đồ thị vô hướng trong Hình 1.5. Khi đó G ∼ = G′ và ánh xạ φ : V → V ′ với φ(1) = a, φ(5) = b, φ(2) = c, φ(6) = d, φ(3) = e, φ(4) = f là đẳng cấu của G và G’. Định lý 1.1.11 (Bổ đề bắt tay). Trong đồ thị vô hướng G = (V, E) bất kỳ ta luôn có ∑ deg(v) = 2 |E|. v∈V Chứng minh. Mỗi x ∈ N (v) ta tương ứng với e = {v, x} ∈ E. Dễ thấy rằng tương ứng này là song ánh giữa N (v) và E(v) = {{v, x} ∈ E|v ̸= x}. Vì thế ∑ |N (v)| = v∈V ∑ |Ev |. v∈V Vì mỗi cạnh {v, x} ∈ E với v ̸= x có hai đỉnh liên thuộc với nó là v và x, nên trong tổng ở vế phải mỗi {v, x} ∈ E với v ̸= x đã được tính đúng hai lần: một lần trong Ev và một lần trong Ex . Do đó, ∑ |E(v)| = 2|E1 |, v∈V ở đây E1 là tập tất cả các cạnh không phải là khuyên của G. Do đó ∑ |N (v)| = 2|E1 |. v∈V Mặt khác, ta có E2 = E \ E1 là tập tất cả khuyên của G. Ký hiệu V1 = {v ∈ V |{v, v} ∈ / E}, V2 = {v ∈ V |{v, v} ∈ E}. Khi đó, vì với mỗi đỉnh v ∈ V2 , ta có đúng một khuyên {v, v} ∈ E, nên |V2 | = |E2 |. Vì vậy, ∑ ∑ ∑ ∑ ∑ deg(v) = deg(v) + deg(v) = |N (v)| + |N (v)| + 2 |V2 | v∈V∑ v∈V1 v∈V2 v∈V1 v∈V2 = |N (v)| + 2 |V2 | = 2 |E1 | + 2 |E2 | = 2 |E| . v∈V 11 Ta có thể sử dụng khái niệm bậc của đỉnh (định nghĩa 1.1.9) và một số kết quả trên của lý thuyết đồ thị để giải một số bài toán ở phổ thông. Ta thường sử dụng một số kết quả sau: (i) Trong mọi đồ thị G, tổng tất cả các bậc của các đỉnh là một số chẵn, bằng hai lần tổng tất cả các cạnh của G (Xem Định lý 1.1.11). (ii) Trong mọi đồ thị có n đỉnh (n ≥ 2) không có khuyên, bao giờ cũng có ít nhất hai đỉnh cùng bậc. (iii) Nếu một đồ thị G với n đỉnh (n > 2) có đúng hai đỉnh cùng bậc thì G phải có đúng một đỉnh bậc 0 hoặc đúng một đỉnh bậc n − 1. Bài toán sau là trường hợp cụ thể của (ii). Bài toán 1.1.12. Có 10 đội bóng thi đấu với nhau, mỗi đội phải đấu một trận với các đội khác. Chứng minh rằng vào bất cứ lúc nào cũng có hai đội đã đấu được một số trận như nhau. Giải. Ta chuyển bài toán về đồ thị: Cho tương ứng mỗi đội bóng với một đỉnh của đồ thị; khi hai đội đã đấu với nhau thì ta nối hai đỉnh tương ứng bằng một cạnh; bậc của mỗi đỉnh bằng số trận mà đội tương ứng đã thi đấu. Ta phải giải bài toán sau: Cho đồ thị với 10 đỉnh. Chứng minh rằng bao giờ cũng có hai đỉnh cùng bậc. Thật vậy, trong một đồ thị có 10 đỉnh, không thể có đồng thời một đỉnh (A chẳng hạn) bậc 0 và một đỉnh (B chẳng hạn) bậc 9. Bởi vì nếu B có bậc 9 thì B là đầu mút của 9 cạnh nối B với 9 đỉnh còn lại, trong đó có A, do đó A không thể có bậc 0; ngược lại, nếu A có bậc 0 thì B nhiều lắm cũng chỉ có bậc 8. Có 10 đỉnh, mà mỗi đỉnh chỉ có thể có một trong 9 bậc (từ 0 đến 8, hoặc từ 1 đến 9), vì vậy theo nguyên lý Dirichlet phải có ít nhất hai đỉnh có cùng bậc. Bài toán sau là trường hợp cụ thể của (iii). 12 Bài toán 1.1.13. Có 10 đội bóng thi đấu với nhau, mỗi đội phải đấu một trận với các đội khác. Có một lúc, người ta nhận thấy có đúng hai đội (*) đã đấu một số trận như nhau. Chứng minh rằng lúc đó hoặc đúng một đội chưa thi đấu trận nào, hoặc đúng một đội đã thi đấu với tất cả đội khác. Giải. Ta chuyển bài toán về đồ thị: Cho đồ thị G có 10 đỉnh. Chứng minh rằng nếu G có đúng hai đỉnh cùng bậc thì G phải có đúng một đỉnh bậc 0 hoặc đúng một đỉnh bậc 9. Trước hết, ta chứng minh rằng nếu G có đúng hai đỉnh cùng bậc thì bậc đó không thể là 0 mà cũng không thể là 9. Thực vậy, nếu G có đúng hai đỉnh cùng bậc và bậc này là 0 (các đỉnh khác có bậc đôi một khác nhau) thì khi loại bỏ hai đỉnh cô lập này đi, ta được một đồ thị G′ với 8 đỉnh có bậc đôi một khác nhau, điều này là vô lý với bài toán trên. Còn nếu G có đúng hai đỉnh cùng bậc và bậc này là 9 thì đồ thị bù Ḡ của G có hai đỉnh cùng bậc 0 và các đỉnh khác có bậc đôi một khác nhau, vô lý với lập luận ở trên. Như vậy, bài toán đã được chứng minh. Sau đây là bài toán ứng dụng khái niệm đồ thị có hướng đã trình bày ở phần 1.1. Bài toán 1.1.14. Trên tập hợp S, cho quan hệ → giữa các cặp phần tử của S với các tính chất sau: 1) Với mọi phần tử khác nhau a, b ∈ S, có đúng một quan hệ a → b hoặc b → a; 2) Với mọi bộ ba phần tử khác nhau a, b, c ∈ S, nếu có a → b và b → c thì cũng có c → a. Hỏi tập hợp S có thể chứa nhiều nhất là bao nhiêu phần tử? Giải. Ta vẽ đồ thị với đỉnh là các phần tử của S. 13 a a c b a) b a c b) Hình 1.6 b c c) d Theo giả thiết, với bất cứ ba đỉnh a, b, c nào, ta cũng có đồ thị con như trong Hình 1.6 (a hoặc b), ở đó mỗi đỉnh là điểm đi ra (điểm đầu) của một cung (mũi tên) khác. Từ đó, nếu có đỉnh thứ tư d (Hình 1.6c) và xét ba đỉnh a, b, d thì ta phải có b → d; nhưng nếu xét ba đỉnh b, c, d thì ta phải có d → b, điều đó mâu thuẫn với giả thiết là có một và chỉ một trong hai quan hệ b → d hoặc d → b. Vậy S có thể có nhiều nhất là ba phần tử. Bài toán 1.1.15 (IMO, 1988). Giả sử n là một số nguyên dương và A1 , A2 , ..., A2n+1 là các tập hợp con của tập hợp B. Giả sử rằng (1) Mỗi Ai có đúng 2n phần tử; ∩ (2) Mỗi Ai Aj (1 ≤ i < j ≤ 2n + 1) có đúng một phần tử; (3) Mỗi phần tử của B đều thuộc ít nhất hai tập con Ai . Hỏi với giá trị nào của n thì chúng ta có thể đánh dấu mọi phần tử của B bởi các con số 0 và 1 sao cho Ai có đúng n phần tử được đánh số 0. Giải. Lúc đầu , từ "ít nhất" trong điều kiện có thể thay thế bằng từ ∩ ∩ "chính xác". Nếu có một phần tử ai ∈ A1 A2n A2n+1 , thì mỗi tập hợp còn lại trong số 2n − 2 tập hợp A2 , A3 , ..., A2n−1 có ít nhất các phần tử của A1 . Vì thế có ít nhất một phần tử thuộc A1 nhưng không ∪ ∪ ∪ ∪ ∪ thuộc A2 A3 ... A2n−1 A2n A2n+1 . Nó mâu thuẫn với (3). 14 Xây dựng đồ thị đầy đủ K2n+1 , trong đó mọi đỉnh vi đại diện cho một tập hợp Ai và mọi cạnh (vi , vj ) = eij (1 ≤ i, j ≤ 2n + 1, i ̸= j) đại diện cho phần tử chung của Ai , Aj . Vì thế câu hỏi có thể được thay đổi thành: Tính chất gì của n thoả mãn điều đó bằng cách gán các cạnh của K2n+1 là 0 hoặc 1, đúng n cạnh của 2n cạnh bất kỳ đến đỉnh vi được đánh số 0 ? K2n+1 có n(2n + 1) cạnh. Nếu yêu cầu của việc đánh số có thể làm được, thì có 21 n(2n + 1) cạnh được đánh số 0. Vì thế n phải là số chẵn. Ngược lại, nếu n = 2m là chẵn, chúng ta gán cạnh (vi , vi−m ), (vi , vi−m+1 ) ,..., (vi , vi−1 ), (vi , vi+1 ) , ... , (vi , vi+m ), i = 1, 2, ..., 2n + 1 là 0, nếu không thì là 1 trong K2n+1 . Phương pháp này đáp ứng yêu cầu (chú ý v(2n+1)+i = vi ). Vì thế, yêu cầu của câu hỏi được thoã mãn nếu và chỉ nếu n là số chẵn. Bài toán 1.1.16 (China Mathematical Competition, 1986). Có n người, hai người bất kỳ trong số đó có một cuộc trò chuyện bằng điện thoại với nhau ít nhất một lần. Bất kỳ n − 2 người trong số đó có cuộc nói chuyện bằng điện thoại 3m lần, trong đó m là một số tự nhiên. Hãy tìm n. Giải. Ta có n ≥ 5. Ký hiệu n người bởi n đỉnh A1 , A2 , ..., An . Nếu Ai , Aj có một cuộc trò chuyện bằng điện thoại, thì có một cạnh (Ai , Aj ). Như vậy, có một cạnh nối 2 đỉnh trong n đỉnh. Không mất tính tổng quát, chúng ta giả sử rằng đó là cạnh (A1 , A2 ). Giả sử không có cạnh nối đỉnh A1 và A3 . Xem xét n − 2 đỉnh A1 , A4 , A5 , ..., An ; A2 , A4 , A5 , ..., An và A3 , A4 , A5 , ..., An . Chúng ta biết số cạnh nối từ các đỉnh A1 , A2 , A3 bất kỳ đến tất cả các đỉnh A4 , A5 , ..., An là bằng nhau và chúng ta ký hiệu là k. Thêm đỉnh A2 vào tập hợp A1 , A4 , A5 , ..., An , thì có S = 3m +k +1 15 cạnh nối n − 1 đỉnh. Lấy bất kì đỉnh nào từ n − 1 đỉnh, số cạnh nối n − 2 đỉnh còn lại luôn là 3m . Vì thế có k + 1 cạnh nối mỗi đỉnh và n − 2 đỉnh còn lại. Vì thế, 1 S = (n − 1)(k + 1). 2 Tương tự, thêm A3 vào tập hợp A1 , A4 , A5 , ..., An . Chúng ta nhận 1 được n − 1 đỉnh và số cạnh là t = 3m + k = (n − 1)k. 2 Vì S = t + 1, chúng ta có 1 1 (n − 1)(k + 1) = (n − 1)k + 1, 2 2 với n = 3. Mâu thuẫn. Như vậy có một cạnh nối A1 , A3 . Tương tự, cũng có một cạnh nối A2 và A3 . Ngoài ra, phải có các cạnh nối A1 , A2 và tất cả các đỉnh Ai (i = 3, 4, ..., n) . Với Ai , Aj (i ̸= j), có một cạnh nối Ai và Aj . Vì thế, có một cạnh nối Ai và Aj . Như vậy, đồ thị này là đồ thị đầy đủ. Từ đó suy ra 1 3m = (n − 2)(n − 3). 2 Vậy chúng ta có n = 5. 1.2 Hành trình, đường, chu trình, vết và mạch Trong mục này chúng tôi sẽ trình bày định nghĩa hành trình (đường đi) có hướng, hành trình vô hướng, định nghĩa đường, chu trình, đồ thị liên thông. Định nghĩa 1.2.1. Giả sử G = (V, E) là một đồ thị có hướng. Một hành trình (đường đi) có hướng trong G là một dãy v0 e1 v1 e2 v2 .....en vn sao cho với mọi i = 0, 1, ..., n, vi ∈ V , còn với mọi i = 1, 2, ..., n, ei ∈ E và ei = (vi−1 , vi ). Khi đó n được gọi là độ dài, đỉnh v0 được gọi là đỉnh đầu, còn vn được gọi là đỉnh cuối của hành trình có hướng trên. Tương 16 tự, một hành trình vô hướng trong G là một dãy v0 e1 v1 e2 v2 .....en vn sao cho với mọi i = 0, 1, ..., n, vi ∈ V , còn với mọi i = 1, 2, ..., n, ei ∈ E và hoặc ei = (vi−1 , vi ) hoặc ei = (vi , vi−1 ). Khi đó n cũng được gọi là độ dài, đỉnh v0 được gọi là đỉnh đầu, còn đỉnh vn được gọi là đỉnh cuối của hành trình vô hướng trên. Một hành trình (có hướng, vô hướng) được gọi là khép kín (chu trình) nếu đỉnh đầu và đỉnh cuối của nó trùng nhau. e2 v2 e1 v3 e7 v5 e9 e4 e8 e3 v4 v1 e5 e6 v6 Hình 1.7: Dùng để minh hoạ cho hành trình trong đồ thị Ví dụ 1.2.2. Giả sử G = (V, E) là đồ thị có hướng như ở Hình 1.7. Khi đó: 1. v1 e1 v2 e9 v6 e6 v5 e7 v2 e2 v3 là một hành trình có hướng với đỉnh đầu là v1 , đỉnh cuối là v3 và độ dài bằng 5. 2. v1 e1 v2 e7 v5 e4 v4 e3 v3 e2 v2 e7 v5 e6 v6 là một hành trình vô hướng với đỉnh đầu là v1 , đỉnh cuối là v6 và độ dài bằng 7. 3. v2 e9 v6 e6 v5 e7 v2 là một hành trình có hướng khép kín. 4. v2 e7 v5 e5 v4 e3 v3 e2 v2 là một hành trình vô hướng khép kín. Trong trường hợp hành trình có hướng, mỗi cung ei đều có đỉnh đầu là đỉnh đứng trước và đỉnh cuối là đỉnh đứng sau ei trong dãy, tức là nó 17