Bài tập toán rời rạc nâng cao

[post ảnh]

mình xin mượn tý đất nhé!

Bài 19/Chương 3:


http://www.forkosh.dreamhost.com/mimetex.cgi?G_1 = (http://www.forkosh.dreamhost.com/mimetex.cgi?X_1, http://www.forkosh.dreamhost.com/mimetex.cgi?E_1), http://www.forkosh.dreamhost.com/mimetex.cgi?G_2 = (http://www.forkosh.dreamhost.com/mimetex.cgi?X_2, http://www.forkosh.dreamhost.com/mimetex.cgi?E_2), http://www.forkosh.dreamhost.com/mimetex.cgi?G_1 http://www.forkosh.dreamhost.com/mimetex.cgi?%5Cle T, http://www.forkosh.dreamhost.com/mimetex.cgi?G_2 http://www.forkosh.dreamhost.com/mimetex.cgi?%5Cle T, với T = (X,E) , http://www.forkosh.dreamhost.com/mimetex.cgi?E_1 http://www.forkosh.dreamhost.com/mimetex.cgi?%5Ccap http://www.forkosh.dreamhost.com/mimetex.cgi?E_2 http://www.forkosh.dreamhost.com/mimetex.cgi?%5Cne http://www.forkosh.dreamhost.com/mimetex.cgi?%5Coslash . http://www.forkosh.dreamhost.com/mimetex.cgi?G_3 = http://www.forkosh.dreamhost.com/mimetex.cgi?G_1 http://www.forkosh.dreamhost.com/mimetex.cgi?%5Ccap http://www.forkosh.dreamhost.com/mimetex.cgi?G_2. CMR: http://www.forkosh.dreamhost.com/mimetex.cgi?G_3 liên thông.
Chứng minh:
Do http://www.forkosh.dreamhost.com/mimetex.cgi?E_1 http://www.forkosh.dreamhost.com/mimetex.cgi?%5Ccap http://www.forkosh.dreamhost.com/mimetex.cgi?E_2 http://www.forkosh.dreamhost.com/mimetex.cgi?%5Cne http://www.forkosh.dreamhost.com/mimetex.cgi?%5Coslash nên http://www.forkosh.dreamhost.com/mimetex.cgi?X_1 http://www.forkosh.dreamhost.com/mimetex.cgi?%5Ccap http://www.forkosh.dreamhost.com/mimetex.cgi?X_2 http://www.forkosh.dreamhost.com/mimetex.cgi?%5Cne http://www.forkosh.dreamhost.com/mimetex.cgi?%5Coslash.
Mà http://www.forkosh.dreamhost.com/mimetex.cgi?G_3 = http://www.forkosh.dreamhost.com/mimetex.cgi?G_1 http://www.forkosh.dreamhost.com/mimetex.cgi?%5Ccap http://www.forkosh.dreamhost.com/mimetex.cgi?G_2 = (http://www.forkosh.dreamhost.com/mimetex.cgi?X_1 http://www.forkosh.dreamhost.com/mimetex.cgi?%5Ccap http://www.forkosh.dreamhost.com/mimetex.cgi?X_2, http://www.forkosh.dreamhost.com/mimetex.cgi?E_1 http://www.forkosh.dreamhost.com/mimetex.cgi?%5Ccap http://www.forkosh.dreamhost.com/mimetex.cgi?E_2) là đồ thị.
Giả sử http://www.forkosh.dreamhost.com/mimetex.cgi?G_3 không liên thông.
http://www.forkosh.dreamhost.com/mimetex.cgi?%5Cexists i, j http://www.forkosh.dreamhost.com/mimetex.cgi?%5Cin http://www.forkosh.dreamhost.com/mimetex.cgi?X_1 http://www.forkosh.dreamhost.com/mimetex.cgi?%5Ccap http://www.forkosh.dreamhost.com/mimetex.cgi?X_2, i http://www.forkosh.dreamhost.com/mimetex.cgi?%5Cnot%5Csim j trong http://www.forkosh.dreamhost.com/mimetex.cgi?G_3.
http://www.forkosh.dreamhost.com/mimetex.cgi?%5Cbullet i, j http://www.forkosh.dreamhost.com/mimetex.cgi?%5Cin http://www.forkosh.dreamhost.com/mimetex.cgi?X_1, mà http://www.forkosh.dreamhost.com/mimetex.cgi?G_1 liên thông http://www.forkosh.dreamhost.com/mimetex.cgi?%5CRightarrow giữa i, j có đường nối http://www.forkosh.dreamhost.com/mimetex.cgi?l_1 trong http://www.forkosh.dreamhost.com/mimetex.cgi?G_1.
http://www.forkosh.dreamhost.com/mimetex.cgi?%5Cbullet i, j http://www.forkosh.dreamhost.com/mimetex.cgi?%5Cin http://www.forkosh.dreamhost.com/mimetex.cgi?X_2, mà http://www.forkosh.dreamhost.com/mimetex.cgi?G_2 liên thông http://www.forkosh.dreamhost.com/mimetex.cgi?%5CRightarrow giữa i, j có đường nối http://www.forkosh.dreamhost.com/mimetex.cgi?l_2 trong http://www.forkosh.dreamhost.com/mimetex.cgi?G_2
Xét:
Trường hợp 1: http://www.forkosh.dreamhost.com/mimetex.cgi?l_1 = http://www.forkosh.dreamhost.com/mimetex.cgi?l_2 http://www.forkosh.dreamhost.com/mimetex.cgi?%5CRightarrow i, j được nối với nhau trong http://www.forkosh.dreamhost.com/mimetex.cgi?G_3 (trái với giả sử phản chứng) (1)
Trường hợp 2: http://www.forkosh.dreamhost.com/mimetex.cgi?l_1 http://www.forkosh.dreamhost.com/mimetex.cgi?%5Cne http://www.forkosh.dreamhost.com/mimetex.cgi?l_2 http://www.forkosh.dreamhost.com/mimetex.cgi?%5CRightarrow Trong T, i, j được nối với nhau bằng 2 đường đi khác nhau trong T.
http://www.forkosh.dreamhost.com/mimetex.cgi?%5CRightarrow T có ít nhất 1 chu trình. (trái giả thiết T là cây). (2)
Từ (1) (2) http://www.forkosh.dreamhost.com/mimetex.cgi?%5CRightarrow http://www.forkosh.dreamhost.com/mimetex.cgi?G_3 liên thông. http://www.forkosh.dreamhost.com/mimetex.cgi?%5Cbox

link (http://www.toantin.org/forums/index.php?s=&showtopic=2796&view=findpost&p=21013)

[post ảnh]

Bài 11/Chương 1:
Đặt A là tập hợp người thỏa giả thiết đề bài. Với a, b http://www.forkosh.dreamhost.com/mimetex.cgi?\in A, ta ký hiệu:
a http://www.forkosh.dreamhost.com/mimetex.cgi?\sim b: a, b quen nhau
a http://www.forkosh.dreamhost.com/mimetex.cgi?\not\sim b: a, b không quen nhau
Theo kêt luận đề bài : có 1 người quen tất cả n-1 người còn lại. (Tức http://www.forkosh.dreamhost.com/mimetex.cgi?\existsahttp://www.forkosh.dreamhost.com/mimetex.cgi?\inA,ahttp://www.forkosh.dreamhost.com/mimetex.cgi?\simx,http://www.forkosh.dreamhost.com/mimetex.cgi?\forallxhttp://www.forkosh.dreamhost.com/mimetex.cgi?\inA,xhttp://www.forkosh.dreamhost.com/mimetex.cgi?\nea)
Giả thiết phản chứng: http://www.forkosh.dreamhost.com/mimetex.cgi?\forallahttp://www.forkosh.dreamhost.com/mimetex.cgi?\inA, http://www.forkosh.dreamhost.com/mimetex.cgi?\existshttp://www.forkosh.dreamhost.com/mimetex.cgi?\tilde{a}http://www.forkosh.dreamhost.com/mimetex.cgi?\inA, ahttp://www.forkosh.dreamhost.com/mimetex.cgi?\not\simhttp://www.forkosh.dreamhost.com/mimetex.cgi?\tilde{a}.
Với x, y http://www.forkosh.dreamhost.com/mimetex.cgi?\in A, x http://www.forkosh.dreamhost.com/mimetex.cgi?\ne y, ta xét :
Trường hợp 1: http://www.forkosh.dreamhost.com/mimetex.cgi?\tilde{x} http://www.forkosh.dreamhost.com/mimetex.cgi?\not\equiv http://www.forkosh.dreamhost.com/mimetex.cgi?\tilde{y}, xét 4 người x, y, http://www.forkosh.dreamhost.com/mimetex.cgi?\tilde{x}, http://www.forkosh.dreamhost.com/mimetex.cgi?\tilde{y} thì 4 người này mâu thuẫn đề bài. (1).
Trường hợp 2:http://www.forkosh.dreamhost.com/mimetex.cgi?\tilde{x} http://www.forkosh.dreamhost.com/mimetex.cgi?\equiv http://www.forkosh.dreamhost.com/mimetex.cgi?\tilde{y}, chọn z http://www.forkosh.dreamhost.com/mimetex.cgi?\in A, z http://www.forkosh.dreamhost.com/mimetex.cgi?\not\in {x, y, http://www.forkosh.dreamhost.com/mimetex.cgi?\tilde{x}} thì trong 4 người z, x, y, http://www.forkosh.dreamhost.com/mimetex.cgi?\tilde{x} chỉ có z là quen với cả 3 người x, y, http://www.forkosh.dreamhost.com/mimetex.cgi?\tilde{x}. Suy ra : z http://www.forkosh.dreamhost.com/mimetex.cgi?\sim http://www.forkosh.dreamhost.com/mimetex.cgi?\tilde{x}. Suy ra: http://www.forkosh.dreamhost.com/mimetex.cgi?\tilde{z}http://www.forkosh.dreamhost.com/mimetex.cgi?\ne http://www.forkosh.dreamhost.com/mimetex.cgi?\tilde{x}
Khi đó có 4 người không tthỏa đề bài là: x, http://www.forkosh.dreamhost.com/mimetex.cgi?\tilde{x}, z, http://www.forkosh.dreamhost.com/mimetex.cgi?\tilde{z}. (2)
Từ (1)(2) suy ra giả thiết phản chứng là sai.
http://www.forkosh.dreamhost.com/mimetex.cgi?\box

link (http://www.toantin.org/forums/index.php?s=&showtopic=2796&view=findpost&p=21005)

[post ảnh]

Bài 10\chương 2: G(X,E) đơn. CMR: G hoặc http://www.forkosh.dreamhost.com/mimetex.cgi?\bar{G} liên thông
Chứng minh:
Ta chỉ cần chứng minh nếu G không liên thông thì http://www.forkosh.dreamhost.com/mimetex.cgi?\bar{G} liên thông là xong.
Giả sử G không liên thông
http://www.forkosh.dreamhost.com/mimetex.cgi?\forall i, j http://www.forkosh.dreamhost.com/mimetex.cgi?\in X, i http://www.forkosh.dreamhost.com/mimetex.cgi?\ne j. Ta xét:
Trường hợp 1: i http://www.forkosh.dreamhost.com/mimetex.cgi?\not\sim j trong G.Suy ra: i http://www.forkosh.dreamhost.com/mimetex.cgi?\sim j trong http://www.forkosh.dreamhost.com/mimetex.cgi?\bar{G} (1).
Trường hợp 2: i http://www.forkosh.dreamhost.com/mimetex.cgi?\sim j trong G.
Do G không liên thông nên http://www.forkosh.dreamhost.com/mimetex.cgi?\exists k http://www.forkosh.dreamhost.com/mimetex.cgi?\in X sao cho i http://www.forkosh.dreamhost.com/mimetex.cgi?\not\sim k và k http://www.forkosh.dreamhost.com/mimetex.cgi?\not\sim j trong G.
i http://www.forkosh.dreamhost.com/mimetex.cgi?\not\sim k trong G. http://www.forkosh.dreamhost.com/mimetex.cgi?\Rightarrow i http://www.forkosh.dreamhost.com/mimetex.cgi?\sim k trong http://www.forkosh.dreamhost.com/mimetex.cgi?\tilde{G}.
k http://www.forkosh.dreamhost.com/mimetex.cgi?\not\sim j trong G. http://www.forkosh.dreamhost.com/mimetex.cgi?\Rightarrow k http://www.forkosh.dreamhost.com/mimetex.cgi?\sim j trong http://www.forkosh.dreamhost.com/mimetex.cgi?\bar{G}
Do quan hệ http://www.forkosh.dreamhost.com/mimetex.cgi?\sim có tính bắc cầu nên i http://www.forkosh.dreamhost.com/mimetex.cgi?\sim j trong http://www.forkosh.dreamhost.com/mimetex.cgi?\bar{G} (2)
(1)(2) http://www.forkosh.dreamhost.com/mimetex.cgi?\Rightarrow http://www.forkosh.dreamhost.com/mimetex.cgi?\bar{G} liên thông.
http://www.forkosh.dreamhost.com/mimetex.cgi?\box

link (http://www.toantin.org/forums/index.php?s=&showtopic=2796&view=findpost&p=21006)

[HoaCucVang]

Ghét nhất là cái vụ chứng minh liên thông này, híc híc. Môn Toán rời rạc đã khép lại hồi năm 2 hay 3 gì đó ai ngờ giờ phải lục tung lại để ôn vì thi đợt này có ngay một môn chình ình Toán Rời Rạc bên cạnh Tiếng Anh và môn Chuyên ngành. Cuộc đời sao mà tàn nhẫn với tui vầy nè trời híc híc....