Problem 3
#1
Đã gửi 25-07-2007 - 18:55
#2
Đã gửi 26-07-2007 - 08:43
Cho đồ thị có chứa $ K_t $ lớn nhất là $ t=2n $
Chứng minh có thể phân hoạch đồ tị đó thành 2 đồ thị con thỏa mãn $ K_m $ lớn nhất trong 2 đồ thị con bằng nhau
Chứng minh bằng cách xét cách phân chia có sự chênh lệch $ K_m $ giữa 2 đồ thị nhỏ nhất.
Nhận xét nó không thể lớn hơn hoặc bằng $2 $ do đó nó phải bằng $1 $
Xét cách chuyển các đỉnh ta chứng minh được đồ thị đầy đủ lớn nhất trong $G $ chính là $ K_{2p+1}$ với $ p \geq n $
Từ đó ta có điều phải chứng minh
Bài viết đã được chỉnh sửa nội dung bởi tanlsth: 26-07-2007 - 08:44
Learn from yesterday,live for today,hope for tomorrow
The important thing is to not stop questioning
#3
Đã gửi 26-07-2007 - 08:47
Xét G là clique dài nhất và có 2k người
Ngoài G ta xét H là clique dài thứ 2 và ko là clique con của G, đồng thời nó có ít người chung với G nhất
Ta cho tất cả những người trong H vào phòng B và tất cả nhg người còn lại vào phòng A
Giả sử G,H có chung j người và H có i người thì clique G trong phòng A còn lại 2k-j người và biến thành Clique G'
TH1: $2k-j \geq i$
ta dễ thấy là chuyển người từ clique G' sang phòng B ko làm đổi số ng' trong độ dài clique max của phòng B, nên ta cứ chuyển đến khi nào clique G' biến hành G'' có i người. Dễ thấy phòng A, B đều có đội dài clique max là i( vì nếu tồn tại 1 clique dài hơn sẽ trái với định nghĩa của H)
TH2: $2k-j \leq i$
TH này ta xét tất cả các clique ơe phòng A
$ G_{1}, G_{2},... G{n} $, các clique này có độ dài tối đa là i theo định nghĩa của H
ta gọi $ H_{j} $ là tập người trong phòng B có thể gắn thêm vào clique $G_{j}$ để tạo ra clique dài hơn
Dễ thấy cứ 1 lần chuyển 1 người từ B sang A thì độ dài clique bên phòng B giảm đi 1, còn các clique bên phòng A tăng độ dài lên không quá 1. Từ các tập $ H_{i} $ và độ dài các $ G_{j} $ ta chọn được 1 số người trong phòng B sao cho khi chuyển xong độ dài clique max trong A bằng hoặc kém hơn độ dài clique trong B là 1( dễ thấy ít nhất có clique G' thực hiện được điều này), và chọn số người sao cho ít nhất . Ta chỉ cần xét TH kém 1.Xét các clique dài nhất trong A. Nếu có 1 ng' trong B ko thể nhóm với bất kì clique nào trong đó thì chuyển sang phòng A-xong. Nếu ko ta chuyển 1 ng' bất kì từ B sang A. Chọn tất cả các clique có m+1 ng' lúc này trong A. Ta thấy có thể chọn 1 ng' trong mỗi clique trên chuyển sang B đẻ đọ dại clique bên đó ko đổi( Nếu ko sẽ tạo ra 1 clique dài hơn H và nhỏ hơn G vô lý)
Vậy bài toán được CM
Bài viết đã được chỉnh sửa nội dung bởi ThangTongHop: 26-07-2007 - 22:11
#4
Đã gửi 26-07-2007 - 08:59
Vì ở ngay trường hợp đầu tiên thì khi em chuyển từ $ A $ sang $ B $ thì biết đâu có 1 nhóm người nào đó tạo với số người chuyển này một $ K_t $ với $ t>i $ thì sao vì như em nói thì có thể vẫn có nhiều clique chung với $ G $ mà
Learn from yesterday,live for today,hope for tomorrow
The important thing is to not stop questioning
#5
Đã gửi 26-07-2007 - 10:51
#6
Đã gửi 26-07-2007 - 16:47
Learn from yesterday,live for today,hope for tomorrow
The important thing is to not stop questioning
#7
Đã gửi 26-07-2007 - 21:25
Bài viết đã được chỉnh sửa nội dung bởi ThangTongHop: 26-07-2007 - 21:46
#8
Đã gửi 26-07-2007 - 21:48
Nhờ mọi người vào check hộ một cái,mình chưa có thời gian xem cái trường hợp 2
Learn from yesterday,live for today,hope for tomorrow
The important thing is to not stop questioning
#9
Đã gửi 27-07-2007 - 21:37
Ta chọn 1 clique bất kì của A và ta cho ng' từ B sang A cho đến khi ko thể được hoặc đạt maxB-maxA=1
Gọi $S_{i}$ là số ng' cần chuyển ít nhất từ B->A vào clique i của A để có thể đạt trạng thái maxB-maxA=1 (với điều kiện clique này có thể thực hiện được như vậy)
Ta chọn số $S_{i}$ min=n và chuyển ngần ấy ng' của A vào clique i, ta có trạng thái maxB-maxA=1
Lúc này xét 1 trong các clique có độ dài bằng maxA
- Nếu clique đó nhận ít hơn n người ( trước khi x được chuyển) thì nghĩa là nó ko thể nhận thêm ng' từ B( vì nếu ko thì chỉ cần $S_{i}$ ng' được chuyển là ta có maxB=maxA)
Ta chuyển 1 ng' bất kì x từ B -> A. Nếu lúc này maxB=maxA, bài toán xong, còn nếu maxA-maxB=1
Xét các clique có độ dài maxA
- clique đó nhận đúng n+1 người( do lý luận trên) ta chọn 1 ng' bất kì từ clique đó( khác nhg ng' bị chuyển) chuyển sang B
Sau những động tác trên ta thấy maxA giảm 1( do các clique max mất 1 ng') còn maxB ko đổi( vì nếu trong B có 1 clique>maxA thì ghép thêm n+1 ng' đã chuyển vào sẽ tạo ra 1 clique có độ dài >i và khác 2k ), do đó bài toán xong
Bài viết đã được chỉnh sửa nội dung bởi ThangTongHop: 30-07-2007 - 00:32
#10
Đã gửi 28-07-2007 - 17:29
Đồ thị gồm $ 2 K_4 $ giao nhau tại một đỉnh $ A $
Khi đó $ 2k-j=i $ và chuyển đỉnh như em thì sau khi chuyển đỉnh $ A $ sang thì lại có một bên là $ K_3 $ và một bên là $ K_4 $ không đúng như em nói
Rõ ràng là cách chuyển đỉnh của em có vấn đề ở việc chuyển đỉnh nào và thứ tự như thế nào vì còn phụ thuộc vào tính chất của đỉnh nữa
Bài viết đã được chỉnh sửa nội dung bởi tanlsth: 28-07-2007 - 18:21
Learn from yesterday,live for today,hope for tomorrow
The important thing is to not stop questioning
#11
Đã gửi 28-07-2007 - 18:08
#12
Đã gửi 30-07-2007 - 14:06
Em post thử mấy ý này xem có được hok
Xét G là clique dài nhất và có 2k người
Ngoài G ta xét H là clique dài thứ 2 và ko là clique con của G, đồng thời nó có ít người chung với G nhất
Ta cho tất cả những người trong H vào phòng B và tất cả nhg người còn lại vào phòng A
Giả sử G,H có chung j người và H có i người thì clique G trong phòng A còn lại 2k-j người và biến thành Clique G'
TH1: $2k-j \geq i$
ta dễ thấy là chuyển người từ clique G' sang phòng B ko làm đổi số ng' trong độ dài clique max của phòng B, nên ta cứ chuyển đến khi nào clique G' biến hành G'' có i người. Dễ thấy phòng A, B đều có đội dài clique max là i( vì nếu tồn tại 1 clique dài hơn sẽ trái với định nghĩa của H)
TH2: $2k-j \leq i$
TH này ta xét tất cả các clique ơe phòng A
$ G_{1}, G_{2},... G{n} $, các clique này có độ dài tối đa là i theo định nghĩa của H
ta gọi $ H_{j} $ là tập người trong phòng B có thể gắn thêm vào clique $G_{j}$ để tạo ra clique dài hơn
Dễ thấy cứ 1 lần chuyển 1 người từ B sang A thì độ dài clique bên phòng B giảm đi 1, còn các clique bên phòng A tăng độ dài lên không quá 1. Từ các tập $ H_{i} $ và độ dài các $ G_{j} $ ta chọn được 1 số người trong phòng B sao cho khi chuyển xong độ dài clique max trong A bằng hoặc kém hơn độ dài clique trong B là 1( dễ thấy ít nhất có clique G' thực hiện được điều này), và chọn số người sao cho ít nhất . Ta chỉ cần xét TH kém 1.Xét các clique dài nhất trong A. Nếu có 1 ng' trong B ko thể nhóm với bất kì clique nào trong đó thì chuyển sang phòng A-xong. Nếu ko ta chuyển 1 ng' bất kì từ B sang A. Chọn tất cả các clique có m+1 ng' lúc này trong A. Ta thấy có thể chọn 1 ng' trong mỗi clique trên chuyển sang B đẻ đọ dại clique bên đó ko đổi( Nếu ko sẽ tạo ra 1 clique dài hơn H và nhỏ hơn G vô lý)
Vậy bài toán được CM
Tôi không hiểu tại sao trong trường hợp cuối cùng lại kết luận đc là độ dài lớn nhất bên B không đổi. Trong quá trình chuyển đổi sao cho max A = max B - 1, có thể max B lúc này đã là khá nhỏ (giả sử i = 2l+1 thì sau khi chuyển nốt một người nữa sang B có thể max B lúc này chỉ là l). Và nếu chuyển một số người bên A (lúc này max A = l+1) quay lại bên B mà tạo nên clique to hơn thì kết hợp với những ai (bên A) để tạo thành clique dài hơn H?
Có lẽ bạn cần giải thích cặn kẽ hơn điểm cuối cùng (làm một số tính toán). Theo marking scheme mà tôi may mắn được nhìn thấy thì đây chính là điểm mấu chốt của lời giải. Hình như bạn cũng chưa dùng giả thuyết rằng độ dài lớn nhất của clique trong đồ thị là chẵn
#13
Đã gửi 30-07-2007 - 15:16
Ngày xưa ghét nhất làm bài đồ thị cứ phải chuyển chuyển thế này, có cách nào có cái trick gì bất ngờ không anh CXR ?Tôi không hiểu tại sao trong trường hợp cuối cùng lại kết luận đc là độ dài lớn nhất bên B không đổi. Trong quá trình chuyển đổi sao cho max A = max B - 1, có thể max B lúc này đã là khá nhỏ (giả sử i = 2l+1 thì sau khi chuyển nốt một người nữa sang B có thể max B lúc này chỉ là l). Và nếu chuyển một số người bên A (lúc này max A = l+1) quay lại bên B mà tạo nên clique to hơn thì kết hợp với những ai (bên A) để tạo thành clique dài hơn H?
Có lẽ bạn cần giải thích cặn kẽ hơn điểm cuối cùng (làm một số tính toán). Theo marking scheme mà tôi may mắn được nhìn thấy thì đây chính là điểm mấu chốt của lời giải. Hình như bạn cũng chưa dùng giả thuyết rằng độ dài lớn nhất của clique trong đồ thị là chẵn
#14
Đã gửi 30-07-2007 - 21:07
#15
Đã gửi 30-07-2007 - 21:33
Ngày xưa ghét nhất làm bài đồ thị cứ phải chuyển chuyển thế này, có cách nào có cái trick gì bất ngờ không anh CXR ?
Bài này có thể dùng phản chứng để làm đơn giản một số bước chuyển - Sau khi đưa về trường hợp max clique size của 2 phòng chênh nhau không quá một thì chỉ cần thêm 2 bước chuyển nữa là xong. Có một vài lời giải xuất hiện ở nhiều hình thức khác nhau .. nhưng chung quy lại vẫn là xét các trường hợp rồi chuyển - cho đến giờ anh chưa thấy một lời giải trực tiếp nào cả. Cái khó chính là ở chỗ vận dụng được tính chẵn lẻ của max clique size.
#16
Đã gửi 31-07-2007 - 21:40
Xét G là clique dài nhất và có 2k người
Ngoài G ta xét H là clique dài nhất và ko là clique con của G, đồng thời nó có ít người chung với G nhất
Ta cho tất cả những người trong H vào phòng B và tất cả nhg người còn lại vào phòng A
Giả sử G,H có chung j người và H có i người thì clique G trong phòng A còn lại 2k-j người và biến thành Clique G'
+TH1: $ 2k-j \geq i$
Nếu $ k \geq i$ TH này chỉ việc chia G thành 2 phần, mỗi phòng 1 nửa và bài toán xong, ko cần chuyển clique H
Nếu k<i
Ta chuyển dần người từ clique G sang phòng B đến khi 2 bên có cùng độ dài i( TH trong khi thực hiện B đạt độ dài >i sẽ vô lý vì clique đó gồm toàn ng' của G và từ đó $ k \geq i $
+TH2: $ 2k-j \leq i $
Ta chọn 1 clique bất kì của A và ta cho ng' từ B sang A cho đến khi ko thể được hoặc đạt maxB-maxA=1
Gọi $ S_{i} $ là số ng' cần chuyển ít nhất từ B->A vào clique i của A để có thể đạt trạng thái maxB-maxA=1 (với điều kiện clique này có thể thực hiện được như vậy)
Ta chọn số min $ S_{i} $=n và chuyển ngần ấy ng' của A vào clique i, ta có trạng thái maxB-maxA=1
Lúc này xét 1 trong các clique có độ dài bằng maxA
- Nếu clique đó nhận ít hơn n người ( trước khi x được chuyển) thì nghĩa là nó ko thể nhận thêm ng' từ B( vì nếu ko thì chỉ cần $ S_{i} $ ng' được chuyển là ta có maxB=maxA)
Ta chuyển 1 ng' bất kì x từ B -> A. Nếu lúc này maxB=maxA, bài toán xong, còn nếu maxA-maxB=1
Xét các clique có độ dài maxA
- clique đó nhận đúng n+1 người( do lý luận trên) ta chọn 1 ng' bất kì từ clique đó( khác nhg ng' bị chuyển) chuyển sang B
Sau những động tác trên ta thấy maxA giảm 1( do các clique max mất 1 ng') còn maxB ko đổi( vì nếu trong B có 1 clique>maxA thì ghép thêm n+1 ng' đã chuyển vào sẽ tạo ra 1 clique có độ dài >i và khác 2k ), do đó bài toán xong
#17
Khách- Khách- vnm_*_*
Đã gửi 01-08-2007 - 14:46
xét trường hợp phòng 1 có clique lớn nhất độ dài k+1;phòng thứ 2 là k,suy ra 2k+1<2n
1,Nếu phòng 1 có duy nhất 1 clique độ dài k+1;phòng 2 có duy nhất 1 clique độ dài k,kí hiệu là A_1...A_{k+1} và B_1...B_k.Tồn tại 1 đỉnh A_i ko được nối với tất cả B_1..B_k vì nếu ko A_1...A__{k+1}.B_1...B_k tạo thành 1 clique dài 2k+1>2n vô lý.Chuyển A_i qua phòng 2 có f_1=f_2=k
2,Nếu phòng 1 có X_1...X_m là các clique độ dài k+1.xét 1 đỉnh L thuộc X_1 mà ko thuộc mọi clique;và chọn trong các clique ko chứa nó mỗi clique 1 đỉnh ko nối với nó được các đỉnh T_1..T_h.Chuyển L và T_1...T_h sang phòng thứ 2 thì f_1=k vì mọi clique dài k+1 đều mất 1 đỉnh.Nếu phòng 2 ko có clique nào dài k+1 có dpcm,nếu ko thì có 1 số clique dài k+1 được tạo ra.Nếu có 1 clique chứa L thì nó ko chứa các đỉnh còn lại chuyển 1 đỉnh trong T_1..T_h về phòng 1 có f_1=f_2=k+1.Nếu ko có clique nào chứa L thì chuyển L về có f_1=f_2=k+1
3,Nếu phòng 1 có 1 clique dài k+1 và phòng 2 có >1 clique dài k thì chuyển 1 đỉnh thuộc clique dài k+1 sang phòng 2.Nếu ko có clique độ dài k+1 nào được tạo ra thì có dpcm,nếu có 1 clique độ dài k+1 tạo ra thì chuyển về trường hợp 1;có nhiều clique độ dài k+1 được tạo ra thì chuyển về trường hợp 2.Có dpcm
#18
Khách- khách_*
Đã gửi 01-08-2007 - 14:57
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh