Preview text:
Khoa CNTT, trường ĐH Khoa học tự nhiên TPHCM. Môn Toán học tổ hợp
BÀI TẬP MẪU CHỦ ĐỀ 7.
ĐƯỜNG ĐI – CHU TRÌNH. HAMILTON/EULER. Bài 1.
a) Cho một đồ thị G đầy đủ có 6 đỉnh được đánh số từ 1 đến 6. Hỏi có bao nhiêu đường đi Hamilton
trên G mà xuất phát từ đỉnh 1?
b) Cho một đồ thị G đầy đủ có 100 đỉnh. Hỏi cần xoá đi ít nhất mấy cạnh để đồ thị mới thu được sẽ có chu trình Euler? Lời giải.
a) Từ đỉnh 1, ta có 5 cách chọn để đi đến 1 trong 5 đỉnh x tiếp theo. Từ đỉnh đó lại có 4 cách chọn
để đi đến đỉnh y tiếp theo mà khác 1 và x. Cứ thế, số cách sẽ là 5.4.3.2.1 = 120.
b) Ta thấy bậc mỗi đỉnh hiện tại trong đồ thị G là 99, là số lẻ. Để tồn tại chu trình Euler thì bậc các
đỉnh phải chẵn, tức là mỗi đỉnh phải giảm 1 bậc, mà mỗi cạnh nối chỉ có 2 đỉnh nên xoá đi 1 cạnh
thì giảm bậc mỗi đỉnh 1 đơn vị. Vì thế số cạnh ít nhất cần xoá là 100/2 = 50.
Chẳng hạn ta sẽ xoá các cạnh nối cặp đỉnh (1-2), (3-4), …, (99-100) thì đồ thị mới thu được sẽ có
bậc tất cả các đỉnh đều là 98. Bài 2.
a) Tại sao ta có thể nói đỉnh khớp (hoặc đỉnh cắt) là có vai trò tương phản với đỉnh cô lập? n
b) Chứng minh rằng graph G có n đỉnh và bậc mỗi đỉnh thì liên thông. 2
c) Chứng minh rằng graph G có n đỉnh và có nhiều hơn 2
C cạnh thì liên thông. n 1 − Lời giải.
a) Khi bỏ đỉnh khớp đi thì số thành phần liên thông bị tăng lên, trong khi đỉnh cô lập là 1 thành
phần liên thông, khi bỏ nó đi thì số thành phần lại giảm xuống.
b) Giả sử phản chứng rằng graph không liên thông, tức là sẽ có ít nhất hai thành phần liên thông. Rõ n
ràng một trong số đó có số cạnh nên bậc mỗi đỉnh trong thành phần liên thông đó chỉ tối đa là 2
n −1, mâu thuẫn. Vậy graph đã cho liên thông. 2
c) Giả sử phản chứng rằng graph không liên thông, tức là sẽ có ít nhất hai thành phần liên thông.
Trong trường hợp có nhiều hơn 2 thành phần, ta thêm cạnh vào để quy về đúng hai thành phần liên
thông. Gọi a,b lần lượt là số đỉnh của hai thành phần này thì ta có a + b = n . Đồng thời số cạnh của 1 1 graph sẽ không quá 2 2 2 2 2 2
C + C = (a − a + b − b) = (a + b − n). a b 2 2
Vì 1 a n −1 nên (a −1)(a − n +1) 0 hay 2
a na − (n −1) . Tương tự với 2 b . Suy ra
Khoa CNTT, trường ĐH Khoa học tự nhiên TPHCM. Môn Toán học tổ hợp 2 2 2
a + b n(a + b) − 2(n −1) = n − 2n + 2 . Do đó 1
(n −1)(n − 2) 2 2
E (n − 2n + 2 − n) = = C , 1 2 2 n−
mâu thuẫn với giả thiết. Bài 3.
a) Chứng minh rằng graph đơn, vô hướng, có bậc mỗi đỉnh ít nhất là 2 thì sẽ có chu trình đơn. Từ
đó chỉ ra rằng nếu bậc mỗi đỉnh đúng bằng 2 thì sẽ tách được thành các chu trình đơn rời nhau.
b) Có 2n kỳ thủ, mỗi người sẽ thi đấu đúng 2 trận cờ: một trận vào ngày 1 và một trận vào ngày 2
(đối thủ trong hai ngày là khác nhau). Chứng minh rằng có thể chọn ra 𝑛 kỳ thủ đôi một chưa thi
đấu với nhau trận nào. Lời giải.
a) Xuất phát từ 1 đỉnh tuỳ ý, đặt là 𝑢1. Do deg(𝑢1) ≥ 2 nên sẽ có một đỉnh nối với 𝑢1, đặt là
𝑢2. Bây giờ vì deg(𝑢2) ≥ 2 nên cũng sẽ tồn tại một đỉnh khác 𝑢1 mà có nối với 𝑢2, đặt là 𝑢3. Cứ
thế, ta luôn sẽ chọn được đỉnh khác với đỉnh trước đó. Vì số đỉnh hữu hạn nên chắc chắn sẽ có đỉnh
lặp lại và lúc này ta có chu trình đơn.
Tiếp theo, nếu bậc mỗi đỉnh trong graph đúng bằng 2 thì thực hiện tương tự trên, ta cũng chọn ra
được một chu trình đơn. Bây giờ chú ý rằng mỗi đỉnh trên đó đều có bậc đúng bằng 2, như thế thì
chu trình đó cũng là một thành phần liên thông. Ta bỏ thành phần đó đi thì cũng không ảnh hưởng
đến bậc của các đỉnh còn lại (tức là cũng bằng 2). Cứ thực hiện tiếp tục như thế là được các chu trình đơn rời nhau.
b) Ta mô hình hoá bài toán thành một graph vô hướng: mỗi kỳ thủ là một đỉnh và hai người đấu
nhau thì hai đỉnh tương ứng sẽ có cạnh nối nhau. Vì đối thủ trong hai ngày là khác nhau nên graph này là graph đơn.
Lúc này, áp dụng kết quả a) thì các đỉnh của graph sẽ chia ra thành các chu trình đơn rời nhau. Chú
ý rằng ta cũng có thể tô màu cạnh ứng với trận đấu ngày 1 là đỏ, còn trận đấu ngày 2 là xanh. Như
thế thì mỗi đỉnh sẽ có 2 cạnh với 2 màu khác nhau, tức là trên chu trình, các cạnh sẽ luân phiên đổi
màu. Điều này cho thấy số đỉnh trên mỗi chu trình là chẵn. Do đó, ta lấy các đỉnh ở vị trí lẻ thì chắc
chắn chúng không kề nhau, và lấy được 1/2 số lượng đỉnh của chu trình. Cứ thực hiện tương tự như
thế với các chu trình còn lại thì ta chọn được 𝑛 đỉnh đôi một không có cạnh nối nhau.
