ლექცია 12, მარტივი გრაფები, ხარისხები, იზომორფიზმი

Problem 10.1 (a,b)

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

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

ბ) დაასკვენით, რომ წვეულებაზე სადაც ხალხი ერთმანეთს ხელს ართმევა, ისეთი ხალხის რაოდენობა, რომლებმაც კენტჯერ ჩამოართვეს ხელი, ლუწია.

ადამიანი ავღნიშნოთ წვეროთი, ხელისჩამორთმევა - წიბოთი და წინა ამოცანაზე დავდივართ.

Problem 10.2 (a,b)

a) თუ სწორად მახსოვს, შესაძებელია
b) შეუძლებელია: G3-ში არის მესამე ხარისხის წვერო, G4-ში - არა.

Problem 10.6

პირდაპირ რომ შევუსაბამოთ, 1-B 2-A დანარჩენი პირდაპირ, სარკისებურად, 1-B 2-A სარკისებურად. იმედია გასაგებია :) თუ არა, განვავრცობ.

Problem 10.5

ისევ და ისევ, ჩვენ ვუშვებთ, რომ სწორია n-ისთვის და ვამოწმებთ n+1-ს, მაშინ, როცა უნდა ვამოწმებდეთ n-1-ს.

Problem 10.3

b არაფრის იზომორფულია, რადგან სხვებისგან განსხვავებით მე-4 ხარისხის წვეროები აქვს.

მგონი a და d არის იზომორფულები. მოგვიანებით გადავამოწმებ.