Планарни отсечки - триангулация
Нека са дадени няколко точки разположени по окръжност (както е показано). Колко е най-големият брой отсечки, с които могат да се свържат така, че никои две отсечки не се пресичат във вътрешна точка:
Нека точките са 4.
Ако прекараме и 6-те (всички възможни отсечки между 4-те точки), то двата диагонала на четириъгълника ще се пресичат:
Тогава със сигурност трябва да премахнем 1 от тях, с което получаваме, че отговорът е 5:
Разглеждайки същия въпрос за по-голям брой точки, виждаме, че отново многоъгълникът съставен от точките се разделя на триъгълници, когато прекараме най-големият брой отсечки, които не се пресичат във вътрешна точка:
Това е така понеже, отсечките, които са страни на многоъгълника винаги могат да бъдат прекарани, а останалите отсечки разделят този многоъгълник на други многоъгълници. Ако някой от тези многоъгълници не е триъгълник, то в него винаги можем да прекараме още 1 отсечка, която не пресича останалите.
Това разделяне се нарича триангулация на многоъгълника с върхове дадените точки.
Вярно ли е, че всяка триангулация води до един и същи брой прекарани отсечки, когато точките са по окръжност?
Да разгледаме 6 точки по окръжност и една от триангулациите на шестоъгълника образуван от тях.
Можем да забележим, че сумата от ъглите на триъгълниците, които се получават от триангулацията е равна на сумата от ъглите на шестоъгълника. Тъй като сумата от ъглите на 1 триъгълник е 180 градуса, а шестоъгълника не се променя, то броят на триъгълниците във всяка от триангулациите ще е един и същ(4).
Добре известно е, че броят на триъгълниците в триангулацията на даден многоъгълник е с 2 по-малък от броят на върховете му. Следва индуктивно, тъй като от всеки многоъгълник А може да се намери така нареченото "ухо" (триъгълник, който може да се отреже от многоъгълника и от него да остане многоъгълник Б с една страна по-малко):
Ако допуснем, че за многоъгълника Б, всяка триангулация има с 2 триъгълника по-малко от броя на страните му следва, че същото е варно и за многоъгълник А.
Връщайки се на задачата с 6-те точки, броят на триъгълниците винаги е 4. Общият брой на страните им е 4.3=12. Всяка от 6-те отсечки по обиколката на многоъгълника участва само в 1 триъгълник, а останалите - точно в 2. Така, броят на отсечките в триангулация на шестоъгълника винаги е 6+(12-6):2=9.
Можем да обобщим това за произволен n-ъгълник. Броят на триъгълниците в триангулация е n-2. Триъгълниците имат 3.(n-2)=3.n-6 страни, като n от тях участват само в един триъгълник - останалите в 2. Така броят на отсечките в произволна триангулация е n+(3.n-6-n):2=2.n-3.
Вярно ли е, че всяка триангулация води до един и същи брой прекарани отсечки, когато точките имат произволно разположение?
Отговорът отново е да. Нека разгледаме 9 точки, като 4 от тях лежат вътре в многоъгълника образуван от останалите, който ще наричаме "изпъкнала обвивка" на 9-те точки.
Знаем вече, че сумата от ъглите на петоъгълника е (5-2).180 градуса, а всяка от 4-те вътрешни точки е обградена с ъгъл равен на 360 градуса. Така всяка триангулация има сума от ъглите на ъглите на триъгълниците - 11.180 градуса т.е. в нея ще участват 11 триъгълника.
Тези 11 триъгълника имат общо 33 страни, които отговарят на 5+(33-5):2=19 отсечки. Това може да се направи за произволно разположение на точките.
Колко е най-големият брой отсечки, които могат да се прекарат, когато точките са n.
Можем да забележим, че най-голямата възможна сума от ъглите на триангулация на n точки се получава, когато изпъкналата обвивка на точките е триъгълник.
Сумата от ъглите на триъгълниците в триангулацията е 180+(n-3).360=(2.n-5).180 градуса т.е. триъгълниците са 2.n-5 на брой. Броят на страните им е 6.n-15, като 3 от отсечките участват по веднъж, а всяка от останалите по 2 пъти. Така броят на отсечките е точно 3+(6.n-15-3):2=3.n-6, което е най-големият брой отсечки, който може да се прекара измежду n точки така, че никои две не се пресичат.
За да изследвате влезте в темата за Възли и връзки->Отвори графи. За да преминете през обучителните стъпки изберете:
Copyright: Mladen Valkov