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

post ảnh · 18-08-2008, 10:28 AM

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

Bài 19/Chương 3:

$G_1$ = ( $X_1$ , $E_1$ ), $G_2$ = ( $X_2$ , $E_2$ ), $G_1$ $\le$ T, $G_2$ $\le$ T, với T = (X,E) , $E_1$ $\cap$ $E_2$ $\ne$ $\oslash$ . $G_3$ = $G_1$ $\cap$ $G_2$ . CMR: $G_3$ liên thông.
Chứng minh:
Do $E_1$ $\cap$ $E_2$ $\ne$ $\oslash$ nên $X_1$ $\cap$ $X_2$ $\ne$ $\oslash$ .
Mà $G_3$ = $G_1$ $\cap$ $G_2$ = ( $X_1$ $\cap$ $X_2$ , $E_1$ $\cap$ $E_2$ ) là đồ thị.
Giả sử $G_3$ không liên thông.
$\exists$ i, j $\in$ $X_1$ $\cap$ $X_2$ , i $\not\sim$ j trong $G_3$ .
$\bullet$ i, j $\in$ $X_1$ , mà $G_1$ liên thông $\Rightarrow$ giữa i, j có đường nối $l_1$ trong $G_1$ .
$\bullet$ i, j $\in$ $X_2$ , mà $G_2$ liên thông $\Rightarrow$ giữa i, j có đường nối $l_2$ trong $G_2$
Xét:
Trường hợp 1: $l_1$ = $l_2$ $\Rightarrow$ i, j được nối với nhau trong $G_3$ (trái với giả sử phản chứng) (1)
Trường hợp 2: $l_1$ $\ne$ $l_2$ $\Rightarrow$ Trong T, i, j được nối với nhau bằng 2 đường đi khác nhau trong T.
$\Rightarrow$ T có ít nhất 1 chu trình. (trái giả thiết T là cây). (2)
Từ (1) (2) $\Rightarrow$ $G_3$ liên thông. $\box$

[Đăng nhập để xem liên kết. ]

post ảnh · 18-08-2008, 10:32 AM

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 $\in$ A, ta ký hiệu:
a $\sim$ b: a, b quen nhau
a $\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 $\exists$ a $\in$ A,a $\sim$ x, $\forall$ x $\in$ A,x $\ne$ a)
Giả thiết phản chứng: $\forall$ a $\in$ A, $\exists$ $\tilde{a}$ $\in$ A, a $\not\sim$ $\tilde{a}$ .
Với x, y $\in$ A, x $\ne$ y, ta xét :
Trường hợp 1: $\tilde{x}$ $\not\equiv$ $\tilde{y}$ , xét 4 người x, y, $\tilde{x}$ , $\tilde{y}$ thì 4 người này mâu thuẫn đề bài. (1).
Trường hợp 2: $\tilde{x}$ $\equiv$ $\tilde{y}$ , chọn z $\in$ A, z $\not\in$ {x, y, $\tilde{x}$ } thì trong 4 người z, x, y, $\tilde{x}$ chỉ có z là quen với cả 3 người x, y, $\tilde{x}$ . Suy ra : z $\sim$ $\tilde{x}$ . Suy ra: $\tilde{z}$ $\ne$ $\tilde{x}$
Khi đó có 4 người không tthỏa đề bài là: x, $\tilde{x}$ , z, $\tilde{z}$ . (2)
Từ (1)(2) suy ra giả thiết phản chứng là sai.
$\box$

[Đăng nhập để xem liên kết. ]

post ảnh · 18-08-2008, 10:33 AM

Bài 10\chương 2: G(X,E) đơn. CMR: G hoặc $\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ì $\bar{G}$ liên thông là xong.
Giả sử G không liên thông
$\forall$ i, j $\in$ X, i $\ne$ j. Ta xét:
Trường hợp 1: i $\not\sim$ j trong G.Suy ra: i $\sim$ j trong $\bar{G}$ (1).
Trường hợp 2: i $\sim$ j trong G.
Do G không liên thông nên $\exists$ k $\in$ X sao cho i $\not\sim$ k và k $\not\sim$ j trong G.
i $\not\sim$ k trong G. $\Rightarrow$ i $\sim$ k trong $\tilde{G}$ .
k $\not\sim$ j trong G. $\Rightarrow$ k $\sim$ j trong $\bar{G}$
Do quan hệ $\sim$ có tính bắc cầu nên i $\sim$ j trong $\bar{G}$ (2)
(1)(2) $\Rightarrow$ $\bar{G}$ liên thông.
$\box$

[Đăng nhập để xem liên kết. ]

HoaCucVang · 20-08-2008, 04:01 PM

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....