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