Problem 10.19
განიხილავ ყველაზე კარგ ვარიანტს, რომ ზედა წვეროს ფერი იყოს 1, მას რომ უერთდებიან, მათ შორის ერთი იყოს 2, მეორე - 3. ქვედა წვეროებიდან ერთი შეგვიძლია ისევ 1-ით შევღებოთ, მაგრამ ბოლოს მაინც დასჭირდება მეოთხე ფერი.
2) ამის წაკითხვა მეზარება :)
განიხილავ ყველაზე კარგ ვარიანტს, რომ ზედა წვეროს ფერი იყოს 1, მას რომ უერთდებიან, მათ შორის ერთი იყოს 2, მეორე - 3. ქვედა წვეროებიდან ერთი შეგვიძლია ისევ 1-ით შევღებოთ, მაგრამ ბოლოს მაინც დასჭირდება მეოთხე ფერი.
2) ამის წაკითხვა მეზარება :)
3. კლიკი (clique) ეწოდება მოცემული გრაფის ისეთ ქვეგრაფს, რომელიც არის სრული (ყველა შესაძლო წიბო გავლებულია).
ა) დაამტკიცეთ, რომ თუ თუ გრაფში მაქსიმალური ზომის კლიკი (წვეროთა რაოდენობა) არის n, მაშინ გრაფის ქრომატული რიცხვი ≥ n.
თუ ყველა ყველას უერთდება, მაშინ ავირჩიოთ ნებისმიერი წვერო და შევღებოთ 1-იანით. ის უერთდება n-1 ცალ სხვა წვეროს, რომელთაგან ყველა ერთმანეთს უერთდება, ანუ ყველას განსხვავებული ფერი სჭირდება. ჯამში გამოდის 1+n-1=n ფერი მაინც.
b) შეიძლება თუ არა ვამტკიცოთ, რომ წინა უტოლობაში ყოველთვის გვექნება ტოლობა?
არ შეიძლება, ხუთკუთხედია კონტრმაგალითი: კლიკი არის 2, მაგრამ მაინც 3 ფერი სჭირდება - მადლობა გ. ლაბარტყავას.
4. Kn–ით აღინიშნება სრული გრაფი n რაოდენობის წვეროთი. ვთქვათ გრაფი G იყოს n ცალი Kn–ის გაერთიანება, სადაც არცერთ ორ Kn–ს არა აქვს საერთო წიბო.
ა) დაასაბუთეთ, რომ ამ პირობებში ორ განსხვავებულ Kn–ს ექნება მაქსიმუმ ერთი საერთო წვერო.
ბ) რას უდრის თითოეული Kn–ის ქრომატული რიცხვი?
გ) დაასაბუთეთ, რომ G გრაფის ქრომატული რიცხვი არის n. (თუ ზოგადი შემთხვევა ცოტა რთული აღმოჩნდება ( :) ), დაასაბუთეთ ამოცანა იმ შემთხვევებისთვის, როცა n=2 და n=3.) -- ეს ამოცანა არ იხნება, ამბროლას იუმორია :)
ა)ერთზე მეტი რომ ჰქონდეთ, წიბოც ექნებოდათ საერთო.
ბ)n-ს
ა) დაამტკიცეთ, რომ თუ თუ გრაფში მაქსიმალური ზომის კლიკი (წვეროთა რაოდენობა) არის n, მაშინ გრაფის ქრომატული რიცხვი ≥ n.
თუ ყველა ყველას უერთდება, მაშინ ავირჩიოთ ნებისმიერი წვერო და შევღებოთ 1-იანით. ის უერთდება n-1 ცალ სხვა წვეროს, რომელთაგან ყველა ერთმანეთს უერთდება, ანუ ყველას განსხვავებული ფერი სჭირდება. ჯამში გამოდის 1+n-1=n ფერი მაინც.
b) შეიძლება თუ არა ვამტკიცოთ, რომ წინა უტოლობაში ყოველთვის გვექნება ტოლობა?
არ შეიძლება, ხუთკუთხედია კონტრმაგალითი: კლიკი არის 2, მაგრამ მაინც 3 ფერი სჭირდება - მადლობა გ. ლაბარტყავას.
4. Kn–ით აღინიშნება სრული გრაფი n რაოდენობის წვეროთი. ვთქვათ გრაფი G იყოს n ცალი Kn–ის გაერთიანება, სადაც არცერთ ორ Kn–ს არა აქვს საერთო წიბო.
ა) დაასაბუთეთ, რომ ამ პირობებში ორ განსხვავებულ Kn–ს ექნება მაქსიმუმ ერთი საერთო წვერო.
ბ) რას უდრის თითოეული Kn–ის ქრომატული რიცხვი?
გ) დაასაბუთეთ, რომ G გრაფის ქრომატული რიცხვი არის n. (თუ ზოგადი შემთხვევა ცოტა რთული აღმოჩნდება ( :) ), დაასაბუთეთ ამოცანა იმ შემთხვევებისთვის, როცა n=2 და n=3.) -- ეს ამოცანა არ იხნება, ამბროლას იუმორია :)
ა)ერთზე მეტი რომ ჰქონდეთ, წიბოც ექნებოდათ საერთო.
ბ)n-ს
No comments:
Post a Comment