Diễn Đàn MathScope - Xem bài viết đơn

theunknown · 02-03-2018, 10:03 PM

Bài 3 đề 4 ngày 1:

Ta phát biểu lại bài toán dưới dạng đồ thị (Graph) như sau: Xét một Graph $G$ có $40$ đỉnh và $80$ cạnh. Tìm $n$ lớn nhất để luôn tồn tại một tập độc lập có $n$ đỉnh. ( Một tập độc lập là tập các đỉnh mà hai đỉnh bất kì không có cạnh nối).
Ta phát biểu bổ đề sau: (Caro-Wei) Xét graph $G$ có bậc các đỉnh lần lượt là $d_1,d_2,...,d_n$. Khi đó tồn tại một tập độc lập có không ít hơn $\sum_{i=1}^{n}\frac{1}{d_i+1}$.

Ta quay lại bài toán trước: Ta dễ thấy rằng

$d_1+d_2+...d_{40}=2*80=160$

Áp dụng bất đẳng thức Cauchy-Schwarz ta có:

$\sum_{i=1}^{40}\frac{1}{d_i+1}\geq \frac{40^2}{\sum_{i=1}^{40}d_i+40}=8$

Theo bổ đề thì tồn tại một tập độc lập có không ít hơn $8$ đỉnh. Ta sẽ chỉ ra rằng $n=8$ là giá trị nhỏ nhất cần tìm.
Một ví dụ cho một Graph có các tập độc lập có số đỉnh không vượt quá $8$ là: Ta chia $40$ đỉnh thành $5$ tập, mỗi tập $8$ đỉnh. Ta đánh dấu mỗi đỉnh trong từng tập bằng các số từ $1$ đến $8$. Giữa hai đỉnh nằm trong cùng một tập ta sẽ không nối cạnh nào và giữa các đỉnh của hai tập khác nhau ta nối đúng $8$ cạnh sao cho hai đỉnh khác nhau được nối khi và chỉ khi chúng có cùng chỉ số được đánh dấu. Dễ thấy cách nối này thỏa mãn một Graph có $n=8$ (thật vậy nếu tồn tại tập độc lập gồm $9$ đỉnh thì tồn tại hai đỉnh cùng được đánh dấu một số và như trên ta thấy vô lý) và số cạnh là $8\binom{5}{2}=80$.

$\blacksquare$

Quay lại bổ đề thì đây là một bổ đề có nhiều cách chứng minh (cách thường dùng nhất là phương pháp xác suất ). Em xin nêu ngắn gọn cách chứng minh như sau:
Ta xét một hoán vị ngấu nhiên của tập các đỉnh của $G$ là $\omega$ với xác suất bằng nhau và bằng $\frac{1}{n!}$. Ta xét sự kiện $A_i$: $\omega(i)<\omega(j)$ với tất cả đỉnh $j$ kề với $i$. Bằng cách đếm ta dễ dàng chứng minh được xác suất của sự kiện này là $\frac{1}{d_i+1}$. Ta để ý rằng nếu một hoán vị đều xảy ra hai sự kiện $A_i,A_j$ với $i\neq j$ thì đỉnh $i$ không thể kề với đỉnh $j$.
Xét biến ngẫu nhiên rời rạc $X$ được tính bằng số các sự kiện $A_i$ mà một hoán vị có thể gặp phải. Ta có:

$E[X]=\sum_{i=1}^{n}P(A_i)=\sum_{i=1}^{n}\frac{1}{d_i+1 }$

Do đó tồn tại một hoán vị $\omega$ có không ít hơn $\sum_{i=1}^{n}\frac{1}{d_i+1}$ sự kiện. Theo nhận xét trên bổ đề được chứng minh.

02-03-2018, 10:03 PM	#35
theunknown +Thành Viên+ Tham gia ngày: Jan 2017 Bài gởi: 5 Thanks: 0 Thanked 5 Times in 2 Posts	Bài 3 đề 4 ngày 1: Ta phát biểu lại bài toán dưới dạng đồ thị (Graph) như sau: Xét một Graph $G$ có $40$ đỉnh và $80$ cạnh. Tìm $n$ lớn nhất để luôn tồn tại một tập độc lập có $n$ đỉnh. ( Một tập độc lập là tập các đỉnh mà hai đỉnh bất kì không có cạnh nối). Ta phát biểu bổ đề sau: (Caro-Wei) Xét graph $G$ có bậc các đỉnh lần lượt là $d_1,d_2,...,d_n$. Khi đó tồn tại một tập độc lập có không ít hơn $\sum_{i=1}^{n}\frac{1}{d_i+1}$. Ta quay lại bài toán trước: Ta dễ thấy rằng $d_1+d_2+...d_{40}=280=160$ Áp dụng bất đẳng thức Cauchy-Schwarz ta có: $\sum_{i=1}^{40}\frac{1}{d_i+1}\geq \frac{40^2}{\sum_{i=1}^{40}d_i+40}=8$ Theo bổ đề thì tồn tại một tập độc lập có không ít hơn $8$ đỉnh. Ta sẽ chỉ ra rằng $n=8$ là giá trị nhỏ nhất cần tìm. Một ví dụ cho một Graph có các tập độc lập có số đỉnh không vượt quá $8$ là: Ta chia $40$ đỉnh thành $5$ tập, mỗi tập $8$ đỉnh. Ta đánh dấu mỗi đỉnh trong từng tập bằng các số từ $1$ đến $8$. Giữa hai đỉnh nằm trong cùng một tập ta sẽ không nối cạnh nào và giữa các đỉnh của hai tập khác nhau ta nối đúng $8$ cạnh sao cho hai đỉnh khác nhau được nối khi và chỉ khi chúng có cùng chỉ số được đánh dấu. Dễ thấy cách nối này thỏa mãn một Graph có $n=8$ (thật vậy nếu tồn tại tập độc lập gồm $9$ đỉnh thì tồn tại hai đỉnh cùng được đánh dấu một số và như trên ta thấy vô lý) và số cạnh là $8\binom{5}{2}=80$. $\blacksquare$ Quay lại bổ đề thì đây là một bổ đề có nhiều cách chứng minh (cách thường dùng nhất là phương pháp xác suất ). Em xin nêu ngắn gọn cách chứng minh như sau: Ta xét một hoán vị ngấu nhiên của tập các đỉnh của $G$ là $\omega$ với xác suất bằng nhau và bằng $\frac{1}{n!}$. Ta xét sự kiện $A_i$: $\omega(i)<\omega(j)$ với tất cả đỉnh $j$ kề với $i$. Bằng cách đếm ta dễ dàng chứng minh được xác suất của sự kiện này là $\frac{1}{d_i+1}$. Ta để ý rằng nếu một hoán vị đều xảy ra hai sự kiện $A_i,A_j$ với $i\neq j$ thì đỉnh $i$ không thể kề với đỉnh $j$. Xét biến ngẫu nhiên rời rạc $X$ được tính bằng số các sự kiện $A_i$ mà một hoán vị có thể gặp phải. Ta có: $E[X]=\sum_{i=1}^{n}P(A_i)=\sum_{i=1}^{n}\frac{1}{d_i+1 }$ Do đó tồn tại một hoán vị $\omega$ có không ít hơn $\sum_{i=1}^{n}\frac{1}{d_i+1}$ sự kiện. Theo nhận xét trên bổ đề được chứng minh. thay đổi nội dung bởi: theunknown, 03-03-2018 lúc 07:41 AM*