ლექცია 13, Simple Graphs, Connectedness

Problem 10.8 (b,c)

b)განვიხილოთ 1-ით, 2-ით და 3-ით დაშორებული წვეროები და ვაჩვენოთ 3 სხვადახვა გზა(ადვილია). დანარჩენი შემთხვევები ამ შემთხვევების იზომორფიზმებია.

c)წინა ამოცანაში დავამტკიცეთ, რომ 3 სხვადასხვა გზა მაინც გვაქვს, ახლა დავამტკიცოთ, რომ 3-ზე მეტი არ გვაქვს. ნებისმიერ წვეროს წავუშალოთ 3-ივე წიბო და გამოვა, რომ მაგ წვეროში ვეღარ მივალთ.

Problem 10.10(a)

დაამტკიცეთ, რომ Kn-ში ბმულობის ხარისხია n-1, როცა n > 1.

ბმულობის ხარისხი ავღნიშნოთ M-ით.
ჯერ დავამტკიცოთ, რომ M >= n-1-ზე.
წინააღმდეგ შემთხვევაში, გამოდის რომ შეგვიძლია წავშალოთ ნებისმიერი n-1 ცალი წიბო ისე, რომ ბმულობა არ დაირღვეს. ავიღოთ ნებისმიერი წვერო და წავუშალოთ ყველა წიბო. ამ წვეროში ვეღარ მივალთ და ამ წვეროდან ვეღარ წამოვალთ - დაირღვა ბმულობა - მივიღეთ წინააღმდეგობა.

ახლა დავამტკიცოთ, რომ M <= n-1-ზე.
წინააღმდეგ შემთხვევაში, თუ რომელიმე n-2 ცალ წიბოს წავშლით ბმილობა შეიძლება დაირღვეს. განვიხილოთ ყველაზე ცუდი ვარიანტი, როცა n-2-ივე წიბოს ერთ წვეროს ვუშლით. მაშინ მას დარჩება 1 წიბო, რომლითაც იგი უკავშირდება რომელიმე სხვა წვეროს, ხოლო ეგ წვერო - ყველა სხვას. გამოვიდა, რომ ბმულობა არ დაირღვა.

მივიღეთ, რომ M >= n-1 და M <= n-1, შესაბამისად, M=n-1.

Problem 10.11

მცდარი დებულება: თუ გრაფში ყოველ წვეროს დადებითი ხარისხი აქვს, მაშინ გრაფი ბმულია.

a)ორი ხაზი დახატეთ.

b)ინდუქციაში შეცდომაა ბიჯში. n+1-ის მაგივრად უნდა განვიხილოთ n-1, ანუ თუ გრაფი ბმულია, მაშინ ნებისმიერი წიბოს ამოღებისას თუ ყველა წიბო დარჩა დადებითხარისხიანი, გრაფი უნდა დარჩეს ბმული, რაც არასწორია (ადვილი შესამოწმებელია).

Problem 10.12(a)

ეილერის ციკლი არის ციკლი, რომელიც ყოველ წიბოს გაივლის ზუსტად ერთხელ.

მოცემულ გრაფში იგი არ გვაქვს.

a)ნებისმიერ წვეროში რამდენჯერაც შევდივართ, იმდენჯერ უნდა გამოვიდეთ, ანუ მისი ხარისხი ლუწია