09HCB

Trang chủ 09HCB- Lớp Hoàn Chỉnh Đại Học Khoá 2009-2011
 
Trang ChínhTrang Chính  GalleryGallery  Tìm kiếmTìm kiếm  Đăng kýĐăng ký  Đăng NhậpĐăng Nhập  

Share
 

 Giải bài tập 8 - slide 1

Go down 
Tác giảThông điệp
Admin
Admin
Admin

Tổng số bài gửi : 149
Join date : 15/03/2010

Giải bài tập 8 - slide 1 Empty
Bài gửiTiêu đề: Giải bài tập 8 - slide 1   Giải bài tập 8 - slide 1 Empty16/3/2010, 11:07 am

Đề bài: Cho G là đồ thị vô hướng liên thông. Giả sử C1 và C2 là 2 dây chuyền sơ cấp trong G có số cạnh nhiều nhất.
Chứng minh C1 và C2 có đỉnh chung.


Giả sử C1 và C2 không có đỉnh chung.
C1 có L1 cạnh, C2 có L2 cạnh. Gọi C1 là dây chuyền có số cạnh lớn nhất(L1>=L2).
C1 có đỉnh đầu là u1, đỉnh cuối là u2, C2 có đỉnh đầu là v1, đỉnh cuối là v2.
Lấy 1 đỉnh u bất kỳ trên C1 và 1 đỉnh v bất kỳ trên C2
Do G liên thông nên giữa 2 đỉnh u và v tồn tại 1 dây chuyền là d(số cạnh trong d>=1).
Các đỉnh d co 2 trường hợp có thể xảy ra là:
-TH1: trong d không có bất kỳ đỉnh nào có trong C1 và C2.
Giữa u và u1 có 1 dây chuyền là d11, giữa u và u2 có 1 dây chuyền là d12,
trong 2 dây chuyền này chọn dây chuyền có số cạnh dài hơn, gọi dây chuyền này là d1, và "số cạnh d11" + "số cạnh d12"=L1
suy ra số cạnh d1 >= L1/2.
Tương tự trong C2 ta có dây chuyền d2 có số cạnh >= L2/2.
Khi đó tồn tại dây chuyền sơ cấp d1dd2 có số cạnh là: số cạnh trong d1 + số cạnh trong d + số cạnh trong d2
>= L1/2 + L2/2 + số cạnh trong d
>= L2/2 + L2/2 + số cạnh trong d(do L1>=L2)
>= L2 + số cạnh trong d > L2(do số cạnh trong d >=1)
Đây là điều vô lý bới số cạnh trong dây chuyền sơ cấp d1dd2 lớn hơn số cạnh trong C2, tức là C2 không là 1 trong 2 dây chuyền có số cạnh lớn nhất(mâu thuẫn với đề bài).
-TH2: còn lại (trong d có chứa một số đỉnh có trong C1,C2).
Xét dây chuyền udv, từ u đi đến đỉnh kế tiếp đến khi nào gặp đỉnh v' thuộc C2. Sau đó, cũng trong d, từ v' ta đi ngược trở lại đến khi nào gặp đỉnh u' thuộc C1.
Khi đó dây chuyền giữa u' và v' này(thuộc udv) không chứa bất kỳ đỉnh nào có trong C1 và C2 => đưa về TH1.


===End[i]
Về Đầu Trang Go down
https://09hcb.forumvi.com
 
Giải bài tập 8 - slide 1
Về Đầu Trang 
Trang 1 trong tổng số 1 trang

Permissions in this forum:Bạn không có quyền trả lời bài viết
09HCB :: Lưu trữ :: HK1 :: LTDT-
Chuyển đến