NINH THỊ NỤ
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC
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
NINH THỊ NỤ
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC
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
i
Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
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
1
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. 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ả
2
Ninh Thị Nụ
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
1.1 và 1.2 là
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. 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
3
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 đã
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|.
|A1 ∪ ... ∪ Am| = |A1| + ... + |Am−1| + |Am|.
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 đó:
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ừ.
|A1 ∪ A2 ∪ ... ∪ An| =
|Ai1| −
|Ai1 ∩ Ai2| + ...
Đị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 đó:
|Ai1 ∩ Ai2 ∩ ... ∩ Aik| + ...
1≤i1≤i2≤...ik≤n X + (−1)n+1|Ai1 ∩ Ai2 ∩ ... ∩ Ain|.
X1≤i1≤i2≤n X1≤i1≤n + (−1)k+1
Đị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.
|A1 × A2 × ... × An| = |A1|.|A2|...|An|.
Mệnh đề 1.1.5. Cho s tập hợp hữu hạn A1, A2, ..., An (n ≥ 2). Khi đó
Đị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ố
4
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ự
k gồm k phần tử của X. Ta kí hiệu A n 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
(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c).
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à
2 3 = 9.
Do đó A
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
k n = nk. A
thức
Đị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à
n là số chỉnh hợp
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 Ak
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
3 = 6.
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 đó A2
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
,
Ak
n =
n! (n − k)!
cho bởi công thức
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ử.
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ử.
Đị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
(a, b, c), (b, c, a), (c, a, b), (a, c, b), (c, b, a)(b, a, c).
5
Ví dụ 1.1.13. Cho X = {a, b, c}. Khi đó các hoán vị của 3 phần tử là
Do đó P3 = 6.
Pn = n!.
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
Định nghĩa 1.1.15. Cho n, k là các số tự nhiên sao cho 0 ≤ k ≤ n. Cho X
n là số tổ hợp chập k của n phần tử.
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 C k
Ví dụ 1.1.16. Cho k = 2 và n = 4. Cho X = {a, b, c, d}. Khi đó các tổ hợp
{a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}.
chập 2 của 4 phần tử trong tập X là
4 = 6.
Do đó C 2
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
,
C k
n =
n! k!(n − k)!
cho bởi công thức
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) C k
n−1.
n = C n−k n n = C k−1 n−1 + C k
(ii) C k
C k
n = C k−1
n−1 + C k−1
n−2 + . . . + C k−1
k+1 + C k−1
k + C k−1 k−1.
(iii) Với n và k là các số nguyên dương ta có
Mệnh đề 1.1.19. Cho số tự nhiên n > 1 và cho a, b là hai số thực. Khi đó
(a + b)n = C 0
nan + C 1
nan−1b + C 2
nan−2b2 + . . . + C n−1
n abn−1 + C n
n bn.
ta có
Hệ quả 1.1.20. Với mỗi số tự nhiên n ta có
n + C 1
n + . . . + C n
n = 2n. Do đó, có 2n các tập con của một tập gồm n
(i) C 0
phần tử.
n − C 1
n + C 2
n + . . . + (−1)kC k
n + . . . + (−1)nC n
n = 0.
6
(ii) C 0
n − 2C 2
n + 3C 3
n − 4C 4
n + . . . + (−1)k−1kC k
n + . . . + (−1)n−1nC n
n = 0 với
(iii) C 1
mọi n ≥ 2.
n + 2C 2
n + . . . + kC k
n + . . . + nC n
n = n2n−1 với mọi n ≥ 1.
(iv) C 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.
.
m! k1!.k2! . . . ks!
Đị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
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 C k1 m 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 này có thể thực hiện theo C k2 m−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à
C k1
m ×C k2
m−k1−k2 . . . × C ks
m−k1−k2−...−ks−1
=
×
×
m−k1 × C k3 m! k1!(m − k1)!
(m − k1 − k2)! k3!(m − k1 − k2 − k3)!
× . . . ×
.
=
(m − k1)! k2!(m − k1 − k2)! (m − k1 − k2 − . . . − ks)! ks!(m − k1 − k2 − . . . − ks)! 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
Cm(k1, k2, . . . , ks).
7
Đị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à
Định lý sau đây cho ta công thức tính số các hoán vị có lặp.
.
Cm(k1, k2, . . . , ks) =
m! k1!.k2! . . . ks!
Đị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
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}.
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
O = B1 ∪ B2 ∪ . . . ∪ Bs.
Khi đó B1 có k1 phần tử, B2 có k2 phần tử a2,. . . , Bs chứa ks phần tử; đồng thời
Như vậy ta thấy rằng mỗi hoán vị T hoàn toàn được xác định khi
.
Cm(k1, k2, . . . , ks) =
m! k1!.k2! . . . ks!
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
Dưới đây là một cách chứng minh khác của định lý 1.1.23.
X = {a1, a2, . . . , as}.
8
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à
)
, . . . , as, . . . , as
T = (a1, . . . , a1
, a2, . . . , a2 k2
k1
ks
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
| | {z {z } } } | {z 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
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
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
)
, u21, . . . , u2k2
T ′ = (u11, . . . , u1k1
, . . . , us1, . . . , usks
k1
k2
ks
(chẳng hạn với T như minh họa ở trên ta được
| | | {z {z } } }
1 sẽ là một hoán vị nào đó của T ′ như trên).
{z 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ị T ′
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ì
{u11, . . . , u1k1, u21, . . . , u2k2, . . . , us1, . . . , usks}.
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
Cm(k1, k2, . . . , ks).k1!k2! . . . ks! = m!.
Do đó ta có đẳng thức
Từ đó suy ra
.
Cm(k1, k2, . . . , ks) =
m! k1!.k2! . . . ks!
(1.1)
9
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).
(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
.
m! k!(m − k)!
phần tử đã cho bằng
m. 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ử
Cm(k, m − k) = C k m.
Số này chính là C k
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
m cách.
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 C k
Đị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
aaa, aab, abb, bbb.
3 của hai phần tử đã cho là
aa, ab, ac, bb, bc, cc.
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à
m, nó
Đị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à C n
C n
m = C n
n+m−1 = C m−1
n+m−1.
được xác định bằng công thức
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
10
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ử.
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ó
k1 lần 11 . . . 1 0
k2 lần 11 . . . 1 0 . . . 0
kmlần 11 . . . 1
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:
z }| { z }| { z }| {
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
aa, ab, ac, bb, bc, cc
(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à:
(2, 0, 0), (1, 1, 0), (1, 0, 1), (0, 2, 0), (0, 1, 1), (0, 0, 2),
với các kiểu theo thứ tự là
thì ta được các dãy tương ứng của chúng là
(2,0,0) l 1100 (1,1,0) l 1010 (1,0,1) l 1001 (0,2,0) l 0110 (0,1,1) l 0101 (0,0,2) l 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).
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
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
đó 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à
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
1, trong đó có n chữ số 1 và m − 1 chữ số 0 (hay mỗi hoán vị có lặp cấp
11
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
(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),
m, khi đó theo Định lý 1.1.23 ta có
C n
m = Cn+m−1(n, m − 1) = C n
n+m−1.
1.2. Công thức đa thức
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à C n
"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,
.
(a + b)n = (a + b)(a + b) . . . (a + b)
n lần
ta có
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 | } {z
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.
(a+b)3 = (a+b)(a+b)(a+b) = aaa+aab+aba+abb+baa+bab+bba+bbb.
Ví dụ 1.2.1. Ta xét các khai triển (a+b)2 = (a+b)(a+b) = aa+ba+ab+bb.
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
12
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
Cn(n1, n2)an1bn2.
có kiểu (n1, n2), ta tìm được số hạng tương ứng của sự khai triển là
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
(a + b)n =
Cn(n1, n2)an1bn2
(1.2)
X
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.
= C n1
Để chuyển từ đẳng thức 1.2 sang công thức quen thuộc, chỉ cần chú ý
n = C k
n. Vậy
n . Đặt n2 = k, ta có C n2
n = C n2
n! n1!n2!
n
C k
(a + b)n =
nan−kbk.
rằng Cn(n1, n2) =
(a1 + . . . + am)n =
Cn(n1, . . . , nm) an1
1 . . . anm m
m i=1 ni=n
Xk=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
P
Xn1,...,nm∈N,
=
an1 1 . . . anm m .
n! n1! . . . nm!
m i=1 ni=n
(1.3)
P
Xn1,...,nm∈N,
(a1 + . . . + am)n = (a1 + . . . + am)(a1 + . . . + am) . . . (a1 + . . . + am)
Chứng minh. Xuất phát từ định nghĩa
(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 d1d2 . . . 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
Cn(n1, n2, . . . , nm) an1
m =
2 . . . anm
1 an2
2 . . . anm m .
1 an2 an1
n! n1!n2! . . . nm!
ứng của sự khai triển là
13
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
(a1 + a2 + . . . + am)n =
2 . . . anm m .
1 an2 an1
n! n1!n2! . . . nm!
m i=1 ni=n
n1≥0,...,nm≥0 X
P
1.3. Mở đầu lý thuyết đồ thị
dạng:
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
a
f
e
b
c
d
Hình 1.1: Ví dụ một đồ thị có hướng
và có mũi tên hướng từ đỉnh đầu tới đỉnh cuối.
E = {(a, a), (a, b), (b, d), (d, b)(c, e), (e, a)}. Khi đó G là đồ thị có hướng
Ví dụ 1.3.2. Cho G = (V, E) với V = {a, b, c, d, e, f } và
14
được biểu diễn bằng Hình 1.1.
Đị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 đó.
E = {(a, a), (a, b), (b, d), (b, c)(c, d)}.
Ví dụ 1.3.5. Cho G = (V, E) với V = {a, b, c, d} và
Khi đó G là đồ thị vô hướng được biểu diễn bằng Hình 1.2.
15
Đồ 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
a
b
d
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 ],
(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ứ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
(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ị vô hướng cấp n và cỡ m = 0 thì cỡ m của nó thỏa mãn 0 ≤ m ≤
n 2 đượ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à (cid:1)
(cid:0)
n 2
On hay En. Còn đồ thị vô hướng không có khuyên cấp n và cỡ m = gọi là n-đồ thị đầy đủ và thường được ký hiệu là Kn.
được
16
(cid:0) (cid:1)
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
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ỳ
chú ý. Một đồ thị vô hướng không có khuyên G = (V, E) được gọi là đồ thị
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.
N +(v) = {x ∈ V |(v, x) ∈ E},
N −(v) = {y ∈ V |(y, v) ∈ E}.
Giả sử G = (V, E) là một đồ thị có hướng và v ∈ V . Ký hiệu
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.
NG(v) = {x ∈ V |x 6= v, và {x, v} ∈ E}
Bây giờ giả sử G = (V, E) là một đồ thị vô hướng và v ∈ V . Ký hiệu
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).
degG(v) hay ngắn gọn là deg(v) nếu như G được hiểu ngầm, như sau:
Định nghĩa 1.3.6. Ta định nghĩa bậc của đỉnh v trong đồ thị G, ký hiệu là
deg(v) =
|N (v)|, |N (v)| + 2, nếu {v, v} ∈ E .
nếu {v, v} /∈ E (1.4) (
deg(v),
δ(G) = min v∈V
deg(v),
∆(G) = max v∈V
Ta cũng kí hiệu
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.
17
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
G′ = (V ′, E′)
G = (V, E)
a
3
2
1
b
f
c
e
d
6
4
5
Hình 1.3: Ví dụ hai đồ thị vô hướng đẳng cấu
ứ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′.
ϕ(1) = a, ϕ(5) = b, ϕ(2) = c,
ϕ(6) = d, ϕ(3) = e, ϕ(4) = f
Ví dụ 1.3.7. Giả sử G = (V, E) và G′ = (V ′, E′) là các đồ thị vô hướng trong Hình 1.3. Khi đó G ∼= G′ và ánh xạ ϕ : V → V ′ với
là đẳng cấu của G và G’.
Định lý 1.3.8 (Bổ đề bắt tay). Trong đồ thị vô hướng G = (V, E) bất kỳ ta
deg(v) = 2 |E|.
luôn có
Xv∈V
Chứng minh. Mỗi x ∈ N (v) ta tương ứng với e = {v, x} ∈ E. Dễ thấy rằng
18
tương ứng này là song ánh giữa N (v) và E(v) = {{v, x} ∈ E|v 6= x}.
|N (v)| =
|Ev|.
Vì thế
Xv∈V Xv∈V Vì mỗi cạnh {v, x} ∈ E với v 6= 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 6= x đã được tính đúng
|E(v)| = 2|E1|,
hai lần: một lần trong Ev và một lần trong Ex. Do đó,
Xv∈V
|N (v)| = 2|E1|.
ở đây E1 là tập tất cả các cạnh không phải là khuyên của G. Do đó
Xv∈V
deg(v) =
deg(v) +
deg(v)
v∈V2 P
v∈V P =
v∈V1 P |N (v)| +
|N (v)| + 2 |V2|
v∈V2 P
=
|N (v)| + 2 |V2| = 2 |E1| + 2 |E2| = 2 |E| .
v∈V1 P v∈V P
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,
Định nghĩa 1.3.9. Giả sử G = (V, E) là một đồ thị có hướng. Một hành
trình có hướng trong G là một dãy v0e1v1e2v2.....envn 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 tự, một hành trình vô hướng
trong G là một dãy v0e1v1e2v2.....envn 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 nếu đỉnh
đầu và đỉnh cuối của nó trùng nhau.
Ví dụ 1.3.10. Giả sử G = (V, E) là đồ thị có hướng như ở Hình 1.4. Khi
19
đó:
e2
v3
v2
e1
e7
e3
e4
v5
e8
v4
e9
v1
e5
e6
v6
Hình 1.4: Dùng để minh hoạ cho hành trình trong đồ thị
v1, đỉnh cuối là v3 và độ dài bằng 5.
1. v1e1v2e9v2e9v6e6v5e7v2e2v3 là một hành trình có hướng với đỉnh đầu là
2. v1e1v2e7v5e4v4e3v3e2v2e7v5e6v6 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. v2e9v6e6v5e7v2 là một hành trình có hướng khép kín.
4. v2e7v5e5v4e3v3e2v2 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ó được xác định bởi chính hai đỉnh đó. Vì vậy người ta thường đơn giản gọi dãy
các đỉnh v0v1v1v2.....vn của G là hành trình có hướng trong G nếu với mọi i = 0, 1, ...., n − 1, (vi, vi+1) là một cung của G. Tình huống có hơi khác với trường hợp hành trình vô hướng. Nếu trong G giữa hai đỉnh vi và vj có cả hai cung là e1 = (vi, vj) và e2 = (vj, vi) thì hai dãy con vie1vj và vie2vj là hai đoạn khác nhau trong hành trình. Vì thế, cung giữa vi và vj cần được chỉ ra cụ thể. Tuy nhiên nếu trong G chỉ có một cung giữa vi và vj ( hoặc là (vi, vj) hoặc là (vj, vi) nhưng không đồng thời cả hai), thì cung giữa hai đỉnh đó cũng được xác định duy nhất trong G bởi vi và vj. Do đó để đơn giản ta cũng thay đoạn vie1vj với e1 = (vi, vj) hay vie2vj với e2 = (vj, vi) của hành trình bằng vi, vj.
Định nghĩa 1.3.11. Một hành trình có hướng (tương ứng, vô hướng), trong
đó các đỉnh đều khác nhau được gọi là một đường có hướng (tương ứng, vô
20
hướng). Một hành trình có hướng (tương ứng, vô hướng), trong đó các cung
đều khác nhau được gọi là một vết có hướng (tương ứng, vô hướng). Một
hành trình có hướng (tương ứng, vô hướng) khép kín, mà khi xóa đỉnh cuối
thì trở thành một đường có hướng (tương ứng, vô hướng), được gọi là một
chu trình có hướng (tương ứng, vô hướng). Một hành trình có hướng (tương
ứng, vô hướng) khép kín, trong đó các cung đều khác nhau, được gọi là một
mạch có hướng (tương ứng, vô hướng).
Trên đây ta đã đưa ra các định nghĩa của hành trình, đường, chu trình,
vết và mạch (có hướng, vô hướng) trong đồ thị có hướng. Các khái niệm tương
tự cũng có thể định nghĩa trong đồ thị vô hướng. Tuy nhiên, ta nhận xét
thấy rằng trong đồ thị vô hướng giữa hai đỉnh bất kỳ chỉ có nhiều nhất là
một cạnh. Vì thế, các khái niệm trên có thể định nghĩa trong đồ thị vô hướng
đơn giản như sau.
Định nghĩa 1.3.12. Giả sử G = (V, E) là một đồ thị vô hướng. Một hành
trình (vô hướng) trong G là một dãy các đỉnh v0v1v2...vn sao cho với mọi i = 0, 1, ..., n − 1, {vi, vi+1} là một cạnh của G. Các cạnh {vi, vi+1}, i = 0, 1, ..., n − 1, cũng được gọi là các cạnh của hành trình v0v1v2...vn. Khi đó n được gọi là độ dài, v0 được gọi là đỉnh đầu, còn vn được gọi là đỉnh cuối của hành trình trên. Một hành trình được gọi là khép kín nếu đỉnh đầu và đỉnh
cuối của nó trùng nhau. Một hành trình được gọi là đường nếu các đỉnh của
hành trình đó đều khác nhau. Một hành trình được gọi là vết nếu các cạnh
của hành trình đó đều khác nhau. Một hành trình khép kín được gọi là chu
trình, nếu nó có độ dài ít nhất là 3 và khi xóa đi đỉnh cuối thì trở thành
đường. Một hành trình khép kín được gọi là mạch nếu mọi cạnh của nó đều
khác nhau.
Ví dụ 1.3.13. Cho đồ thị G = (V, E) như Hình 1.5. Đồ thị này được gọi là
đồ thị Petersen. Khi đó,
1. abcde là một đường;
2. abcdea là một chu trình;
21
3. abcdeaa’c’e’e là một vết.
a
a’
b
b’
e’
e
c’
d’
c
d Hình 1.5: Đồ thị Petersen
Định nghĩa 1.3.14. Một đồ thị (có hướng, vô hướng) G = (V, E) được gọi
là liên thông yếu hay cũng gọi tắt là liên thông, nếu với hai đỉnh vi và vj khác nhau bất kỳ của G tồn tại một hành trình vô hướng trong G với đỉnh
G = (V, E)
b
G1
G2
h
f
c
a
g
i
e
d
Hình 1.6: Đồ thị G với hai thành phần liên thông là G1 và G2
đầu là vi và đỉnh cuối là vj. Trong trường hợp ngược lại, đồ thị được gọi là không liên thông.
Đồ thị con liên thông G′ = (V ′, E′) của một đồ thị (có hướng, vô
hướng) G = (V, E) được gọi là một thành phần liên thông của G, nếu G′ = G[V ′] và với mọi V ′′ ⊆ V , mà thực sự chứa V ′, đồ thị G[V ′′] là không
liên thông.
Ví dụ 1.3.15. Đồ thị có hướng G = (V, E) cho trong Hình 1.6 là đồ thị
22
không liên thông. Nó có hai thành phần liên thông là G1 và G2.
Chương 2
Bài toán đếm trên đồ thị
2.1. Cây và các bài toán đếm cây
Mục này chủ yếu theo các tài liệu [4, 6, 7, 8, 9]].
Các kết quả mục này được tham khảo trong cuốn Combinatorial problems
and exercises của Lovasz (Bài tập 1-6 trang 34). Một cách chứng minh khác
có thể xem thêm trong cuốn Introduction to enumerative combinatorics của
Bona (mục 5.1 và 5.3).
Định nghĩa 2.1.1. Một đồ thị vô hướng liên thông không có khuyên và
không có chu trình được gọi là cây.
Định nghĩa 2.1.2. Một đồ thị vô hướng không có khuyên (không nhất thiết
phải là liên thông) và không có chu trình được gọi là rừng.
Từ các định nghĩa trên dễ thấy rằng mỗi thành phần liên thông của
G = (V, E)
G4
G3
G2
G1
Hình 2.1: Ví dụ một rừng gồm 4 cây
23
rừng là cây.
Ví dụ 2.1.3. Đồ thị G = (V, E) trên Hình 2.1 là rừng gồm 4 cây là G1, G2, G3, G4.
Định nghĩa 2.1.4. Một đồ thị G = (V, E) được gọi là acyclic nếu không
tồn tại các dãy các đỉnh v0, v1, . . . , vn = v0 sao cho (vi, vi+1) ∈ E với i = 1, 2, . . . , n.
Nhận xét 2.1.5. Một đồ thị acyclic là một rừng.
Một đồ thị liên thông và acyclic là một cây.
Các đỉnh bậc 1 của cây được gọi là đỉnh lá hay đỉnh cuối, còn các đỉnh
bậc lớn hơn 1 của cây được gọi là đỉnh cành hay đỉnh trong.
Cấu trúc của cây được mô tả bởi định lý sau đây.
Định lý 2.1.6 (Định lý móc xích kiểu hoa cúc). Giả sử T = (V, E) là đồ
thị có hướng không có khuyên. Khi đó các khẳng định sau đây là tương đương
nhau:
(a) T là cây;
(b) T không chứa chu trình và |E| = |V | − 1;
(c) T liên thông và |E| = |V | − 1;
(d) T là đồ thị liên thông, nhưng nếu xóa đi một cạnh bất kỳ thì đồ thị
nhận được là không liên thông;
(e) Hai đỉnh khác nhau bất kỳ của T được nối với nhau bởi đúng một
đường;
(f) T không chứa chu trình, nhưng nếu ta thêm một cạnh nối hai đỉnh
không kề nhau trong T thì đồ thị nhận được có đúng một chu trình.
Chứng minh. 1. (a) ⇒ (b): Giả sử T là cây. Khi đó theo định nghĩa cây, T
không chứa chu trình. Vì vậy để chứng minh (b) ta chỉ còn phải chứng minh
rằng T có |V |−1 cạnh.Ta chứng minh khẳng định này bằng quy nạp theo |V |.
Khẳng định là hiển nhiên đúng nếu |V | = 1. Giả sử với mọi |V | ≤ k, khẳng
định đã được chứng minh là đúng. Ta chứng minh nó đúng cho |V | = k + 1.
Giả sử e = {u, v} là một cạnh của cây T. Xóa cạnh này ra khỏi T ta
thu được đồ thị mới T’. Nếu u và v cùng thuộc một thành phần liên thông
u với v, thì uevP là một hành trình khép kín. Từ hành trình này ta có thể
24
cuả T’ và chẳng hạn P là một hành trình của thành phần liên thông đó nối
xây dựng được một chu trình trong T. Điều này mâu thuẫn với giả thiết T
là cây. Vậy u và v phải thuộc hai thành phần liên thông khác nhau của T’,
T3. Điều này mâu thuẫn với giả thiết rằng T là đồ thị liên thông. Vậy T’ có đúng hai thành phần liên thông là T1 = (V1, E1) và T2 = (V2, E2). Khi đó Ti là cây với |Vi| ≤ k, và theo giả thiết qui nạp, |Ei| = |Vi| − 1, i = 1, 2. Ta có
|V | = |V1| + |V2|
|E| = |E1| + |E2| + 1
chẳng hạn u thuộc thành phần liên thông T1, còn v thuộc thành phần liên thông T2 của T’. Nếu ngoài T1 và T2, T còn có thành phần liên thông T3, thì trong T ta không thể nối u bằng một hành trình với một đỉnh x trong
|E| = |E1| + |E2| + 1 = (|V1| − 1) + (|V2 − 1) + 1
= (|V1| + |V2|) − 1 = |V | − 1.
Suy ra,
|V | − 1. Để chứng minh khẳng định (c) ta chỉ còn phải chứng minh rằng T
2. (b) ⇒ (c): Giả sử T là đồ thị không chứa chu trình và có |E| =
là đồ thị liên thông. Giả sử T không liên thông. Khi đó T bao gồm k ≥ 2
|E| = |E1| + |E2| + ... + |EK|
= (|V1| − 1) + (|V2| − 1) + ... + (|Vk| − 1) = |V | − k.
thành phần liên thông chẳng hạn là T1, T2, ...., Tk. Do T không chứa chu trình, nên các thành phần liên thông Ti = (Vi, Ei), i = 1, 2, ..., k, là cây. Vì (a) ⇒ (b) đã được chứng minh, nên ta suy ra |Ei| = |Vi| − 1, i = 1, 2, ..., k. Vì |E| = |E1| + |E2| + ... + |EK|, |V | = |V1| + |V2| + ... + |VK|, nên ta có
|V | − 1. Vậy T phải là đồ thị liên thông.
Vì k ≥ 2, nên đẳng thức nhận được mâu thuẫn với giả thiết |E| =
3. (c) ⇒ (d): Trước hết ta chứng minh rằng nếu một đồ thị vô hướng
|V | − k. Ta chứng minh khẳng định này bằng qui nạp theo |E|. Với |E| = 0,
không có khuyên bất kỳ G = (V, E) có k thành phần liên thông thì |E| ≥
25
khẳng định trên là hiển nhiên đúng vì khi đó G = On, tức là k = |V |. Giả sử khẳng định đã được chứng minh là đúng cho các đồ thị có t cạnh và
G = (V, E) là một đồ thị vô hướng liên thông với |E| = t + 1. Nếu ta xóa đi
một cạnh của G thì đồ thị nhận được G’ sẽ có |V | đỉnh, t cạnh và số thành
phần liên thông hoăc bằng k hoặc bằng k + 1. Nếu số thành phần liên thông
bằng k thì theo giả thiết qui nạp t ≥ |V | − k. Suy ra, |E| = t + 1 ≥ |V | − k
và đây là điều ta cần chứng minh. Nếu số thành phần liên thông bằng k + 1,
|E| = t + 1 ≥ (|V | − k − 1) + 1 = |V | − k và đây cũng là điều ta cần chứng
thì cũng theo giả thiết qui nạp, t ≥ |V | − (k + 1) = |V | − k − 1. Suy ra,
minh.
Bây giờ ta chứng minh (c) ⇒ (d). Giả sử T = (V, E) là đồ thị vô
hướng liên thông với |E| = |V | − 1. Nếu xóa một cạnh của T thì đồ thị
nhận được T’ sẽ có |E| − 1 cạnh. Nếu T’ vẫn liên thông, thì theo khẳng định
|E| − 1 = |V | − 2. Ta nhận được |V | − 2 ≥ |V | − 1. Mâu thuẫn. Vậy đồ thị
vừa chứng minh ở đoạn trên, |E| − 1 ≥ |V | − 1. Nhưng |E| = |V | − 1, nên
nhận được từ T bằng cách xóa đi một cạnh bất kỳ là không liên thông.
4. (d) ⇒ (e): Giả sử T = (V, E) là đồ thị thỏa mãn (d). Vì T liên
thông nên hai đỉnh khác nhau bất kỳ u và v của T được nối với nhau bằng
Q1 là đoạn hành trình của Q từ u tới lần xuất hiện đầu tiên của a trong Q, còn Q2 là đoạn hành trình của Q từ lần xuất hiện cuối cùng của a trong Q tới v. Khi đó Q1 ∪ Q2 là hành trình trong T nối u với v, trong đó đỉnh a xuất hiện đúng một lần. Lặp lại quá trình trên một số hữu hạn lần ta sẽ
một hành trình Q. Giả sử đỉnh a là đỉnh xuất hiện ít nhất hai lần trong Q.
nhận được đường P trong T nối u với v.
Giả sử hai đỉnh khác nhau u và v của T được nối với nhau bằng hai
đường khác nhau P1 và P2. Khi đó Q = P1 ∪ P2 là một hành trình khép kín trong T. Nếu e = {u, v} là một cạnh của Q, thì T − e sẽ là đồ thị liên thông.
Thật vậy, nếu hành trình H nào đó trong T nối hai đỉnh khác nhau x và y
không chứa cạnh e thì H cũng là hành trình trong T − e nối x và y; còn nếu
H chứa e thì (H − e) ∪ (Q − e) sẽ là hành trình trong T − e nối x và y.
Điều vừa nhận được mâu thuẫn với (d). Vậy hai đỉnh khác nhau bất kỳ của
T được nối với nhau bởi đúng một đường.
5. (e) ⇒ (f ): Giả sử đồ thị vô hướng T = (V, E) thỏa mãn (e). Khi đó
26
T không chứa chu trình vì trong trường hợp ngược lại hai đỉnh khác nhau
bất kỳ của chu trình đó sẽ được nối với nhau bằng hai đường. Bây giờ nếu
thêm vào T một cạnh e nối hai đỉnh u và v không kề nhau nào đó trong
T, thì cạnh e đó cùng với đường nối u với v trong T sẽ tạo thành chu trình
trong đồ thị T + e. Nếu trong T + e có hai chu trình là C1 và C2, thì dễ thấy rằng cả C1 và C2 đều chứa e (vì T không chứa chu trình). Khi đó C1 − e và C2 − e là hai đường khác nhau nối u với v. Điều này mâu thuẫn với (e). Vậy T + e có đúng một chu trình.
6. (f ) ⇒ (a): Giả sử đồ thị vô hướng T = (V, E) thỏa mãn (f). Để
chứng minh T là cây ta chỉ còn phải chứng minh rằng T liên thông.
Giả sử T không liên thông. Khi đó T có ít nhất là hai thành phần liên
thông. Nếu ta thêm một cạnh nối hai đỉnh không kề nhau nhưng thuộc hai
thành phần liên hông khác nhau của T thì ta không nhận được một chu trình
nào trong đồ thị nhận được. Điều này mâu thuẫn với giả thiết (f). Vậy T liên
thông và cùng với khẳng định (f). T là cây
n
di = 2n − 2,
di ≥ 1.
i=1 X
Mệnh đề 2.1.7. Giả sử cho trước các đỉnh v1, . . . , vn và các số nguyên dương d1, . . . , dn sao cho
.
(n − 2)! (d1 − 1)! . . . (dn − 1)!
Khi đó số cây có tập đỉnh {v1, . . . , vn} sao cho đỉnh vi có bậc di với i = 1, 2, . . . , n là
Chứng minh. Ta chứng minh bằng quy nạp theo n. Với n = 1, 2, khẳng định
n
di = 2n − 2 < 2n
là hiển nhiên. Do
Xi=1
27
nên ta luôn tìm được một chỉ số i sao cho di = 1. Không mất tính tổng quát ta giả sử dn = 1. Ta thực hiện xóa đỉnh vn. Ta nhận thấy rằng đỉnh vn sẽ được nối với một đỉnh vj với 1 ≤ j ≤ n − 1 nào đó và khi ta thực hiện xóa đỉnh vn thì cây thu được có tập đỉnh là {v1, v2, . . . , vn−1} với các bậc tương ứng là d1, . . . , dj−1, dj − 1, dj+1, . . . , dn−1. Ngược lại, nếu cho trước một cây có tập đỉnh là {v1, v2, . . . , vn−1} với dãy bậc là d1, . . . , dj−1, dj −1, dj+1, . . . , dn−1 thì bằng cách nối đỉnh vj với đỉnh vn ta sẽ thu được một cây trên {v1, v2, . . . , vn}
.
=
(n − 3)! (d1 − 1)! . . . (dj−1 − 1)!(dj − 2)!(dj+1 − 1)! . . . (dn−1 − 1)! (dj − 1)(n − 3)! (d1 − 1)! . . . (dj−1 − 1)!(dj+1 − 1)! . . . (dn−1 − 1)!
với dãy bậc tương ứng là d1, . . . , dn . Theo giả thiết quy nạp, số cây trên {v1, v2, . . . , vn} có dãy bậc d1, . . . , dj−1, dj − 1, dj+1, . . . , dn−1 là
n−1
n−1
=
(dj − 1)
Do đó, số cây trên {v1, v2, . . . , vn} với dãy bậc tương ứng d1, . . . , dn là
(dj − 1)(n − 3)! (d1 − 1)! . . . (dn−1 − 1)!
(n − 3)! (d1 − 1)! . . . (dn−1 − 1)!
.
=
(n − 3)! (d1 − 1)! . . . (dn−1 − 1)! (n − 2)! (d1 − 1)! . . . (dn−1 − 1)!
Xj=1 Xj=1 = (n − 2)
n−1
k
Tn =
TkTn−k.
n − 2 k − 1!
Mệnh đề 2.1.8. Kí hiệu Tn là số cây trên {v1, v2, . . . , vn}. Khi đó
Xk=1
Chứng minh. Nếu T là một cây trên V = {v1, v2, . . . , vn} và e ∈ E(T ) thì T − e chứa hai cây phân biệt T ′, T ′′, và chúng phủ V . Bằng cách này ta thu được (n − 1)Tn cặp (T ′, T ′′). Giả sử, T ′, T ′′ là hai cây phân biệt và chúng phủ V ; đặt |V (T ′)| = k, |V (T ′′)| = n − k. Khi đó ta có k(n − k) cách để bổ sung thêm một cạnh nối T ′ với T ′′ để thu được một cây trên V . Do đó từ một cặp (T ′, T ′′) này sinh ra k(n − k) cây T . Số các cặp (T ′, T ′′) thỏa mãn
TkTn−k. Do đó
n−2 k−1
n−1
như vậy là
(n − 1)Tn =
TkTn−kk(n − k).
n − 1 k − 1!
(cid:0) (cid:1)
n−1
Xk=1 Suy ra
.
k
=
Tn =
TkTn−k
n − 1 n − k
n − 2 k − 1!
n − 2 k − 1!
n − 1 k − 1!
do
Xk=1
28
Định lý 2.1.9 (Công thức Cayley). Số cây có n đỉnh đúng bằng nn−2.
=
(n − 2)! (d1 − 1)! . . . (dn − 1)!
(n − 2)! k1! . . . kn!
Chứng minh. Theo kết quả của Bài toán 1.2.2, ta suy ra số cây có n chính là n
1 + . . . + 1 n
! Xk1,...,kn≥1 k1+...+kn=2n−2 Xd1,...,dn≥1 d1+...+dn=2n−2
2.2. Công thức tính số cây khung
| {z }
Mục này trình bày một cách tính toán số lượng cây khung cực đại
của một đồ thị cho trước. Trước hết ta nhắc lại một số khái niệm trong lý
thuyết đồ thị. Mục này tham khảo theo bài giảng Algebraic combinatorics
của Lionel Levine (Bài giảng 19).
Giả sử G = (V, E) là một đồ thị có hướng với V = {v1, v2, v3, . . . , vn}.
Khi đó ma trận kề của đồ thị G là ma trận
a11 a12 a21 a22 ... ... an1 an2
· · · a1n · · · a2n ... ... · · · ann
A = (aij)n×n =
1, nếu (vi, vj) ∈ E,
0, nếu (vi, vj) /∈ E.
Ở đây aij = (
G. Vì vậy, ma trận kề A được coi là một biểu diễn của G.
Dễ thấy rằng ma trận kề A của đồ thị có hướng G hoàn toàn xác định
Ví dụ 2.2.1. Giả sử G = (V, E) với V = {v1, v2, v3, v4, v5, v6} và E = {e1, e2, . . . , e10} là đồ thị có hướng được biểu diễn bằng Hình 7.1. Khi đó, ma trận kề của G là ma trận
A =
0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 1
29
Già sử G = (V, E) là đồ thị có hướng với V = {v1, v2, . . . , vn} và
E = {e1, e2, . . . , em}. Khi đó ma trận liên thuộc của đồ thị G là ma trận
,
b11 b12 b21 b22 ... ... bn1 bn2
. . . b1m . . . b2m ... ... . . . bnm
B = (bij)n×m =
v1
e1
v2
e7
e2
e10
v6
e8
e4
v3
e9
e5
v5
e6
v4
e3
Hình 7.1. Đồ thị có hướng G của ví dụ 7.1.
Ở đây
nếu vi là đỉnh đầu của ej
nếu vi không liên thuộc với ej.
1, bij = −1, nếu vi là đỉnh cuối nhưng không là đỉnh đầu của ej 0,
Ma trận liên thuộc B cũng hoàn toàn xác định đồ thị có hướng G. Vì
vậy, B cũng được coi là một biểu diễn của G.
Ví dụ 2.2.2. Giả sử G = (V, E) là đồ thị có hướng cho ở Ví dụ 7.1. Khi đó
1 −1
ma trận liên thuộc G là ma trận
,
0 0 0 1 1 0 1 0 0 −1 0 −1 0 0 0 0 0 0 −1 0 0 0 0 0 0
0 0 0 1 −1 0 0
0 −1 −1 0 0 0 0 0 0 0 0 1 −1 1 1 0
0 0 0 0 1
0 0 0 1 0
H = (V, A) với A ⊆ E, được gọi là đồ thị con khung của đồ thị G.
Định nghĩa 2.2.3. (i) Một đồ thị con H của đồ thị G = (V, E) có dạng
(ii) Cho trước một đồ thị hữu hạn G với n đỉnh. Đồ thị con T được gọi
là cây khung của đồ thị G nếu T là đồ thị con khung đồng thời là một cây
30
với số cạnh tối thiểu.
D − A với
(iii) Ma trận Laplacian của đồ thị G được định nghĩa bởi hệ thức L =
1 . A là ma trận kề của đồ thị G,
dv1
dv2
2 . D là ma trận chéo được xác định như sau
,
dvn
D =
. . .
trong đó dvi = deg(vi), là số lượng các đỉnh liên hợp với đỉnh vi.
Đặt κ(G) là lực lượng của số cây khung của đồ thị G.
|V | = n. Khi đó
κ(G) =
λ1λ2 . . . λn−1
1 n
Định lý 2.2.4 (Kirchhoff). Cho trước một đồ thị liên thông G = (V, E) với
trong đó λi là các giá trị riêng khác không của ma trận L.
Thông thường để chứng minh Định lý Kirchhoff ta sẽ dựa trên công
thức Cauchy-Binet. Ở đây luận văn trình bày một cách chứng minh bằng
cách mở rộng đối tượng khảo sát cho các đồ thị định hướng và coi đồ thị vô
hướng như là một trường hợp đặc biệt. Trước hết ta có định nghĩa
Định nghĩa 2.2.5. (i) Cho trước một đồ thị định hướng Γ = (V, E). Đồ thị
r ∈ V nếu ba điều kiện sau được thỏa mãn:
con T = (V, A) được gọi là cây khung định hướng của đồ thị Γ với gốc tại
1 . Mọi đỉnh v 6= r đều có bậc ngoài bằng 1;
2 . Đỉnh r có bậc ngoài bằng 0;
3 . Đồ thị T không chứa chu trình định hướng.
D − A với
(ii) Ma trận Laplacian của đồ thị Γ được định nghĩa bởi hệ thức L =
31
1 . A là ma trận kề của đồ thị Γ;
dv1
dv2
2 . D là ma trận chéo được xác định như sau:
,
dvn
D =
. . .
trong đó dvi = outdeg(vi) = |{vj ∈ E : (vi, vj) ∈ E}|.
Đặt κ(Γ, r) là khung định hướng của Γ có gốc tại r.
κ(Γ, r) = det Lr
Định lý 2.2.6 (Kirchhoff). Cho trước đồ thị liên thông Γ = (V, E). Khi đó
với Lr là ma trận nhận được từ L bằng cách xóa đi hàng r và cột r.
Chứng minh Định lí 2.2.6. Không giảm tính tổng quát của bài toán ta đánh
số lại các đỉnh của đồ thị Γ sao cho r là đỉnh thứ n. Áp dụng công thức khai
det Lr =
sign(σ)L1,σ(1)L2,σ(2) . . . Ln−1,σ(n−1).
triển Leibniz cho định thức det Lr ta nhận được
Xσ∈Sn−1
sign(σ)
det Lr =
di
Li,σ(i).
Đặt Fix(σ) = {i | σ(i) = i}. Khi đó,
Xσ∈Sn−1 Yi /∈Fix(σ) Yi∈Fix(σ)
Phép chứng minh được kết thúc.
Nhận xét 2.2.7. Thừa số
i /∈Fix(σ) Li,σ(i) chỉ khác không khi và chỉ khi (i, σ(i)) ∈ E với mọi i /∈ Fix(σ). Do ma trận Lr có các số di nằm trên đường chéo chính và các số −1 hoặc 0 nằm ở các vị trí còn lại nên ta nhận
Q
Li,σ(i) = (−1)n−1−| Fix(σ)|.
được
Yi /∈Fix(σ)
Nhận xét 2.2.8. Mọi hoán vị σ đều có thể được phân tích thành tập các
Q
32
điểm bất động, và các chu trình và nếu gọi H = T ∪ C1 ∪ . . . Ck là đồ thị i∈Fix(σ) di đếm con cảm sinh từ hoán vị σ sao cho T ⊆ Fix(σ) thì thừa số số các đồ thị con H = T ∪ C1 ∪ . . . Ck sao cho mỗi đỉnh v ∈ Fix(σ) đều có bậc ngoài bằng 1.
sign(σ)(−1)n−1−| Fix(σ)|.
CH =
Từ nhận xét vừa nêu ở trên, ta nhận thấy bằng cách đặt
X{σ∈Sn−1|T ⊆Fix(σ)}
det Lr =
CH.
H là một đồ thị con của Γ X
ta có thể biểu diễn lại định thức dưới dạng
1 nếu H là một cây khung định hướng và 0 trong trường hợp ngược lại.
Để chứng minh khẳng định của bài toán ta cần chỉ ra rằng: CH bằng
Thật vậy, nếu H là một cây thì tất cả các đỉnh đều nằm trong Fix(σ)
1 và n − 1 điểm đều là các điểm bất động nên CH = 1.
và σ chính là hoán vị đồng nhất. Do dấu của hoán vị đồng nhất luôn bằng
sign(σ) = (−1)(|Ci1 |−1)+...+(|Cil |−1).
Sau cùng, ta chỉ cần chỉ ra rằng CH = 0 nếu k ≥ 1, tức là khi H chứa một chu trình. Giả sử Ci1, . . . , Cil là các chu trình tương ứng với các chu trình của hoán vị σ nên
(−1)(|Ci1 |−1)+...+(|Cil |−1)(−1)|Ci1|+...+|Cil |
CH =
Khi đó
=
(−1)|S|
X{i1,...,il}∈[k]
=
(−1)l
k l !
XS⊂[k] k
= (1 − 1)k = 0,
Xl=0 nếu k ≥ 1.
Bây giờ ta sẽ sử dụng Định lí 2.2.6 để chứng minh tính đúng đắn của
Định lí 2.2.4 như sau:
Chứng minh Định lí 2.2.4. Cho trước đồ thị vô hướng G và gọi Γ là đồ thị
G.
định hướng với các cạnh (i, j) và (j, i) được cảm sinh từ các cạnh của đồ thị
Nhận xét rằng, tồn tại một tương ứng giữa tập các cây khung của Γ
33
có gốc tại r và tập các cây khung của G.
Thật vậy, ta chọn một cây khung định hướng của Γ có gốc tại r và
thu được một cây khung của G bằng cách xóa đi gốc và định hướng của các
cạnh. Ngược lại, với một cây khung T của G, ta thu được một cây khung
định hướng của Γ bằng cách định hướng lại các cạnh sao cho chỉ có một
đường đi duy nhất từ một đỉnh bất kì của đồ thị G đến đỉnh r, một đường
đi như thế luôn tồn tại do T là một đồ thị liên thông và T là một cây nên
đường đi này là duy nhất.
n
nκ(G) =
κ(G, r).
r=1 X
Khi đó,
Giả sử L là ma trận Laplacian của đồ thị Γ. Khi đó, đa thức đặc trưng
χ(t) = det(tI − L).
của ma trận L được định nghĩa bởi hệ thức
n
det Lr = (−1)n−1[t]χ(t),
r=1 X
Áp dụng các kết quả đã biết từ lý thuyết đại số tuyến tính ta thu được
trong đó [t]χ(t) là hệ số của t trong khai triển của đa thức χ(t).
n
κ(G, r)
nκ(G) =
r=1 X n
=
det Lr = (−1)n−1[t]χ(t)
r=1 X
n
= (−1)n−1[t]
(t − λi) các giá trị riêng của ma trận L và λn = 0
Kết hợp các phân tích vừa nêu ta thu được
Yi=1 = (−1)n−1(−1)n−1λ1λ2 . . . λn−1.
κ(G) =
λ1λ2 . . . λn−1.
1 n
Vậy
2.3. Đánh giá số cạnh của một đồ thị phẳng
Phép chứng minh được kết thúc.
Mục này thao khảo chính theo cuốn sách Lý thuyết tổ hợp và đồ thị
34
của Ngô Đắc Tân và cuốn Problem-solving methods in combinatorics, an
ap-proach to olympiad problems của P. Soberón.
Định nghĩa 2.3.1. đồ thị vô hướng G = (V, E) được gọi là đồ thị phẳng nếu
như nó có thể biểu diễn được ở trên mặt phẳng sao cho các đường cong biểu
diễn các cạnh hoặc không giao nhau hoặc giao nhau chỉ ở các đỉnh chung.
Biểu diễn nói trên của đồ thị phẳng được gọi là biểu diễn phẳng.
K5
K3,3
K4
K4
Hình 2.2: Ví dụ đồ thị phẳng và đồ thị không phẳng
Ta sẽ đồng nhất đồ thị phẳng với một biểu diễn phẳng của nó.
Ví dụ 2.3.2. Trên Hình 2.2 ta có hai biểu diễn của đồ thị đầy đủ K4. Biểu diễn ở bên trái không là biểu diễn phẳng, còn biểu diễn ở bên phải là biểu
diễn phẳng của K4. Như vậy, đồ thị K4 là đồ thị phẳng.
Đồ thị đầy đủ K5 và đồ thị 2-phần đầy đủ K3,3 (Hình 2.2) không là
đồ thị thị phẳng.
Giả sử G = (V, E) là một đồ thị phẳng. Khi đó, phần mặt phẳng được
giới hạn bởi các cạnh của G và không bị chia thành các phần nhỏ hơn bởi
các cạnh khác được gọi là một miền (hay cũng gọi là một mặt) của G.
Định lý 2.3.3 (Công thức Euler cho đồ thị phẳng). Nếu đồ thị phẳng liên
thông G = (V, E) có v đỉnh, c cạnh và f miền, thì v − e + f = 2.
Chứng minh. Ta chứng minh định lý này bằng quy nạp theo f . Nếu f = 1,
thì G không chứa chu trình. Suy ra, G là cây vì nó liên thông. Từ Định lý
2.1.6 suy ra Định lý 2.3.3 đúng trong trường hợp này.
Bây giờ giả sử đồ thị phẳng liên thông G có số miền f > 1 và giả sử
Định lý 2.3.3 đã được chứng minh là đúng cho mọi đồ thị phẳng liên thông
có số miền nhỏ hơn f . Vì f > 1, nên G chứa chu trình. Giả sử {u, v} là một
35
cạnh của một chu trình của G. Vì mỗi chu trình tách mặt phẳng làm hai
phần rời nhau, nên cạnh {u, v} thuộc biên của hai miền, chẳng hạn S và T.
Nếu xóa cạnh {u, v}, thì ta nhận được một đồ thị phẳng liên thông G’ mới,
trong đó các miền S và T được nhập lại với nhau tạo thành một miền mới,
còn các miền khác giữ nguyên không đổi. Như vậy là G’ có v đỉnh, e − 1 cạnh
và f − 1 miền. Theo giả thiết qui nạp, v − (e − 1) + (f − 1) = 2. Nhưng
đẳng thức này hiển nhiên tương đương với v − e + f = 2.
Trước khi phát biểu và chứng minh một kết quả nữa về đồ thị phẳng
liên thông, ta đưa ra các khái niệm mới là chu vi nhỏ nhất và chu vi lớn nhất
của đồ thị.
Định nghĩa 2.3.4. Độ dài của chu trình ngắn nhất trong một đồ thị được
gọi là chu vi nhỏ nhất (girth) của đồ thị đó. Chu vi nhỏ nhất của đồ thị G
thường được ký hiệu là g(G) hay ngắn gọn là g nếu đồ thị G được hiểu rõ
từ ngữ cảnh.
Định nghĩa 2.3.5. Tương tự, độ dài của chu trình dài nhất trong một đồ
thị được gọi là chu vi lớn nhất (circumference) của đồ thị đó. Chu vi lớn nhất
của đồ thị G thường được ký hiệu là c(G) hay ngắn gọn là c nếu đồ thị G
được hiểu rõ từ ngữ cảnh.
Nếu như trong đồ thị vô hướng G không tồn tại chu trình, tức là khi G
∞.
là rừng, thì chu vi nhỏ nhất và chu vi lớn nhất của G được định nghĩa bằng
G = (V, E) bất kỳ với chu vi nhỏ nhất g thỏa mãn 3 ≤ g ≤ ∞ ta luôn có
(|V | − 2).
|E| ≤
g g − 2
Định lý 2.3.6 (Bất đẳng thức cạnh đỉnh). Trong đồ thị phẳng liên thông
Chứng minh. Giả sử G = (V, E) là đồ thị phẳng liên thông thỏa mãn điều
điện của Định lý 2.3.6. Ta cũng giả sử rằng G có E = {e1, e2, ...el} và các miền f1, f2, ..., fl. Ta xác định ma trận X = (xij)t×l cỡ t × l như sau:
xij =
1 nếu ei là một cạnh trên biên của miền fj, 0 trong trường hợp ngược lại.
(2.1) (
36
Ma trận X xác định như trên gọi là ma trận cạnh-miền của đồ thị phẳng G.
Vì mỗi cạnh của G là một cạnh trên biên của nhiều nhất là hai miền,
nên trong mỗi hàng của ma trận X có nhiều nhất là hai số 1. Mặt khác, các
cạnh ở trên biên của mỗi miền tạo thành một chu trình trong G. Do đó,
mỗi cột của ma trận X có ít nhất g số 1, ở đây g là chu vi nhỏ nhất của
gl ≤ s ≤ 2t.
G. Vì vậy, nếu s là số các số 1 có trong X, thì ta có các bất đẳng thức sau đây:
Mặt khác, vì G liên thông theo Định lý 2.3.3, l = t − |V | + 2. Sau khi thay
gl = gt − g|V | + 2g ≤ 2t
(|V | − 2).
⇔ |E| ≤
⇔ t(g − 2) ≤ g(|V | − 2) g g − 2
thế vào các bất đẳng thức trên ta được
Bất đẳng thức cạnh đỉnh ở định lý trên có thể áp dụng để chứng minh
nhiều đồ thị không là đồ thị phẳng.
Hệ quả 2.3.7. Đồ thị đầy đủ K5 và đồ thị 2-phần đầy đủ K3,3 không là đồ thị phẳng.
Chứng minh. Đồ thị K5 có 5 đỉnh, 10 cạnh và chu vi nhỏ nhất g = 3. Nếu K5 là đồ thị phẳng, thì theo bất đẳng thức cạnh đỉnh 10 ≤ 3 3−2(5 − 2) = 9. Mâu thuẫn. Vậy K5 không là đồ thị phẳng.
K3,3 là đồ thị phẳng, thì theo bất đẳng thức cạnh đỉnh 9 ≤ 4 Mâu thuẫn. Vậy K3,3 không là đồ thị phẳng.
Tương tự, đồ thị K3,3 có 6 đỉnh, 9 cạnh và chu vi nhỏ nhất g bằng 4. Nếu 4−2(6 − 2) = 8.
Xét trường hợp đặc biệt, đánh giá số cạnh cho đồ thị không chứa chu
trình chẵn
(|V | − 1).
|E| ≤
3 2
Mệnh đề 2.3.8. Mọi đồ thị G = (V, E) không có chu trình độ dài chẵn thì
37
Để chứng minh bài toán này, ta cần bổ đề sau :
Bổ đề 2.3.9. Mọi đồ thị G không có chu trình độ dài chẵn thì không có hai
chu trình nào có cạnh chung.
Giả sử phản chứng, ta tìm được hai chu trình C1 và C2 có cạnh chung. Gọi độ dài cạnh chung là x, độ dài của C1 không nằm trên phần chung là y và độ dài của C2 không nằm trên phần chung là z. Ta có x + y và x + z là các số lẻ nên ta suy ra y + z là số chẵn (do 2x + y + z là số chẵn). Điều này
mâu thuẫn với giả thiết đồ thị G không chứa chu trình độ dài chẵn. Phép
chứng minh bổ đề được kết thúc.
Chứng minh Mệnh đề 2.3.8. Từ Bổ đề 2.3.9 suy ra mỗi cạnh thuộc tối đa
một chu trình. Gọi c là số chu trình chứa trong đồ thị G thì ta có |E| ≥ 3c,
bởi vì một chu trình độ dài lẻ chứa ít nhất là 3 cạnh. Mặt khác nếu ta xóa
đi một cạnh từ mỗi chu trình thì ta được một rừng, hay |E| − c ≤ |V | − 1.
+ |V | − 1.
|E| ≤ c + |V | − 1 ≤
|E| 3
Kết hợp cả hai đánh giá trên ta suy ra
|E| ≤
(|V | − 1).
3 2
Vậy
2.4. Số tam giác trong đồ thị
Phép chứng minh bài toán được kết thúc.
Mục này đề cập một số bài toán đếm trên đồ thị gắn liền với các đề
thi học sinh giỏi ở phổ thông. Tài liệu tham khảo chính là cuốn Problem-
solving methods in combinatorics, an ap-proach to olympiad problems của
P. Soberón (Bài tập 4.15, 4.16).
Mệnh đề 2.4.1. (i) Cho G là một đồ thị k-chính quy, có n đỉnh. Khi đó số
tam giác trong G bằng
C 3
(n − k − 1) .
n −
nk 2
(9.2)
n (n − 1) (n − 5) 24
(ii) Cho G là đồ thị có n đỉnh. Khi đó trong G có ít nhất
38
tam giác.
Chứng minh. (i) Với đỉnh x của G, kí hiệu d (x) chỉ số cạnh nối đến x. Số bộ
ba đỉnh (x, y, z) không tạo thành ba đỉnh của một tam giác là d (x) [n − 1 − d (x)]
d (x) [n − 1 − d (x)].
suy ra số bộ ba đỉnh không tạo thành ba đỉnh của một tam giác là
Xx∈X
Tuy nhiên trong tổng này bộ ba đỉnh (x, y, z) không tạo thành một
tam giác được lặp lại đúng hai lần nên số bộ ba đỉnh không tạo thành một
d (x) [n − 1 − d (x)].
1 2
tam giác sẽ là
C 3
.
d (x) [n − 1 − d (x)] = C 3
n −
n −
1 2
nk (n − 1 − k) 2
Xx∈X Vậy số tam giác tạo thành sẽ là
Xx∈X
2
C 3
.
=
d (x) [n − 1 − d (x)] ≥ C 3
n −
n −
1 2
n − 1 2
1 2
n (n − 1) (n − 5) 24
(ii) Sử dụng bất đẳng thức AM – GM ta có
(cid:18) (cid:19) Xx∈X
k
Mệnh đề 2.4.2. (APMO 1989) Chứng minh rằng một đồ thị n đỉnh, k cạnh
4k − n2 3n
tam giác. thì sẽ có ít nhất
(cid:0) (cid:1) Giải. Giả sử G = (X, U ), trong đó |X| = n, |U | = k. Giả sử x, y là hai đỉnh
kề phân biệt của tập X; Từ x có d(x) − 1 cạnh và từ y có d(y) − 1 cạnh,
d(x) − 1 + d(y) − 1 − (n − 2) = d(x) + d(y) − n
khác với cạnh [x, y]. Vì có n − 2 đỉnh khác nên x, y là cạnh kề của ít nhất
đỉnh chung Do đó, ta có số tam giác chứa cạnh [x; y] ít nhất là d (x)+d (y)−n.
A =
[d (x) + d (y) − n].
1 3
Suy ra số tam giác trong đồ thị đã cho có ít nhất là
X[x;y]∈U
[d (x)]2.
[d (x) + d (y) − n] =
Mặt khác ta dễ thấy đẳng thức sau:
39
Xx∈U X[x;y]∈U
2
.
=
d (x)
− nk
A ≥
4k2 − nk
Từ đó theo bất đẳng thức Cauchy – Schwartz ta có:
1 3
1 3
40
! Xx∈X (cid:0) (cid:1)
Kết luận
Luận văn Một số bài toán đếm trong lý thuyết đồ thị đã đạt được các kết quả
sau:
- Tìm hiểu về đại số tổ hợp, công thức đa thức.
- Tìm hiểu các khái niệm, tính chất cơ bản của lý thuyết đồ thị.
- Tìm hiểu về bài toán đếm cây trên tập đỉnh cho trước; đếm đỉnh,
đếm cạnh để tìm hiểu cấu trúc của cây.
- Tìm hiểu cách biểu diễn đồ thị bằng ma trận và đếm số cây khung
bằng các giá trị riêng của ma trận Laplacian.
- Tìm hiểu đánh giá số đỉnh số cạnh trong đồ thị phẳng.
- Tìm hiểu bài toán đếm số tam giác trong đồ thị.
- Một số bài toán đếm khác như đếm rừng, ... sẽ được được tác giả tìm
41
hiểu trong thời gian tới.
Tài liệu tham khảo
Tiếng Việt
[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.
[3] Một số đề thì học sinh giỏi quốc gia và quốc tế, Olympic 30.4, Olympic
Tiếng Anh
sinh viên.
[4] M. Bóna (2007), Introduction to enumerative combinatorics, Higher Ed-
ucation.
[5] L. Levine, Algebraic combinatoricst, https://www.sciencedirect.com/book
/9780444815040/combinatorial-problems-and-exercises.
[6] L. Lovász (1993), Combinatorial problems and exercises, 2nd edition,
Elsevier.
[7] Y. Jin, C. Liu (2003), The enumeration of labelled spanning trees of km,n,
Australasian Journal of Combinatoric, Volume 28, Pages 73-79.
[8] P. Soberón (2013), Problem-solving methods in combinatorics, an ap-
proach to olympiad problems, Birkhauser.
[9] Y. Zhang (2011), Combinatorial problems in mathematical competitions,
World Scientific.
![Luận văn Thạc sĩ: Tổng hợp và đánh giá hoạt tính chống ung thư của hợp chất lai chứa khung tetrahydro-β-carboline và imidazo[1,5-a]pyridine](https://cdn.tailieu.vn/images/document/thumbnail/2025/20250807/kimphuong1001/135x160/50321754536913.jpg)
