Luận văn Thạc sĩ Toán học: Một số bài toán đếm trong lý thuyết đồ thị

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:45

Thêm vào BST

Báo xấu

30
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn tìm hiểu về số cây trên tập đỉnh cho trước, số cây có n đỉnh cho trước, với n là một số nguyên dương. Luận văn cũng tìm hiểu cách tính số cây khung bằng ma trận Laplacian. Việc đánh giá số đỉnh, số cạnh của đồ thị phẳng cũng được xem là bài toán đếm. Cuối cùng luận văn trình bày một số đánh giá về việc đếm số tam giác trong đồ thị, bài toán này cũng thường xuất hiện trong các đề thi học sinh giỏi. Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Một số bài toán đếm trong lý thuyết đồ thị

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NINH THỊ NỤ MỘT SỐ BÀI TOÁN ĐẾM TRONG LÝ THUYẾT ĐỒ THỊ LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2019
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NINH THỊ NỤ MỘT SỐ BÀI TOÁN ĐẾM TRONG LÝ THUYẾT ĐỒ THỊ Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 8 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 - 2019
Mục lục Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Chương 1. Mở đầu đại số tổ hợp và lý thuyết đồ thị . . . . . . . . . 3 1.1. Đại số tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2. Công thức đa thức . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3. Mở đầu lý thuyết đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Chương 2. Bài toán đếm trên đồ thị . . . . . . . . . . . . . . . . . . . . . . . . 23 2.1. Cây và các bài toán đếm cây . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2. Công thức tính số cây khung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.3. Đánh giá số cạnh của một đồ thị phẳng. . . . . . . . . . . . . . . . . . . . . . . . . 34 2.4. Số tam giác trong đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 i
Mở đầu Cùng với sự phát triển với tốc độ nhanh của công nghệ thông tin, lý thuyết tổ hợp và đồ thị đã trờ thành các lĩnh vực toán học quan trọng và cần thiết cho nhiều lĩnh vực khoa học và ứng dụng. Lý thuyết tổ hợp là chiếc cầu nối giữa các bài toán cần được giải quyết với công cụ tính toán, còn đồ thị là mô hình trực quan để mô tả các quan hệ hai ngôi. Trong những thập kỷ gần đâỵ, người ta đã quan tâm nhiều tới đồ thị và các ứng dụng của nó. Đó là do đồ thị đã chứng tỏ được là một mô hình hữu hiệu cho tính toán và tối ưu. Ngày nay khái niệm đồ 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ó nhiều bài toán toán về lý thuyết đồ thị cần được tìm hiểu như bài toán tối ưu trên đồ thị, bài toán tô màu đồ thị, cấu trúc đồ thị, ... Các bài toán về đồ thị cũng thường xuất hiện trong các đề thi học sinh giỏi các cấp. Luận văn tìm hiểu về một số bài toán đếm trên lý thuyết đồ thị như bài toán đếm cây; tính số cây khung; tìm mối liên hệ giữa một số yếu tố trong đồ thị như cạnh, đỉnh; đếm số tam giác trên đồ thị. Luận văn được chia làm hai chương. Chương 1 trình bày một số kiến thức chuẩn bị về đại số tổ hợp, công thức đa thức và mở đầu về lý thuyết đồ thị. Tuy là kiến thức chuẩn bị cho Chương 2 nhưng đối với tác giả nhiều kiến thức của chương là kiến thức mới và có nhiều ứng dụng trong giải toán phổ thông. Chương này chủ yếu tham khảo theo các tài liệu [1, 2, 4]. Chương 2 trình bày về một số bài toán đếm cơ bản trong lý thuyết đồ thị. Bắt đầu là bài toán đếm về cây. Việc đếm số đỉnh, số cảnh của cây cũng cho ta một số đặc trưng của cây (Định lý móc xích kiểu hoa cúc). Tiếp theo luận văn tìm hiểu về số cây trên tập đỉnh cho trước, số cây có n đỉnh cho trước, với n là 1
một số nguyên dương. Luận văn cũng tìm hiểu cách tính số cây khung bằng ma trận Laplacian. Việc đánh giá số đỉnh, số cạnh của đồ thị phẳng cũng được xem là bài toán đếm. Cuối cùng luận văn trình bày một số đánh giá về việc đếm số tam giác trong đồ thị, bài toán này cũng thường xuất hiện trong các đề thi học sinh giỏi. Chương 2 tham khảo chính theo các tài liệu [4, 6, 7, 8, 9]]. Trong quá trình làm luận văn, tôi nhận được sự hướng dẫn và giúp đỡ tận tình của TS. Trần Nguyên An - Trường Đại học Sư phạm - Đại học Thái Nguyên. Tôi xin được bày tỏ lòng biết ơn sâu sắc đến thầy. Tôi 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 khóa Cao học Toán khóa 11E (2017-2019) - trường Đại học Khoa học - Đại học Thái Nguyên, đã truyền thụ đến cho tôi nhiều kiến thức và kinh nghiệm nghiên cứu khoa học. Lời cuối cùng, tác giả muốn dành để tri ân bố mẹ và gia đình vì đã chia sẻ những khó khăn để tác giả hoàn thành công việc học tập của mình. Thái Nguyên, ngày 30 tháng 01 năm 2019 Tác giả Ninh Thị Nụ 2
Chương 1 Mở đầu đại số tổ hợp và lý thuyết đồ thị 1.1. Đại số tổ hợp Mục này nhắc lại một số kiến thức chuẩn bị về Đại số tổ hợp như các quy tắc đếm cơ bản, các công thức tổ hợp. Tài liệu tham khảo chính của mục 1.1 và 1.2 là 1. Trần Nguyên An và Nguyễn Văn Hoàng (2016), Tập hợp và logic Toán, NXB Đại học Thái Nguyên. 2. Ngô Đắc Tân (2003), Lý thuyết tổ hợp và đồ thị, NXB Đại học Quốc gia Hà Nội. Người ta thường phân biệt nhiều mức độ trong việc giải các bài toán tổ hợp. Mức độ đầu tiên là tìm ít nhất một cách bố trí những đối tượng có tính chất đã cho. Nếu bài toán tổ hợp có nhiều lời giải thì vẫn đề đặt ra là đếm số lời giải, và mô tả tất cả các lời giải của các bài toán đã cho. Cuối cùng, nếu các lời giải khác nhau được phân biệt với nhau bởi những tham số nào đó, thì vấn đề đặt ra là tìm lời giải tối ưu của bài toán đã cho. Ở đây chúng ta sẽ chỉ giới hạn vào việc đếm số lời giải của bài toán tổ hợp. Để làm việc này, người ta thường áp dụng những công thức thiết lập cho từng loại bài toán. Tất cả các công thức ấy, xét cho cùng, đều dựa trên hai quy tắc đơn giản là quy tắc cộng và quy tắc nhân. Định nghĩa 1.1.1 (Quy tắc cộng). Nếu một công việc nào đó có thể thực hiện theo n phương án khác nhau, trong đó: phương án 1 có m1 cách thực hiện, phương án 2 có m2 cách thực hiện, ..., phương án thứ n có mn cách thực hiện. Khi đó, có: m1 + m2 + ... + mn cách để hoàn thành công việc đã 3
cho. Ta phát biểu quy tắc cộng theo ngôn ngữ tập hợp: Gọi A1 là tập hợp các đối tượng x1 , A2 là tập hợp các đối tượng x2 , ..., An là tập hợp các đối tượng xn . Mỗi cách chọn đối tượng xi ứng với một phần tử của Ai và đảo lại. Điều kiện "cách chọn đối tượng xi không trùng với bất kỳ đối tượng xj , (j 6= i)" được diễn tả theo ngôn ngữ tập hợp bằng điều kiện: Ai ∩ Aj = ∅, (i 6= j); i, j = 1, 2, ..., n. Cách chọn "x1 hoặc x2 ... hoặc xn" được phiên dịch thành cách chọn một phần tử của tập hợp A1 ∪ A2 ∪ ... ∪ An . Các số m1 , m2, ..., mn theo thứ tự là số phần tử của tập hợp A1, A2, ..., An, tức là, theo cách ký hiệu quen thuộc m1 = |A1 |, m2 = |A2 |, ..., mn = |An |. Mệnh đề 1.1.2. Nếu A1 , ..., Am là các tập hợp hữu hạn đôi một rời nhau, khi đó: |A1 ∪ ... ∪ Am | = |A1 | + ... + |Am−1| + |Am |. Quy tắc cộng có thể mở rộng cho công thức |A1 ∪ A2 ∪ ... ∪ An |, trong đó A1 ,..., An là các tập hợp hữu hạn tùy ý (không nhất thiết đôi một rời nhau). Công thức này được gọi là Nguyên lý bao hàm và loại trừ. Định lý 1.1.3 (Nguyên lý bao hàm và loại trừ). Giả sử A1 , A2, ...An. Là các tập hữu hạn bất kỳ. Khi đó: X X |A1 ∪ A2 ∪ ... ∪ An | = |Ai1 | − |Ai1 ∩ Ai2 | + ... 1≤i1≤n 1≤i ≤i2 ≤n X1 k+1 + (−1) |Ai1 ∩ Ai2 ∩ ... ∩ Aik | + ... 1≤i1 ≤i2 ≤...ik ≤n n+1 + (−1) |Ai1 ∩ Ai2 ∩ ... ∩ Ain |. Định nghĩa 1.1.4 (Quy tắc nhân). Nếu một công việc nào đó phải hoàn thành qua m giai đoạn liên tiếp, trong đó: giai đoạn 1 có m1 cách thực hiện, giai đoạn 2 có m2 cách thực hiện, ..., giai đoạn n có mn cách thực hiện. Khi đó, có: m1 .m2 ...mn cách để hoàn thành công việc đã cho. Mệnh đề 1.1.5. Cho s tập hợp hữu hạn A1 , A2 , ..., An (n ≥ 2). Khi đó |A1 × A2 × ... × An | = |A1 |.|A2|...|An|. Định nghĩa 1.1.6. Cho X là một tập hợp có n phần tử và k > 0 là một số tự nhiên. Một chỉnh hợp có lặp chập k của n phần tử là một bộ sắp thứ tự 4
k gồm k phần tử của X . Ta kí hiệu An là số chỉnh hợp có lặp chập k của n phần tử. Ví dụ 1.1.7. Cho X = {a, b, c}. Khi đó (a, a, b, c) là một chỉnh hợp có lặp chập 4 của 3 phần tử. Những bộ (b, a, a), (a, b, c) là những chỉnh hợp có lặp chập 3 của 3 phần tử. Tất cả các chỉnh hợp có lặp chập 2 của 3 phần tử là (a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c). 2 Do đó A3 = 9. Mệnh đề 1.1.8. Chỉnh hợp có lặp chập k của n phần tử được cho bởi công thức k An = nk . Định nghĩa 1.1.9. Cho X là một tập hợp có n phần tử và 0 < k ≤ n là một số tự nhiên. Một chỉnh hợp không lặp chập k của n phần tử là một bộ sắp thứ tự gồm k phần tử phân biệt của X. Ta kí hiệu Akn là số chỉnh hợp không lặp chập k của n phần tử. Ví dụ 1.1.10. Cho X = {a, b, c}. Khi đó (a, b, c) là một chỉnh hợp không lặp chập 3 của 3 phần tử; (b, a, a) không là chỉnh hợp không lặp chập 3 của 3 phần tử. Các chỉnh hợp không lặp chập 2 của 3 phần tử là (a, b), (a, c), (b, a), (b, c), (c, a), (c, b). Do đó A23 = 6. Mệnh đề 1.1.11. Số các chỉnh hợp không lặp chập k của n phần tử được cho bởi công thức n! Akn = , (n − k)! trong đó ta quy ước 0! = 1. Cho thuận tiện, ta quy ước rằng có đúng một chỉnh hợp không lặp chập 0 của n phần tử. Định nghĩa 1.1.12. Cho X là một tập hợp có n phần tử. Một hoán vị của n phần tử là một bộ sắp thứ tự gồm n phần tử phân biệt của X. Ta kí hiệu Pn là số hoán vị của n phần tử. Ví dụ 1.1.13. Cho X = {a, b, c}. Khi đó các hoán vị của 3 phần tử là (a, b, c), (b, c, a), (c, a, b), (a, c, b), (c, b, a)(b, a, c). 5
Do đó P3 = 6. Mệnh đề 1.1.14. Số các hoán vị của n phần tử được cho bởi công thức Pn = n!. Định nghĩa 1.1.15. Cho n, k là các số tự nhiên sao cho 0 ≤ k ≤ n. Cho X là một tập gồm n phần tử. Một tổ hợp chập k của n phần tử là một tập con của X gồm k phần tử. Ta kí hiệu Cnk là số tổ hợp chập k của n phần tử. Ví dụ 1.1.16. Cho k = 2 và n = 4. Cho X = {a, b, c, d}. Khi đó các tổ hợp chập 2 của 4 phần tử trong tập X là {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}. Do đó C42 = 6. Mệnh đề 1.1.17. Công thức tính số các tổ hợp chập k của n phần tử được cho bởi công thức n! Cnk = , k!(n − k)! trong đó ta quy ước 0! = 1. Mệnh đề 1.1.18. Cho k, n là các số tự nhiên sao cho 0 ≤ k ≤ n. Khi đó ta có (i) Cnk = Cnn−k . (ii) Cnk = Cn−1 k−1 k + Cn−1 . (iii) Với n và k là các số nguyên dương ta có Cnk = Cn−1 k−1 k−1 + Cn−2 k−1 + . . . + Ck+1 + Ckk−1 + Ck−1 k−1 . Mệnh đề 1.1.19. Cho số tự nhiên n > 1 và cho a, b là hai số thực. Khi đó ta có (a + b)n = Cn0an + Cn1an−1b + Cn2an−2 b2 + . . . + Cnn−1abn−1 + Cnnbn . Hệ quả 1.1.20. Với mỗi số tự nhiên n ta có (i) Cn0 + Cn1 + . . . + Cnn = 2n. Do đó, có 2n các tập con của một tập gồm n phần tử. (ii) Cn0 − Cn1 + Cn2 + . . . + (−1)k Cnk + . . . + (−1)nCnn = 0. 6
(iii) Cn1 − 2Cn2 + 3Cn3 − 4Cn4 + . . . + (−1)k−1kCnk + . . . + (−1)n−1nCnn = 0 với mọi n ≥ 2. (iv) Cn1 + 2Cn2 + . . . + kCnk + . . . + nCnn = n2n−1 với mọi n ≥ 1. Kết quả sau đây cho ta cách đếm số phân hoạch một tập hợp có m phần tử cho trước thỏa mãn một số yêu cầu. Định lý 1.1.21. Cho các số tự nhiên k1 , k2 , . . . , ks sao cho k1 + k2 + . . . + ks = m. Khi đó số phân hoạch một tập hợp A gồm m phần tử khác nhau thành hợp rời rạc của s tập con B1 , B2 , . . . , Bs, với số phần tử theo thứ tự là k1, k2, . . . , ks, bằng m! . k1 !.k2! . . . ks ! Chứng minh. Ta có thể thực hiện các phân hoạch đã mô tả trên đây của tập A thành s tập con B1 , B2, . . . , Bs như sau: Ta lấy một tập con B1 bất kỳ chứa k1 phần tử của tập hợp A (điều này có thể thực hiện theo Cm k1 cách), trong m − k1 phần tử còn lại, ta lấy một tập con B2 chứa k2 phần tử (điều k2 này có thể thực hiện theo Cm−k1 cách). . . . Khi đó, theo quy tắc nhân, số tất cả các cách chọn các tập con B1 , B2 , . . . , Bs là k1 k2 k3 ks Cm ×Cm−k 1 × Cm−k 1 −k2 . . . × Cm−k1 −k2 −...−ks−1 m! (m − k1 )! (m − k1 − k2 )! = × × k1!(m − k1)! k2 !(m − k1 − k2 )! k3!(m − k1 − k2 − k3 )! (m − k1 − k2 − . . . − ks )! ×...× ks !(m − k1 − k2 − . . . − ks )! m! = . k1!.k2! . . . ks ! Định nghĩa 1.1.22. Cho s phần tử khác nhau a1 , a2 , . . . , as . Một chỉnh hợp có lặp chập m của s phần tử đã cho, trong đó có k1 phần tử thứ nhất a1 , có k2 phần tử thứ hai a2 , . . ., và có ks phần tử as (với m = k1 + k2 + . . . + ks ), được gọi là một hoán vị có lặp cấp m = k1 + k2 + . . . + ks kiểu (k1 , k2 , . . . , ks ) của s phần tử. Số các hoán vị có lặp cấp m kiểu (k1 , k2 , . . . , ks) của s phần tử được kí hiệu là Cm (k1, k2, . . . , ks). 7
Định lý sau đây cho ta công thức tính số các hoán vị có lặp. Định lý 1.1.23. Số hoán vị có lặp cấp m = k1 + . . . + ks kiểu (k1 , k2 , . . . , ks ) của s phần tử, được xác định bằng công thức m! Cm(k1, k2, . . . , ks ) = . k1 !.k2! . . . ks ! Chứng minh định lý 1.1.23 cách 1. Gọi s phần tử phân biệt đã cho là a1 , a2 , . . . , as . Ta đặt O = {O1 , O2 , . . . , Om } là tập gồm m ô chứa đánh số từ 1 đến m. Lấy T là một hoán vị có lặp chập m kiểu (k1, k2, . . . , ks ) của s phần tử đã cho. Nếu ta đưa T vào dãy các ô chứa từ O1 đến Om (theo đúng thứ tự từ trái sang phải), khi đó mỗi Oi sẽ chứa một phần tử aj nào đó trong số s phần tử đã cho. Ta kí hiệu B1 = {Oi ∈ O | Oi chứa phần tử a1 }, B2 = {Oi ∈ O | Oi chứa phần tử a2 }, ..., Bs = {Oi ∈ O | Oi chứa phần tử as }. Khi đó B1 có k1 phần tử, B2 có k2 phần tử a2 ,. . . , Bs chứa ks phần tử; đồng thời O = B1 ∪ B2 ∪ . . . ∪ Bs . Như vậy ta thấy rằng mỗi hoán vị T hoàn toàn được xác định khi biết các tập B1 , B2 , . . . , Bs. Nói cách khác số các hoán vị có lặp cấp m kiểu (k1, k2, . . . , ks ) của s phần tử đã cho bằng số các phân hoạch tập O thành s tập con rời nhau B1 , B2 , . . . , Bs sao cho |B1 | = k1 , |B2 | = k2 , . . . , |Bs | = ks . Từ đó theo định lý 1.1.21 ta được m! Cm(k1, k2, . . . , ks ) = . k1 !.k2! . . . ks ! Dưới đây là một cách chứng minh khác của định lý 1.1.23. Chứng minh định lý 1.1.23 cách 2. Giả sử có tập hợp X gồm s phần tử là X = {a1 , a2, . . . , as }. 8
Ta lấy tùy ý một hoán vị T có lặp cấp m, kiểu (k1 , . . . , ks) của s phần tử đã cho (chẳng hạn để tiện cho minh họa ta lấy T = (a1, . . . , a1 , a2, . . . , a2 , . . . , as , . . . , as ) | {z } | {z } | {z } k1 k2 ks là một hoán vị có các phần tử giống nhau sẽ đứng cạnh nhau; còn nói chung các hoán vị có lặp T1 khác thì các phần tử giống nhau có thể không đứng cạnh nhau). Tiếp theo, nếu ta thay thế tất cả các phần tử giống nhau trong T bởi những phần tử khác nhau sao cho ta được tất cả các phần tử đều khác nhau, thì ta được một hoán vị T ′ gồm m phần tử khác nhau (chẳng hạn với T như minh họa ở trên ta được T ′ = (u11, . . . , u1k1 , u21, . . . , u2k2 , . . . , us1, . . . , usks ) | {z } | {z } | {z } k1 k2 ks thực sự là một hoán vị thông thường của m phần tử khác nhau {u11 , . . . , u1k1 , u21, . . . , u2k2 , . . . , us1, . . . , usks }; còn đối với hoán vị T1 như trên thì nó sinh ra hoán vị T1′ sẽ là một hoán vị nào đó của T ′ như trên). Khi đó các số hoán vị khác nhau sinh ra từ T ′ là k1 !k2 ! . . . ks! (ta thấy điều này bằng cách sử dụng quy tắc nhân). Ta sẽ làm như vậy cho bất kì hoán vị T có lặp cấp m, kiểu (k1 , . . . , ks), từ đó ta sẽ tìm được tất cả m! hoán vị của m phần tử khác nhau {u11, . . . , u1k1 , u21, . . . , u2k2 , . . . , us1, . . . , usks }. Do đó ta có đẳng thức Cm (k1, k2, . . . , ks).k1!k2! . . . ks ! = m!. Từ đó suy ra m! Cm(k1, k2, . . . , ks ) = . (1.1) k1 !.k2! . . . ks ! Nhận xét 1.1.24. (i) Số Cm(k1 , k2 , . . . , ks ) ở Định lý 1.1.23 được gọi là các hệ số đa thức (vì ta sẽ thấy ở đó là các hệ số trong sự khai triển của đa thức (a1 + a2 + . . . + as )m khi coi các ẩn là a1 , a2 , . . . , as ). 9
(ii) Theo công thức (1.1), số hoán vị có lặp cấp m, kiểu (k, m − k), của 2 phần tử đã cho bằng m! . k!(m − k)! Số này chính là Cm k . Vậy số hoán vị có lặp của hai phần tử cấp m, kiểu (k, m − k) bằng số tổ hợp chập k của m phần tử k Cm (k, m − k) = Cm . Ta có thể chứng minh đẳng thức này mà không dựa vào công thức (1.1). Thật vậy, một hoán vị có lặp của hai phần tử a và b cấp m, kiểu (k, m − k) được tạo thành bởi k phần tử a và m − k phần tử b. Nó được hoàn toàn xác định bởi cách chọn vị trí của phần tử a. Vì tổng số vị trí bằng k + (m − k) = m, và phần tử a chiếm k vị trí, nên có thể chọn các vị trí đó theo Cm k cách. Định nghĩa 1.1.25. Cho X là tập có m phần tử khác nhau, và n là số tự nhiên (không nhất thiết yêu cầu n ≤ m). Khi đó một tổ hợp có lặp chập n của m phần tử đã cho là một bộ gồm n phần tử (không nhất thiết phân biệt, không phân biệt thứ tự) lấy từ tập X . Ví dụ 1.1.26. i) Cho hai phần tử khác nhau a và b. Các tổ hợp có lặp chập 3 của hai phần tử đã cho là aaa, aab, abb, bbb. ii) Các tổ hợp có lặp chập 2 của 3 phần tử khác nhau a, b, c là aa, ab, ac, bb, bc, cc. Định lý 1.1.27. Số tổ hợp có lặp chập n của m phần tử, kí hiệu là Cm n , nó được xác định bằng công thức n = Cn Cm m−1 n+m−1 = Cn+m−1. Chứng minh. Giả sử m phần tử đã cho được kí hiệu là a1 , . . . , am . Lấy T là một tổ hợp có lặp chập n của m phần tử đã cho. Ta thấy rằng T sẽ được hoàn toàn xác định khi biết có k1 phần tử a1 trong T , có k2 phần tử a2 trong T , . . . , có km phần tử am trong T (trong đó k1 + k2 + . . . + km = n, và 0 ≤ k1 , . . . , km ≤ n). Một tổ hợp T như vậy ta sẽ gọi tắt là một tổ hợp có lặp chập n kiểu (k1 , . . . , km) của m phần tử. 10
Ta sẽ thiết lập một tương ứng giữa các tổ hợp có lặp chập n của m phần tử với tập các dãy gồm các chữ số 1 và 0 như sau: Xét một tổ hợp T có lặp chập n kiểu (k1 , . . . , km ) của m phần tử. Ta cho ứng T với dãy sau đây: k lần k lần k lần z 1}| { z 2}| { z m}| { 11 . . . 1 0 11 . . . 1 0 . . . 0 11 . . . 1 Nếu một phần tử ai nào đó không có mặt trong tổ hợp, tức là ki = 0, thì ta không viết nhóm chữ số 1 tương ứng (thí dụ: nếu ta xét các tổ hợp có lặp chập 2 của 3 chữ số a, b, c là: aa, ab, ac, bb, bc, cc với các kiểu theo thứ tự là (2, 0, 0), (1, 1, 0), (1, 0, 1), (0, 2, 0), (0, 1, 1), (0, 0, 2), thì ta được các dãy tương ứng của chúng là (2,0,0) (1,1,0) (1,0,1) (0,2,0) (0,1,1) (0,0,2) l l l l l l 1100 1010 1001 0110 0101 0011 rõ ràng ở thí dụ này trong tất cả các dãy trên thì số các số 1 có mặt trong dãy là 2, và số các số 0 có mặt là 1). Như vậy, tổng quát, ta thấy rằng số chữ số 1 tham gia vào dãy ứng với tổ hợp T kiểu (k1 , k2 , . . . , km) bằng n = k1 + k2 + . . . + km , còn số chữ số 0 tham gia vào dãy đó thì bằng m − 1 (chữ số 0 đóng vai trò phân tách m nhóm ra nên sẽ cần m − 1 số 0). Ta nhận thấy rằng mỗi dãy nói trên đúng là một chỉnh hợp có lặp chập n + m − 1 của hai số 1 và 0, trong đó có n số 1 và m − 1 số 0 (nói cách khác đó là một hoán vị có lặp cấp n + m − 1 kiểu (n, m − 1) của hai chữ số 1 và 0). Đảo lại, ứng với mỗi chỉnh hợp có lặp chập n + m − 1 hai chữ số 0 và 1, trong đó có n chữ số 1 và m − 1 chữ số 0 (hay mỗi hoán vị có lặp cấp n + m − 1, kiểu (n, m − 1), của hai chữ số 1 và 0), ta có một tổ hợp có lặp chập n kiểu (k1 , . . . , km) của m phần tử, mà ta có thể viết ra một cách dễ dàng 11
(thí dụ: Ứng với chỉnh hợp có lặp chập 12 của hai chữ 0 và 1 (gồm 9 số 1 và 3 số 0) là 011100111111; ta có thể thiết lập lại tổ hợp có lặp chập 9 kiểu (0,3,0,6) của 4 phần tử a, b, c, d là bbbdddddd). Như vậy số tổ hợp có lặp chập n của m phần tử bằng số chỉnh hợp có lặp chập n + m − 1 của hai chữ số 0 và 1 (trong đó có n chữ số 1 và m − 1 chữ số 0), tức là bằng số các hoán vị có lặp cấp n + m − 1, kiểu (n, m − 1), của hai chữ số 1 và 0). Kí hiệu số tổ hợp có lặp chập n của m phần tử là n , khi đó theo Định lý 1.1.23 ta có Cm n =C n Cm n+m−1(n, m − 1) = Cn+m−1 . 1.2. Công thức đa thức "Công thức nhị thức Newton" là sự khai triển của biểu thức (a + b)n trong đó a, b ∈ R và n ∈ N∗ . "Công thức đa thức" là sự khai triển của biểu thức (a1 + a2 + . . . + am )n trong đó a1 , a2 , . . . , am ∈ R và n ∈ N∗ . Để chứng minh công thức đa thức, trước hết ta chứng minh lại công thức nhị thức Newton, theo một cách khác so với cách đã trình bày ở trên. Cách này dễ dàng mở rộng ra cho trường hợp tổng quát. Theo định nghĩa, ta có (a + b)n = (a + b)(a + b) . . . (a + b) . | {z } n lần Ta khai triển vế phải dựa vào tính chất phân phối của phép nhân với phép cộng, và viết các số hạng của sự khai triển đó theo đúng thứ tự xuất hiện của chúng. Ví dụ 1.2.1. Ta xét các khai triển (a+b)2 = (a+b)(a+b) = aa+ba+ab+bb. (a+b)3 = (a+b)(a+b)(a+b) = aaa+aab+aba+abb+baa+bab+bba+bbb. Rõ ràng các số hạng ở vế phải là tích các phần tử của tất cả các chỉnh hợp có lặp chập n của hai chữ a và b. Các số hạng đồng dạng là tất cả các hoán vị có lặp của a và b có cấp n và kiểu (n1 , n2 ), với n1 + n2 = n. Số tất cả các hoán vị có lặp đó là Cn (n1 , n2 ). Sau khi rút gọn các số hạng đồng dạng 12
có kiểu (n1 , n2 ), ta tìm được số hạng tương ứng của sự khai triển là Cn (n1, n2)an1 bn2 . Làm như vậy đối với tất cả các kiểu (n1 , n2 ) khác nhau, cuối cùng ta tìm được sự khai triển của nhị thức Newton dưới dạng X (a + b)n = Cn (n1, n2)an1 bn2 (1.2) trong đó phép cộng trải trên tất cả các kiểu (n1 , n2 ) với n1 + n2 = n và n1, n2 ∈ N. Để chuyển từ đẳng thức 1.2 sang công thức quen thuộc, chỉ cần chú ý n! rằng Cn (n1 , n2 ) = = Cnn1 = Cnn2 . Đặt n2 = k , ta có Cnn2 = Cnk . Vậy n1!n2! n X n (a + b) = Cnk an−k bk . k=0 Định lý 1.2.2. Sự khai triển của (a1 + a2 + . . . + am )n được cho bởi công thức sau đây, gọi là công thức đa thức X (a1 + . . . + am )n = Cn (n1, . . . , nm ) an1 1 . . . anmm Pm n1 ,...,nm ∈N, i=1 ni =n X n! = an1 1 . . . anmm . (1.3) Pm n1 ! . . . nm ! n1 ,...,nm ∈N, i=1 ni =n Chứng minh. Xuất phát từ định nghĩa (a1 + . . . + am )n = (a1 + . . . + am )(a1 + . . . + am ) . . . (a1 + . . . + am ) (n lần), ta mở các dấu ngoặc và viết các số hạng theo thứ tự xuất hiện của chúng, ta sẽ được mn số hạng có dạng d1 d2 . . . dn , mỗi số hạng là một chỉnh hợp có lặp chập n của m chữ a1 , a2 , . . . , am . Các số hạng đồng dạng là tất cả các hoán vị có cùng một kiểu (n1 , n2 , . . . , nm). Có Cn (n1 , n2 , . . . , nm) hoán vị như thế. Rút gọn các số hạng đồng dạng đó, ta tìm được số hạng tương ứng của sự khai triển là n! Cn (n1, n2, . . . , nm) an1 1 an2 2 . . . anmm = an1 1 an2 2 . . . anmm . n1 !n2! . . . nm! Làm như vậy đối với tất cả các kiểu (n1 , n2 , . . . , nm) sao cho n1 + n2 + . . . + nm = n, cuối cùng ta tìm được sự khai triển của (a1 + a2 + . . . + am )n dưới 13
dạng: X n! (a1 + a2 + . . . + am )n = an1 1 an2 2 . . . anmm . Pm n1 !n2! . . . nm ! n1 ≥0,...,nm ≥0 i=1 ni =n 1.3. Mở đầu lý thuyết đồ thị Mục này trình bày một số kiến thức chuẩn bị về đồ thị: đồ thị vô hướng, đồ thị có hướng, một số dạng đồ thị đặc biệt, bậc của đỉnh, Bổ đề bắt tay, ... Tài liệu tham khảo chính của mục này là Ngô Đắc Tân (2003), Lý thuyết tổ hợp và đồ thị, NXB Đại học Quốc gia Hà Nội. Định nghĩa 1.3.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 , tức là E là một quan hệ hai ngôi trên 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ì dượ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 f e b d c Hình 1.1: Ví dụ một đồ thị có hướng Ví dụ 1.3.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. 14
Định nghĩa 1.3.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à 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 định nghĩa khái niệm đồ thị vô hướng ta nhắc lại khái niệm đa tập. Một đa tập hợp, gọi tắt là đa tập là tập các vật, trong đó có thể có những vật không phân biệt được với nhau (và có thể coi như sự lặp lại của cùng một vật). Ví dụ A = {a, b, b, c, c} là một đa tập lực lượng 6. Định nghĩa 1.3.4 (Đồ 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 đinh đầ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 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 đó. Ví dụ 1.3.5. 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ị 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 15
a d b c Hình 1.2: Ví dụ một đồ thị vô hướng 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 ′ = {xy} ) 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 6= 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 n thì cỡ m của nó thỏa mãn 0 ≤ m ≤ n2 . Đồ 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. 16
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 6= ∅, 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 6= 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 6= 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.3.6. Ta định nghĩa bậc của đỉnh v trong đồ thị G, ký hiệu là degG (v) hay ngắn gọn là deg(v) nếu như G được hiểu ngầm, như sau: ( |N (v)|, nếu {v, v} ∈ /E deg(v) = (1.4) |N (v)| + 2, nếu {v, v} ∈ E . 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 17