ლექცია 16, bipartite matchings

Theorem 10.6.3. დაამტკიცეთ, რომ დაწყვილება შესაძლებელია მაშინ და მხოლოდ მაშინ, როცა გოგოების სიმრავლის ყოველ ქვესიმრავლეს უფრო მეტი ან ტოლი რაოდენობის ბიჭი მოსწონს, ვიდრე ამ ქვესიმრავლეში გოგოა (ანუ რამდენი/რომელი გოგოებიც არ უნდა ავარჩიოთ, მათ ჯამში თავიანთ თავზე მეტი ან ტოლი რაოდენობის ბიჭი უნდა მოსწონდეთ)

დამტკიცება. ჯერ დავუშვათ, რომ გვაქვს დაწყვილება და ვაჩვენოთ, რომ ეს პირობა სრულდება. განვიხილოთ გოგოების ზოგადი ქვესიმრავლე. ყოველ გოგოს ერთი ბიჭი მაინც მოსწონს - ის, რომელთანაც დაწყვილებულია. მაშასადამე, გოგოების ნებისმიერი ქვესიმრავლის ზომა მათ მიერ მოწონებული ბიჭების სიმრავლის ტოლი მაინც არის. ამ მხრივ, დებულება ჭეშმარიტია.

ახლა ვაჩვენოთ, რომ თუ პირობა სრულდება, გვაქვს დაწყვილება. წიყენებთ ინდუქციას |G|-ზე, გოგოების რაოდენობაზე.

Base Case: თუ |G| =1, მაშინ პირობის მიხედვით, მას ერთი ბიჭი მაინც მოსწონს, ანუ დაწყვილება არსებობს.

ინდუქციური ბიჯი: დავუშვათ |G|≥ 2. არის ორი ვარიანტი:

ვარიანტი 1: გოგოები ყოველ ქვესიმრავლეს მოსწონს ბიჭების მკაცრად დიდი ქვესიმრავლე. ამ შემთხვევაში ასე ვიქცევით: რომელიმე გოგოს ვაწყვილებთ ბიჭთან, რომელიც მას მოსწონს და ორივეს "ვუშვებთ". დარჩენილ ხალხზე ჩვენი პირობა მაინც სრულდება და დანარჩენ გოგოებს ინდუქციურად ვაწყვილებთ.

ვარიანტი 2: გოგოების რომელიმე ქვესიმრავლე X ⊂ G მოსწონს ტოლი რაოდენობის ბიჭი - Y ⊂ B. გოგოებს X-იდან ინდუქციურად ვაწყვილებთ Y-ის ბიჭებთან და "ვუშვებთ" მათ. დანარჩენი გოგოებიც შეგვიძლია ინდუქციურად დავაწყვილოთ, თუ ვაჩვენებთ რომ პირობა სრულდება. ამისათვის განვიხილოთ დარჩენილი გოგოების ზოგადი ქვესიმრავლე - X' ⊆ (G − X), ხოლო Y' იყოს მათ მიერ მოწონებული ბიჭების სიმრავლე. უნდა ვაჩვენოთ, რომ |X'|≤|Y'|. თავდაპირველად, X ∪ X'-ს გოგოებს მოსწონდათ Y ∪ Y'-ის ბიჭები. ასე რომ, პირობის თანახმად:

|X ∪ X'|≤|Y ∪ Y'| 

გავუშვით |X| გოგო მარცხენა სიმრავლიდან (დარჩა X') და მაგდენივე ბიჭი გავუშვით მარჯვენიდან (დარჩა Y'). მაშასადამე |X'|≤|Y '|, რისი დამტკიცებაც გვინდოდა.
ასე რომ, ორივე ვარიანტში შეგვიძლია გოგოები დავაწყვილოთ.

Problem 10.23

გვყავს კლუბები. თითო კლუბში არის მინიმუმ 13 სტუდენტი. თითო სტუდენტი არის მაქსიმუმ 9 ჯგუფში, რაც საკმარისი პირობაა იმისთვის, რომ ყოველ კლუბს ჰყავდეს უნიკალური წარმომადგენელი (არ შეიძლბა ერთი სტუდენტი ერთზე მეტი კლუბის წარმომადგენელი იყოს). ახენით რატომ.

დაწყვილებისთვის საჭიროა, რომ თითოეული გოგოს ჯამური ხარისხი თითოეული ბიჭის ჯამურ ხარისხზე მეტი ან ტოლი იყოს იყოს. ამ შემთხევაში გოგოები იყოს კლუბიბები და სტუდენტები - ბიჭები.
შესაბამისად, თითოეული გოგო მინიმუმ მე-13 ხარისხისაა, ხოლო თითოეულო ბიჭი - მაქსიმუმ 9, რაც აკმაყოფილებს პირობას.
დავაწყვილოთ ტრადიციული რიტუალით სტუდენტები და კლუბები. თითოეული კლუბის წარმომადგენელი იქნება ის, ვისთანაც ის დაწყვილდება.

Problem 10.26

Theorem. A graph G is 2-colorable iff it contains no odd length cycle.

ა) სამი-ხუთი წინადადებით, ჩამოაყალიბეთ, რატომ იქნება თეორემის მარჯვენა მხარე ჭეშმარიტი, თუ მარცხენა ჭეშმარიტია.

ბ) ახლა დაუშვით, რომ მარჯვენა მხარეა ჭეშმარიტი. ახსენით, რატომ შეგვიძლია ყურადღება გავამახვილოთ გრაფის კონკრეტულ კომპონენტზე.

გ) ახსენით, როგორ შევღებოთ ნებისმიერი ხე ორი ფერით.

ავირჩიოთ ფესვი. დავალაგოთ ფენებად. პირველ ფენაში - ფესვი. ყოველ შემდეგში - ისეთი წვეროები, რომლებიც წინა ფენის წვეროებს უერთდებიან. დავნომროთ ფენები. კენტი ნომრები შევღებოთ ერთი ფერით, ლუწი - მეორეთი.

დ)აირჩიეთ H გრაფის ნებისმიერი დამფარავი ხე, T. დაამტკიცეთ, რომ H შეიძლება შევღებოთ 2 ფრად. ამისთვის აჩვენეთ, რომ T-ში არ მყოფი წიბოები სხვადასხვა ფერის წვეროებს აერთებენ.

Problem 10.27

52 კარტს ვალაგებთ 13 სვეტად, თითოში 4 რიგია. თითო სვეტიდან თითო კარტი უნდა ავიღოთ ისე, რომ გამოგვივიდეს 13 სხვადასხვა მნიშვნელობის კარტი.

აჩვენეთ, რომ ნებისმიერი n სვეტი n განსხვავებულ მნიშვნელობას მაინც მოიცავს.

გავარჩიოთ ნებისმიერი 2 სვეტი. ყველაზე ცუდ ვარიანტში ისინი შეიცავენ 2 განსხვავებული მნიშვნელობის კარტს (ორივე მნიშვნელობის 4-4 კარტს). გამოდის, რომ ნებისმიერი ორი სვეტი შეიცავს 2 განსხვავებულ მნიშვნელობას მაინც, რაც იმას ნიშნავს, რომ რამდენი სვეტიც გვაქვს (13 იქნება თუ n), მინიმუმ იმდენი განსხვავებული მნიშვნელობა გვაქვს.

ამოცანის ახსნისთვის მადლობას ვუხდით ბ-ნ ნ. დოღონაძეს.

Problem 10.28

გვაქვს 20 დადებითი თვისება. წლის დასაწყისში ყოველ სტუდენტს ჰქონდა 8 დადებითი თვისება. ყველა მათგანის ეს სიმრავლე უნიკალური იყო: არ ერთის 8 თვისება არ ემთხვეოდა არც ერთ სხვისას. დაამტკიცეთ, რომ თითოეულ მათგანს შეუძლია შეიძინოს კიდევ 1 დადებითი თვისება ისე, რომ მათი თვისებების სიმრავლეები მაინც უნიკალურებად დარჩნენ.

იმ 8 თვისებათა სიმრავლეები, რომლებიც რომელიმე სტუდენტს ახასიათებენ, იყვნენ გოგოები.
9 თვისების ყველა შესაძლო სიმრავლე - ბიჭები.

8 თვისებიანი სიმრავლისთვის რომელიმე ერთი თვისების დამატებით რა 9 წევრიანი სიმრავლის მიღებაც შეიძლება, იმასთან შევაერთოთ.

გამოვა რომ, თითოელი გოგო 12 ბიჭს უერთდება (12 საგანი დარჩა და ნებისმიერ რვიანს აქედან ერთ-ერთს ვუმატებთ ცხრიანის მისაღებად).
ხოლო ყოველი ბიჭი - მაქსიმუმ 9 გოგოს (ცხრიანს 9-დან ერთ-ერთი უნდა გამოვაკლოთ რვიანის მისაღებად, შესაბამისად 9 ვარიანტი გვაქვს). მაქსიმუმ იმიტომ, რომ შეიძლება ზოგიერთი რვიანი არც ერთ სტუდენტს არ შეესაბამებოდეს.

გვისრულდება დაწყვილების გამარტივებული პირობა, რომ გოგოების მინიმალური წევრის ხარისხი ბიჭების მაქსიმალური წევრი ხარისხზე მეტი უნდა იყო (12>9), შესაბამისად დაწყვილება შედგება და სტუდენტები მე-9 თვისებას ამ დაწყვილების მიხედვით აირჩევენ.

ამოცანის ახსნისთვის მადლობას ვუხდით ბ-ნ ნ. დოღონაძეს.