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

**Traum** · 20-12-2007, 06:46 PM

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 $

20-12-2007, 06:46 PM	#2
Traum 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ơ.