Chủ đề này có 3 trả lời

[DinhCuongTk14]

Cho đồ thị G liên thông và có tối thiểu 1 đỉnh bậc lẻ .Cmr có thể tô các cạnh của G bới 2 màu X,D mà với mỗi đỉnh bất kì của G thì số cạnh xanh và đỏ xuất phát từ đỉnh đó chênh nhau không quá 1

[tanlsth]

Sử dụng đường 1 nét Ơle và sử dụng phép thêm bớt các cạnh ta có điều phải chứng minh
Cụ thể
Gọi $ A_1,A_2,..,A_k $ là các đỉnh bậc lẻ suy ra $ k \vdots 2 $
Chia các đỉnh $ A_i $ này thành $ \dfrac{k}{2} $ cặp
Thêm 1 cạnh vào mỗi cặp thì mỗi đỉnh của đò thị mới thu được đều có bậc chẵn
Từ đó tồn tại đường 1 nét Ơle rồi ta tô màu đan xen theo đường đó ta có điều phải chứng minh

Bài viết đã được chỉnh sửa nội dung bởi tanlsth: 01-04-2007 - 12:31

[vnm]

nếu bạn thêm như vậy có thể có 1 cặp đỉnh đã nối với nhau
Có thể thêm 1 đỉnh vào đồ thị và nối tất cả các đỉnh bậc lẻ với nó

[tanlsth]

Tớ thêm như vậy thì mỗi đỉnh lẻ chỉ có đúng 1 cạnh được thêm thôi,vẫn thỏa mãn