|
|
|
Ngoài một số quy định đã được nêu trong phần Quy định của Ghi Danh , mọi người tranh thủ bỏ ra 5 phút để đọc thêm một số Quy định sau để khỏi bị treo nick ở MathScope nhé ! * Quy định về việc viết bài trong diễn đàn MathScope * Nếu bạn muốn gia nhập đội ngũ BQT thì vui lòng tham gia tại đây |
| Ðiều Chỉnh | Xếp Bài |
|
18-12-2007, 08:02 PM | #1 |
+Thành Viên+ | 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. |
20-12-2007, 06:46 PM | #2 |
Moderator Tham gia ngày: Nov 2007 Đến từ: cyber world Bài gởi: 413 Thanks: 14 Thanked 466 Times in 171 Posts | 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 $ __________________ Traum is giấc mơ. |
Bookmarks |
|
|