ხის დიამეტრი და ცენტრი

რომელია ხეში ყველაზე გრძელი გზა და სად არის მისი შუა? პირველს ორი BFS პოულობს, მეორეს ფოთლების ფენა-ფენა წაშლა, ორივეს წრფივ დროში.

★ ლექცია: trees_Intro1 · ზაზა გამეზარდაშვილი▶ ვიდეო საშუალო⏱ 12 წთ

←ეყრდნობა

6სიგანეში ძებნა (BFS)დიამეტრს ორი BFS პოულობს: ჯერ უშორესი ნებისმიერი წვეროდან, მერე უშორესი იმ წვეროდან.5ხეები: ცნებები, თვისებები, შემოვლებიდიამეტრი და ცენტრი ხის ძირითადი ცნებებით იგება: სიღრმით, სიმაღლითა და გზით.

გზას უხსნის→

10დპ ხეებზედიამეტრი ხეზე დპ-ითაც გამოითვლება: ყოველ წვეროში ორი უღრმესი შვილის განშტოება შეაერთე.

1ისწავლე 2უყურე 3ითამაშე 4შეამოწმე 5ივარჯიშე

ისწავლე

იდეა, მექანიზმი და ფასი.

01ხის დიამეტრი

ხის დიამეტრი ეწოდება უგრძელეს მანძილს მის ნებისმიერ ორ წვეროს შორის. ლექციის ხეში ის 13-დან 10-მდე გადის 12-ის, 8-ის, 5-ის, 2-ის, 1-ის, 3-ისა და 6-ის გავლით: 8 წიბო. ხეს შეიძლება ერთზე მეტი დიამეტრი ჰქონდეს (სამი ტოლი მკლავის მქონე Y-ფორმის ხეს სამი აქვს), მაგრამ ყველა ერთი სიგრძისაა.

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

უხეში ძალით BFS ყოველი წვეროდან უნდა გავუშვათ და ნანახი უდიდესი მანძილი დავიმახსოვროთ: O(V²). შემდეგი ორი ნაწილი ამას O(V)-მდე ამცირებს.

ლექციის მე-14 და მე-18 სლაიდების ხე (სლაიდებზე წვეროები დანომრილი არ არის, ნომრები ჩვენია); მისი დიამეტრი 13-დან 10-მდე გადის.

02თეორემა: უშორესი წვერო დიამეტრის ბოლოა

თეორემა: ვთქვათ, ხის დიამეტრი წარმოადგენს მანძილს U წვეროდან V წვერომდე. მაშინ ხის ნებისმიერი X წვეროდან უშორესი მანძილი არის მანძილი ან U-მდე, ან V-მდე.

ლექცია საწინააღმდეგოს უშვებს: X-დან ყველაზე შორი წვერო არის რაიმე Y ფოთოლი, რომელიც არც U-ს ემთხვევა და არც V-ს. ორი შემთხვევა:

ა) X დიამეტრზე მდებარეობს. თუ Y X-დან უფრო შორსაა, ვიდრე V, მაშინ დიამეტრის X…V ნაწილის X…Y-ით ჩანაცვლებით მივიღებდით U…X…Y გზას, დიამეტრზე გრძელს. წინააღმდეგობა.
ბ) X დიამეტრის გარეთ მდებარეობს. ვიპოვოთ X-დან დიამეტრის უახლოესი Z წვერო. თუ Y X-დან უფრო შორსაა, ვიდრე V, მაშინ Z-დანაც უფრო შორს იქნება, და U…Z…Y დიამეტრზე გრძელი გამოვა. წინააღმდეგობა.

ორივე შემთხვევა შეუძლებელია, ამიტომ ნებისმიერი X-დან უშორესი წვერო დიამეტრის ბოლოა. რ.დ.გ. სწორედ ამის გამო მუშაობს შემდეგ ნაწილში აღწერილი ალგორითმი.

ლექციის დამტკიცების ბ) შემთხვევა: X დიამეტრის გარეთაა, Z დიამეტრის მისი უახლოესი წვეროა.

03დიამეტრის პოვნის ალგორითმი: ორი BFS

თეორემიდან პირდაპირ გამომდინარეობს ალგორითმი:

გავუშვათ BFS (ან DFS) ნებისმიერი წვეროდან და ვიპოვოთ უშორესი წვერო V: თეორემის თანახმად, ის დიამეტრის ერთ-ერთი ბოლოა;
გავუშვათ BFS V-დან; უშორესი წვერო U დიამეტრის მეორე ბოლოა, d[U] კი დიამეტრია.

ამ ხეზე 7-დან დაწყებით: პირველი BFS 13-ს 7 მანძილზე აღწევს, ის ყველაზე შორსაა, ე.ი. V = 13. მეორე BFS 13-დან 10-ს 8 მანძილზე აღწევს: U = 10, დიამეტრი 8. თუ მეორე გაშვების მშობლების მასივს შევინახავთ, თავად გზასაც ამოვბეჭდავთ: 13, 12, 8, 5, 2, 1, 3, 6, 10.

ფრთხილად: პირველი მანძილი (7) დიამეტრი არ არის; ის მხოლოდ გვეუბნება, საიდან დავიწყოთ მეორე გაშვება. ხეზე ყოველი BFS O(V)-ია, რადგან E = V − 1, ამიტომ მთელი ალგორითმი O(V) ღირს. არაუარყოფითი წონების შემთხვევაში BFS შევცვალოთ DFS-ით, რომელიც წონებს აჯამებს; თეორემა ისევ სამართლიანია.

პატარა რიცხვები BFS-ის მანძილებია. 7-დან უშორესია 13; 13-დან უშორესია 10, მანძილით 8.

04ექსცენტრისიტეტი, ცენტრი და რადიუსი

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

ხეს შეიძლება ჰქონდეს ერთი ან ორი ცენტრი; შესაბამისად მათ ცენტრულ ან ბიცენტრულ ხეებს უწოდებენ. 13-წვეროიან ხეს აქვს ცენტრი 2, რადიუსი 4 და დიამეტრი 8. დაუმატე კიდევ ერთი ფოთოლი ისე, რომ დიამეტრი 9 გახდეს, და მიიღებ მარჯვენა ბიცენტრულ ხეს ცენტრებით 1 და 2 და რადიუსით 5.

რატომ გვაინტერესებს? ცენტრი საუკეთესო ადგილია სერვერისთვის, საწყობისთვის ან შეხვედრის წერტილისთვის, როცა ყველაზე ცუდი შემთხვევის მანძილის შემცირება გვინდა. ხეების იზომორფიზმის შემოწმებისას ის ბუნებრივი სათავეცაა. და ის ყოველთვის დიამეტრზე დევს, ზუსტად მის შუაში: რადიუსი = ⌈დიამეტრი / 2⌉.

მე-18 სლაიდი: ცენტრული და ბიცენტრული ხეები, დიამეტრები ვარდისფრადაა.

05ხის ცენტრის პოვნის ალგორითმი

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

რეალიზაცია: ვინახავთ ყოველი წვეროს ხარისხს, ყველა ფოთოლს (ხარისხი 1) ვსვამთ რიგში და ბიჯ-ბიჯ ვამუშავებთ. ფოთლის წაშლა მეზობლის ხარისხს ერთით ამცირებს, და მეზობელი, რომლის ხარისხიც 1 გახდა, შემდეგი ბიჯის ფოთოლი ხდება. O(V).

ამ ხეზე: პირველი ბიჯი შლის ექვს ფოთოლს, 4, 7, 9, 10, 11, 13; მეორე შლის 6-ს და 12-ს; მესამე 3-ს და 8-ს; მეოთხე 1-ს და 5-ს; რჩება წვერო 2. ყველაზე დიდხანს დიამეტრი, უგრძელესი გზა, რჩება, ამიტომ ცენტრი ყოველთვის დიამეტრზე მდებარეობს: თუ დიამეტრზე კენტი რაოდენობის წვეროა, ცენტრი ერთია, თუ ლუწი, ორი.

ფერები აჩვენებს, რომელ ბიჯზე წაიშალა თითოეული წვერო; რჩება 2.

ფასი ერთი შეხედვით

დიამეტრი (ორი BFS)O(V)

ცენტრი (ფოთლების წაშლა)O(V)

უხეში ძალა: ყველა ექსცენტრისიტეტიO(V²)

რადიუსი D დიამეტრიდან⌈D / 2⌉

დაიმახსოვრე

დიამეტრის ორივე ბოლო ფოთოლია, ნებისმიერი წვეროდან უშორესი წვერო კი დიამეტრის ბოლოა.
ორი BFS დიამეტრს O(V)-ში პოულობს: ნებისმიერი წვერო → უშორესი V → უშორესი U, და პასუხია d[U].
ფოთლების ფენა-ფენა წაშლის შემდეგ რჩება ერთი ან ორი ცენტრი, რომლებიც დიამეტრის შუაში დგას.

უყურე

ლექცია ვიდეოს სახით.

▶

ლექცია, ანიმაციით

ვიდეო ლექციას სლაიდ-სლაიდ მიჰყვება: იგივე მაგალითი, იგივე აღნიშვნები. უყურე ვიზუალიზატორთან თამაშამდე ან მის შემდეგ.

▶ ვიდეოს გვერდი ▣ პრეზენტაციად გახსნა

ითამაშე

გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.

👀 რას უყურო: „ითამაშე“ ჩანართში უფრო პატარა, 10-წვეროიანი ხეა (დიამეტრი 6, ცენტრი 3). პირველი BFS სხვადასხვა წვეროდან დაიწყე: შორეული ბოლო შეიძლება შეიცვალოს, დიამეტრი კი არასდროს.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →

ხის დიამეტრი და ცენტრი · BFS #1 (წვ. 1-დან)

ხის დიამეტრი მისი უგრძესი გზაა. თეორემა (ხეების ლექციიდან) იძლევა ორ-BFS-იან ხერხს მის საპოვნელად O(V)-ში.

ფსევდოკოდი

 1 diameter = longest path between any two vertices 2 BFS from ANY vertex → its farthest vertex u is a diameter end 3 note u 4 BFS from u → its farthest vertex v; dist(u,v) = diameter 5 (diameter path highlighted) 6 center: peel leaves layer by layer until 1–2 vertices remain

1 / 1

შეამოწმე

სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.

№1

BFS რაიმე X წვეროდან პოულობს უშორეს Y-ს 5 მანძილზე. რა ვიცით?

№2

7-წვეროიანი გზა (ჯაჭვი). რამდენი ცენტრი აქვს და რა რადიუსი?

№3

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

ივარჯიშე

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

LeetCodeDiameter of Binary Tree დამწყები↗CSESTree Diameter დამწყები↗LeetCodeMinimum Height Trees საშუალო↗CSESTree Distances I საშუალო↗CSESTree Distances II მოწინავე↗