grahp Trong một buổi dạ hội, mỗi người tham dự đều có ít nhất 3 người bạn, cmr có thể chọn ra 1 số chẵn người để xếp ngồi quanh một bàn tròn sao cho mỗi người đều ngồi giữa 2 người quen. |
Bài toán tổng quát của bài toán này là: Trong một đồ thị mà có $\ge \frac{3n}{2} $ cạnh thì có ít nhất một chu kì độ dài chẵn. Dùng nó có thể giải được bài graph của VMEO III. Chứng minh: Trước hết ta chỉ cần chứng minh cho đồ thị liên thông. Nhận xét 1: Nếu có hai chu trình có chung cạnh thì tồn tại chu trình chẵn. Nhận xét 2: Từ một cây, thêm một cạnh bất kì thì có thêm một chu trình. Giả sử T là cây cơ bản của đồ thị G, Giả sử G không có chu trình đồ dài chẵn. Ta có khi thêm cho T một cạnh bất kì thì số chu trình trong G tăng lên 1, mà ta có không có 2 chu trình nào có chung cạnh và mỗi chu trình có độ dài ít nhất là 3, do đó số cạnh thêm vào không lớn hơn $n-1/2 $, hay tổng số cạnh của đồ thị không lớn hơn $3(n-1)/2 $ |
Múi giờ GMT. Hiện tại là 12:19 PM. |
Powered by: vBulletin Copyright ©2000-2024, Jelsoft Enterprises Ltd.