Đến nội dung

Hình ảnh

Problem 3


  • Please log in to reply
Chủ đề này có 17 trả lời

#1
HUYVAN

HUYVAN

    CTCVAK08

  • Hiệp sỹ
  • 1126 Bài viết
Trong một cuộc thi Toán có một số thí sinh là bạn của nhau. Chúng ta gọi một nhóm các thí sinh là một clique nếu như hai người bất kì trong số họ là bạn của nhau. Gọi số thí sinh trong một clique là độ lớn của clique đó. Giả sử rằng độ lớn lớn nhất của một clique là một số chẵn các thí sinh. Chứng minh rằng các thí sinh tham dự cuộc thi có thể được chia vào hai căn phòng sao cho độ lớn lớn nhất của clique phòng này bằng độ lớn lớn nhất của clique phòng kia

#2
tanlsth

tanlsth

    Tiến Sĩ Diễn Đàn Toán

  • Hiệp sỹ
  • 1428 Bài viết
Bài này đưa về ngôn ngữ đồ thị
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
ThangTongHop

ThangTongHop

    Trung sĩ

  • Thành viên
  • 176 Bài viết
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

Bài viết đã được chỉnh sửa nội dung bởi ThangTongHop: 26-07-2007 - 22:11

Cuộc sống không có gì nếu không cố gắng hết sức!

#4
tanlsth

tanlsth

    Tiến Sĩ Diễn Đàn Toán

  • Hiệp sỹ
  • 1428 Bài viết
Cách chuyển người của em có vấn đề
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
ThangTongHop

ThangTongHop

    Trung sĩ

  • Thành viên
  • 176 Bài viết
Em đã chon H là clique dài nhất sau G và có thể có điểm chung với G rồi mà, sao có cái nào dài hơn H và nhỏ hơn G được
Cuộc sống không có gì nếu không cố gắng hết sức!

#6
tanlsth

tanlsth

    Tiến Sĩ Diễn Đàn Toán

  • Hiệp sỹ
  • 1428 Bài viết
Theo như em nếu $ H $ và $ G $ không có điểm chung thì sai hoàn toàn

Learn from yesterday,live for today,hope for tomorrow
The important thing is to not stop questioning


#7
ThangTongHop

ThangTongHop

    Trung sĩ

  • Thành viên
  • 176 Bài viết
H,G không có điểm chung ta vẫn làm như thế có gì sai đâu ạ. Thực ra ko có điểm chung thì tương đương với TH1

Bài viết đã được chỉnh sửa nội dung bởi ThangTongHop: 26-07-2007 - 21:46

Cuộc sống không có gì nếu không cố gắng hết sức!

#8
tanlsth

tanlsth

    Tiến Sĩ Diễn Đàn Toán

  • Hiệp sỹ
  • 1428 Bài viết
Nhưng mà nếu sau khi chuyển mà phần A vẫn không thay đổi max và khi mà số các đỉnh chuyển như em sang bên B thì sẽ tạo thành 1 đồ thị đầy đủ mới có số đỉnh lớn hơn$ i $
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
ThangTongHop

ThangTongHop

    Trung sĩ

  • Thành viên
  • 176 Bài viết
Đoạn cuối của TH2 để em nói rõ. Động tác mà ta sẽ thực hiện lần lượt như sau
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

Cuộc sống không có gì nếu không cố gắng hết sức!

#10
tanlsth

tanlsth

    Tiến Sĩ Diễn Đàn Toán

  • Hiệp sỹ
  • 1428 Bài viết
Ngay cái trường hợp 1 anh thử lấy trường hợp này
Đồ 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
ThangTongHop

ThangTongHop

    Trung sĩ

  • Thành viên
  • 176 Bài viết
Cái này 2k=i=4,j=1, cái này là TH2
Cuộc sống không có gì nếu không cố gắng hết sức!

#12
CXR

CXR

    Người thứ 7 ...

  • Founder
  • 195 Bài viết

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 :-?
"The essential thing in life is not conquering but fighting well"

#13
mignon

mignon

    Binh nhì

  • Thành viên
  • 15 Bài viết

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 :-?

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 ?

#14
ThangTongHop

ThangTongHop

    Trung sĩ

  • Thành viên
  • 176 Bài viết
Về TH2 anh xem cái đoạn phía dưới ý, em có post rõ lại rồi đấy, ghép 2 đoạn vào là ok:D
Cuộc sống không có gì nếu không cố gắng hết sức!

#15
CXR

CXR

    Người thứ 7 ...

  • Founder
  • 195 Bài viết

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.
"The essential thing in life is not conquering but fighting well"

#16
ThangTongHop

ThangTongHop

    Trung sĩ

  • Thành viên
  • 176 Bài viết
Ah ha em quên, TH1 cần dùng Giả thiết chẵn. Để em post lại lời giải đầy đủ cuối cùng

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
Cuộc sống không có gì nếu không cố gắng hết sức!

#17
Khách- Khách- vnm_*_*

Khách- Khách- vnm_*_*
  • Khách
co' thể làm như thế này. kí hiệu f_1 là độ dài clique lớn nhất trong phòng 1,tương tự với f_2
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_*

Khách- khách_*
  • Khách
chú ý là ta giả sử clique độ dài lớn nhất của đồ thị ban đầu là 2n




0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh