ლექცია 18, ბრტყელი გრაფები

Planer graphs
1. რა რეზულტატს გვაძლევს ეილერის თეორემა (ბმული ბრტყელი გრაფების შესახებ), თუ გრაფი წარმოადგენს ხეს?

v-e+f=2 - ეილერის თეორემა. თუ გრაფი ხეა, f=1 და:
v-e=1


2. Problem 12.4, p.250
ა) დაამტკიცეთ, რომ, თუ ბრტყელი გრაფის ყოველ წახნაგს შემოვუვლით პერიმეტრის გარშემო ერთხელ, მაშინ ჯამში ყოველ წიბოს გავივლით ზუსტად ორჯერ. მითითება: განიხილეთ ორი შემთხვევა, როცა წიბოს ორ მხარეზე სხვადასხვა წახნაგია და როცა წიბოს ორივე მხარეზე ერთი და იგივე წახნაგია.

როცა წიბოს განსხვავებულ მხარეებზე განსხვავებული წახნაგებია, მაშინ წიბოზე 2-ჯერ უნდა გავიაროთ - ერთხელ, რათა პირველს შემოვუაროთ გარშემო, მეორეჯერ - მეორეს.

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

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

-ეს კარგად არ მახსოვს და რატის ვთხოვ, რომ დაგვიწეროს.

3. დაამტკიცეთ, რომ თუ ბრტყელ ბმულ გრაფს აქვს 3 წვერო მაინც, მაშინ წიბოების და წვეროების რაოდენობა აკმაყოფილებს უტოლობას: e < 3v - 6. მითითება: ნახეთ Corollary
12.6.3, p.241.

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

3f <= 2e

ეილერის ფორმულაში f = (e - v + 2). ჩავსვათ ჩვენს უტოლობაში:

3(e - v + 2) <= 2e

e - 3v + 6 <= 0

e <= 3v - 6

4. დაამტკიცეთ , რომ K5 (სრული გრაფი 5 წვეროთი) არ არის ბრტყელი. (ანუ, ხუთი ოთხფეხა, რომელიც ცხოვრობს ზღვის ფსკერზე, ერთდროულად ვერ ჩამოართმევს ერთმანეთს (ყველა ყველას) ხელს (უფრო სწორად, ფეხს). მითითება: გამოიყენეთ წინა ამოცანა.
ჩავსვათ წინა ამოცანის ფორმულაში - e <= 3v - 6
ჩვენს შემთხვევაში e = 5+4+3+2+1 = 15, v = 5.

ბრტყელი რომ იყოს, მოცემული უტოლობა უნდა სრულდებოდეს:

15 <= 15 - 6.

როგორც ვხედავთ, იგი არ სრულდება.

P.S. რომ შესრულებულიყო, ვერ დავასკვნიდით, არის თუ არა K5 ბრტყელი - პირობა აუცილებელია, მაგრამ არასაკმარისი.

5. Problem 12.3, p.250 მითითება: ყოველ წახნაგის საზღვარი არის მინიმუმ 4 (და არა 3). დანარჩენი მესამე ამოცანის მსგავსად.

6. დაასაბუთეთ, რომ თუ K5 –ში ან K3,3–ში წავშლით ერთ წიბოს, მაშინ დარჩენილი გრაფი გახდება ბრტყელი.

K3,3 არი ბინარული გრაფი 3-3 წვეროთი ორივე მხარეს, რომლის ყოველი წვერო უერთდება საწინააღმდეგო 3 წვეროდან ყველას. დავხატოთ მაგალითი(ერთი წიბო წავშალეთ):

:D ფეინთის მამა ვარ. ეს არის K3,3 რომელშიც წაშლილია 1 წიბო - შუა წვეროებს რომ აერთებდა. როგორც ვხედავთ, გრაფი ბრტყელია

ახლა K5 ვნახოთ:

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