StruniMa

Еднопланарни отсечки и графи

Нека са дадени няколко точки разположени по окръжност (както е показано). Колко е най-големият брой отсечки, с които могат да се свържат така, че никои две отсечки не се пресичат във вътрешна точка (ще ги наричаме "еднопланарни" отсечки)?

Нека точките са 8.

Отсечките могат да бъдат 2 вида - такива, които не се пресичат с никоя от останалите и такива, които пресичат точно една от останалите:

Отсечките, които пресичат точно една от останалите могат да се групират по двойки (на примера има 2 такива двойки). Ако премахнем по една от отсечките получаваме отсечки, които пресичат не се пресичат с нито една от останалите:

А вече знаем, че броят на останалите отсечки не може да е повече от отсечките в триангулация, който е 2.8-3=13.

Също така можем да забележим, че всяка двойка пресичащи се отсечки може да се обгради от четириъгълник, който не се пресича от никоя от останалите отсечки - нека да го наречем "независим":

В противен случай някоя от двете отсечки ще се пресича с поне 2 други (и някоя от тях ще има поне 2 пресечни точки):

Нека P е броят на отсечките, които не пресичат никоя от останалите, а Q е броят на двойките отсечки, които се пресичат т.е. общия брой на прекараните отсечки е P+2Q. Премахвайки половината от отсечките в двойките остават общо P+Q отсечки, които са не повече от 13 (тъй като никои две не се пресичат).

От друга страна броят на двойките не надвишава броят на независимите четириъгълници:

който е най-много (6.180):360=3. Така Q е не повече от 3 т.е. P+2.Q = (P+Q)+Q е не повече от 13+3=16.

Ако точките са произволен брой - n, аналогично P+Q не надвишава 2.n-3, а Q е най-много броят на независимите четириъгълници, който е не повече от:

т.е. броят на отсечките не надвишава:

където [n/2] е най-голямото цяло число, което не надвишава n/2. При четен брой точки (2.k) разделяме многоъгълника на четириъгълници и прекарваме диагоналите им, а при нечетен (2.k+1) разделяме многоъгълника на четириъгълници с прекарани диагонали и един триъгълник:

Това може да се направи и с индукция (Драгомир Грозев).

Колко е най-големият брой отсечки, които могат да се прекарат така, че всяка пресича най-много една от останалите, когато точките са разположени по произволен начин?

Тук отново можем да разсъждаваме като разделим отсечките на 2 вида - нека P са отсечките, които не се пресичат от останалите, а Q е броят на двойките пресечни отсечки.

Тук обаче можем да забележим, че двойките пресичащи се отсечки не е задължимтелно да образуват "независими" четириъгълници:

но могат да бъдат разделени с "независими" многоъгълници, които имат поне 4 върха (ще наричаме поне-четириъгълници):

Така Q не надвишава най-големият брой независими поне-четириъгълници, на които може да се раздели изпъкналата обвивка на точките. Този брой е най-голям, когато многоъгълниците са с по-малък брой страни(понеже участват с най-малка сума от ъглите в общата сума) - т.е. не може да надвишава максималния брой "независими" четириъгълници, който за даденото разположение на точките е 4:

Броят на отсечките в коя да е триангулация на точките е 6+(8.3-6):2=15. Откъдето общия брой на отсечките не надвишава 15+4=19, които и виждаме на примера.

В някои случаи броят на възможните двойки отсечки, които се пресичат може да е по-малък от най-големият брой "независими" четириъгълници. На показаната фигура двойките пресечни отсечки е не повече от 2, въпреки че броят на независимите четириъгълници могат да са повече:

В обощение можем да кажем, че броят на еднопланарните отсечки не надминава

[брой на отсечките в триангулация на изпъкналата обвивка] + [най-големия брой "независими" четириъгълници, на които може да се раздели изпъкналата обвивка]

като не винаги този брой се достига.

Как могат да се разместят 8 точки така, че да се построи най-големия възможен брой отсечки, всяка от които пресича във вътрешна точка не повече от 1 от останалите?

Вече знаем, че най-големия брой отсечки в триангулация се получава когато изпъкналата обвивка на точките е триъгълник и този брой е 3.n-6 = 3.8-6 = 18:

Същото остава вярно и за максималния брой независими четириъгълници, тъй като сумата от ъглите около точките е възможно най-голяма. В този случай тя е 180+5.360, което означава че броят на независимите четириъгълници не е повече от 5. Следователно следното разположение на точките ни дава най-големият брой еднопланарни отсечки(18+5=23) с краища точките:

Аналогично можем да разсъждаваме и за n точки - броят на отсечките в триангулация е най-много 3.n-6. Сумата от ъглите в триангулацията е:

180+(n-3).360

т.е. можем да имаме най-много n-3 двойки пресичащи се отсечки. Откъдето броят на еднопланарните отсечки е най-много (3.n-6)+(n-3)=4.n-9. Този брой се достига за всеки брой n>=6, като можем от примерите за 6,7,8 да получим индуктивно примери за всички n=6+3.k, n=7+3.k, n=8+3.k с обграждане на предишния пример с триъгълник и добавянето на нови 3 "независими" четириъгълника:

За да изследвате влезте в темата за Възли и връзки->Отвори графи. За да преминете през обучителните стъпки изберете: