Diễn Đàn MathScope - Xem bài viết đơn - Kỳ thi chọn HSGQG môn Toán 2015

**quocbaoct10** · 10-01-2015, 11:15 AM

Bài 7:
a) xét đồ thị lưỡng phân $G(M,N,E)$ trong đó $M$ là tập đỉnh biểu diễn học sinh nam và $N$ là tập đỉnh biểu diễn học sinh nư. ta có $|M|=m$ và $|N|=n$.
Theo điều kiện của đề, ta thấy mỗi đỉnh tử $M$ được nối với ít nhất một đỉnh ở $N$ và ngược lại. Một buổi diễn phụ thuộc vào học sinh nam $i$ (nữ tương tự) nghĩa là trong đồ thị lưỡng phân $G(M,N,E)$ thì trong tập các đỉnh nối với đỉnh $i$ phải có ít nhất một đỉnh $n_{i_k}$ có $deg (n_{i_k}) = 1$, giả sử có $k$ đỉnh như vậy. Bỏ đi các đỉnh $n_{i_k}$ có $deg=1$ và đỉnh $i$, ta sẽ được đồ thị $G(M',N',E')$ mà trong đó $|M'|=m-1$ và $|N'|=n-k$.Sau khi xóa đi $k$ cạnh, số cạnh còn lại có thể chẵn hoặc lẻ. Với trường hợp chẵn, nếu trong tập $M'$ không có đỉnh $m_t$ nào có $deg(m_t)=n-k$ thì ta có thể chọn một số lẻ đỉnh và nối đỉnh đó đến một đỉnh khác trong tập $N'$, khi đó sẽ được một số đỉnh lẻ. như vậy có $O=\binom{n-1}{1}+\binom{n-1}{3}+\binom{n-1}{5}+ ...$. Tương tự đó với việc chọn số chẵn đỉnh để được số cạnh chẵn, ta có $E=\binom{n-1}{0}+\binom{n-1}{2}+...$. Dễ thấy $O=E$ nên suy ra số tập cạnh chẵn sẽ bằng số tập cạnh lẻ. Tương tự với trường hợp phần còn lại là tập cạnh lẻ. Nếu có ít nhất 1 đỉnh trong $M'$ có $deg=n-k$, ta bỏ đi qua các đỉnh này và chọn tương tự cho phần các đỉnh còn lại. Như vậy, từ đấy ta luôn có điều phải chứng minh.
b). Gọi $O(m,n)$ là số đồ thị $G(M,N,E)$ có số cạnh lẻ, $E(m,n)$ là số đồ thị có số cạnh chẵn, khi đó xét một điểm $i \in M$, nếu đồ thị G bị phụ thuộc $i$ thì dựa vào câu a) sẽ có số đồ thị có số cạnh chẵn và số đồ thị có số cạnh lẻ là bằng nhau (*). Với những đồ thị không phụ thuộc vào $i$, khi bỏ i, ta sẽ được số đồ thị có chẵn cạnh là $E(m-1,n)$ và số đồ thị có lẻ cạnh là $O(m-1,n)$. Nếu $i$ có số $deg(i)=2k+1$ thì từ số đồ thị có số chẵn cạnh $E(m,n)$ ta sẽ có được số đồ thị có số lẻ cạnh $k.O(m-1,n)$, tương tự với $O(m,n)$ (1). Khi với $deg(i)=2k+2 > 0$ thì từ số đồ thị có cạnh chẵn $E(m,n)$ ta nhận được số đồ thị có cạnh chẵn là $(k-1)E(m-1,n)$ và tương tự với số đồ thị có cạnh lẻ (2) (sở dĩ được $k-1$ vì ta không xét đến trường hợp $deg(i)=0$ cũng là một số chẵn).
Từ (1) và (2) và (*) ta được: $E(m,n)-O(m,n)=O(m-1,n)-E(m-1,n)=...=(-1)^m(E(1,n)-O(1,n))=(-1)^m$.
Vì vậy số đồ thị có số cạnh chẵn không chênh lệch với số đồ thị có số lẻ cạnh quá 1 đơn vị, nên có thể sắp xếp xen kẽ các đô thị có số cạnh chẵn và các đồ thị có số cạnh lẻ với nhau.
.

10-01-2015, 11:15 AM	#68
quocbaoct10 +Thành Viên Danh Dự+ Tham gia ngày: Oct 2012 Đến từ: THPT chuyên Lê Quý Đôn-Nha Trang-Khánh Hòa Bài gởi: 539 Thanks: 292 Thanked 365 Times in 217 Posts	Bài 7: a) xét đồ thị lưỡng phân $G(M,N,E)$ trong đó $M$ là tập đỉnh biểu diễn học sinh nam và $N$ là tập đỉnh biểu diễn học sinh nư. ta có $\|M\|=m$ và $\|N\|=n$. Theo điều kiện của đề, ta thấy mỗi đỉnh tử $M$ được nối với ít nhất một đỉnh ở $N$ và ngược lại. Một buổi diễn phụ thuộc vào học sinh nam $i$ (nữ tương tự) nghĩa là trong đồ thị lưỡng phân $G(M,N,E)$ thì trong tập các đỉnh nối với đỉnh $i$ phải có ít nhất một đỉnh $n_{i_k}$ có $deg (n_{i_k}) = 1$, giả sử có $k$ đỉnh như vậy. Bỏ đi các đỉnh $n_{i_k}$ có $deg=1$ và đỉnh $i$, ta sẽ được đồ thị $G(M',N',E')$ mà trong đó $\|M'\|=m-1$ và $\|N'\|=n-k$.Sau khi xóa đi $k$ cạnh, số cạnh còn lại có thể chẵn hoặc lẻ. Với trường hợp chẵn, nếu trong tập $M'$ không có đỉnh $m_t$ nào có $deg(m_t)=n-k$ thì ta có thể chọn một số lẻ đỉnh và nối đỉnh đó đến một đỉnh khác trong tập $N'$, khi đó sẽ được một số đỉnh lẻ. như vậy có $O=\binom{n-1}{1}+\binom{n-1}{3}+\binom{n-1}{5}+ ...$. Tương tự đó với việc chọn số chẵn đỉnh để được số cạnh chẵn, ta có $E=\binom{n-1}{0}+\binom{n-1}{2}+...$. Dễ thấy $O=E$ nên suy ra số tập cạnh chẵn sẽ bằng số tập cạnh lẻ. Tương tự với trường hợp phần còn lại là tập cạnh lẻ. Nếu có ít nhất 1 đỉnh trong $M'$ có $deg=n-k$, ta bỏ đi qua các đỉnh này và chọn tương tự cho phần các đỉnh còn lại. Như vậy, từ đấy ta luôn có điều phải chứng minh. b). Gọi $O(m,n)$ là số đồ thị $G(M,N,E)$ có số cạnh lẻ, $E(m,n)$ là số đồ thị có số cạnh chẵn, khi đó xét một điểm $i \in M$, nếu đồ thị G bị phụ thuộc $i$ thì dựa vào câu a) sẽ có số đồ thị có số cạnh chẵn và số đồ thị có số cạnh lẻ là bằng nhau (). Với những đồ thị không phụ thuộc vào $i$, khi bỏ i, ta sẽ được số đồ thị có chẵn cạnh là $E(m-1,n)$ và số đồ thị có lẻ cạnh là $O(m-1,n)$. Nếu $i$ có số $deg(i)=2k+1$ thì từ số đồ thị có số chẵn cạnh $E(m,n)$ ta sẽ có được số đồ thị có số lẻ cạnh $k.O(m-1,n)$, tương tự với $O(m,n)$ (1). Khi với $deg(i)=2k+2 > 0$ thì từ số đồ thị có cạnh chẵn $E(m,n)$ ta nhận được số đồ thị có cạnh chẵn là $(k-1)E(m-1,n)$ và tương tự với số đồ thị có cạnh lẻ (2) (sở dĩ được $k-1$ vì ta không xét đến trường hợp $deg(i)=0$ cũng là một số chẵn). Từ (1) và (2) và () ta được: $E(m,n)-O(m,n)=O(m-1,n)-E(m-1,n)=...=(-1)^m(E(1,n)-O(1,n))=(-1)^m$. Vì vậy số đồ thị có số cạnh chẵn không chênh lệch với số đồ thị có số lẻ cạnh quá 1 đơn vị, nên có thể sắp xếp xen kẽ các đô thị có số cạnh chẵn và các đồ thị có số cạnh lẻ với nhau. Bài này bỏ câu a thì vui hơn nhiều nhỉ . __________________ i'll try my best. thay đổi nội dung bởi: quocbaoct10, 10-01-2015 lúc 11:54 AM