ლექცია 14, მარტივი გრაფები, ხეები

თეორემა 10.3.1

1. ნებისმიერი ბმული ქვეგრაფი ხეა.
2. ნებისმიერ ორ წვეროს შორის ერთადერთი მარტივი გზაა.
3. ნებისმიერი წიბოს ჩამატება ქმნის ციკლს.
4. ნებისმიერი წიბოს წაშლა "წყვეტს" გრაფს.
5. თუ 2 წვერო მაინც გვაქვს, მაშინ 2 ფოთოლი მაინც გვაქვს.
7. წვეროების რაოდენობა წიბოების რაოდენობაზე ერთით მეტია.


problem 10.8 (a)

a) H3-ს აქვს 8 წვერო, 12 წიბო. 8 წვეროიან ხეს ექნება 7 წიბო. 12 წიბოდან 14 სხვადასხვას ვერ ავირჩევთ.

problem 10.15

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

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

Problem 10.17

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

დავუშვათ საწინააღმდეგო: რომელიღაცა 2 წვეროს შორის ან 1-ზე მეტი გზაა ან არც ერთი.
თუ გზა ერთზე მეტია, მაშინ ამ გზებიდან ნებისმიერი 2 ადგენს ციკლს, ანუ გრაფი ხე ვერ იქნება.
თუ გზა არ არის, გრაფი ბმული არაა, ანუ არც ხეა.

Problem 10.18

a)დაამტკიცეთ, რომ ხის წვეროების საშუალო ხარისხი 2-ზე ნაკლებია.

ხეში v-e=1.   ხარისხთა ჯამური რაოდენობაა 2e (თითო წიბო 2 წვეროს ხარისხს ზდის ერთით).

 e = v - 1;     2*e = 2*v-2;

საშუალო ხარისხი = 2e/v;    2e/v = (2v-2)/v = 2 - 2/v;

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