Съседи и групи
Нека са дадени 5 точки. Могат ли да се свържат помежду си така, че от всяка точка да излизат по 2 отсечки?
Да, например като свържем точките в петоъгълник:
За да проверим това в състезателно ниво в СтруниМа, можем да натиснем бутона "Провери съседи". Могат ли да се свържат 5-те точки така, че от всяка точка да излизат по 5 отсечки?
За да преброим броя на нужните отсечки събираме в колко от отсечките участва всяка точка и след това трябва да разделим на 2. Т.е. ако считаме отсечките за двубои в турнир, то броят на участията винаги ще е 2 пъти по-голям от броят на двубоите. Така ако всяка точка участва в 3 отсечки, то броят на участията е 5.3=15, което не се дели точно на 2 т.е. е невъзможно да свържем отсечките по този начин.
Това може да се приложи и за групи от по 3 и повече участници във всяка.
Възможно ли е да свържем 7 точки с триъгълници така, че всяка точка да участва в точно 2 триъгълника?
Не, защото броят на участията на точките е 7.2=14, което трябва да се дели на 3 - тъй като във всеки триъгълник участват по 3 точки.
Нека да ги свържем така, че всички точки без една да участват 2 триъгълника, а последната в три ( така броят на участията ще е 6.2+3 = 15 ):
Броенето на участия на точките може да е полезно когато търсим най-големия брой групи, които изпълняват дадено условие:
Можете да изследвате в обучителната тема "Звена и съседи - графи" в Графи и вериги:
Колко е най-големият брой групи от по 3 точки такива, че всеки две групи имат не повече от една обща точка?
Можем да забележим, че всяка точка участва в не повече от 3 групи - в противен случай ще има две групи с 2 общи точки:
Броят на участията на точките не може да надминава 7.3=21. Тъй като всяка група има по 3 точки, то броят на триъгълниците не надвишава 21:3=7. Пример със 7 съществува (1-2-7, 1-3-6, 1-4-5, 5-6-7, 2-3-5, 3-4-7, 2-4-6):
Можем да забележим, че всяко едно от ребрата на 7-кликата участва в някой от триъгълнииците. Понякога е полезно и да броим не само участията на точките, но и например участията на ребрата на графа. В този случай броят на ребрата е 7.6/2 = 21, всяко ребро участва в не повече от 1 триъгълник и всеки триъгълник има 3 ребра. Т.е. броят на триъгълниците не надвишава 21:3=7. Можем да видим направените до сега групи в падащото меню отдясно, както и да трием групи от него:
Нека да разгледаме задачата за 10 точки. Колко е най-големият брой групи от по 3 точки такива, че всеки две групи имат не повече от една обща точка?
Всяка точка участва в не повече от 4 триъгълника (тъй като в противен случай ще има два триъгълника с два общи върха):
т.е. броят на участията са най-много 10.4=40 - не може да имаме повече от [40:3]=13 триъгълника. За да построим пример нека всички точки без една да участват в 4 групи и една от тях в 3 групи. Образуваме трите триъгълника от първата точка и останалите 3 ги свързваме в друг триъгълник:
След това точките 2,3,4,7,8,9 ги разделяме по 3 начина на 3 двойки точки (3-те сиви, 3-те оранжеви и 3-те сини отсечки):
Свързвайки точките 5,6,7 съответно със сивите, оранжевите и сините отсечки се получават общо 4+3.3=13 триъгълника, всеки два от които, имат най-много един общ връх:
Използвайки тези разсъждения можем да получим, че ако точките са n, то броят на триъгълниците, които изпълняват това условие не надминават най-голямото цяло число по-малко или равно от n.([n-1/2])/3. Това е така, понеже всеки връх участва в най-много [(n-1)/2] триъгълници, а всеки триъгълник има 3 върха.
Дали винаги този брой се достига? Този тип задачи се обобщава, като Щайнерови тройни системи.
Дадени са няколко точки. Колко е най-големият брой групи от по 4 точки такива, че всеки две групи имат не повече от две общи точки (от дадените)?
Тук можем да разсъждаваме, като разгледаме участията на двойките върхове (което съвпада с максималния брой общи върхове на групите). При 6 точки можем да забележим, че всяка точка участва в не повече от 2 групи, тъй като най-големият брой триъгълници с не повече от един общ връх измежду 5 точки е 2:
Всяка от търсените групи има по 4 върха в нея, а броят на участията на върховете в групите не надминава 6.2 = 12 - т.е. не може да имаме повече от 12:4 = 3 групи. За пример можем да дадем групите 1-2-3-4, 1-4-5-6, 2-3-5-6, като всеки две от тях имат не повече от 2 общи точки:
При 7 точки можем да разсъждаваме с участията на точките - участията на всяка точка не надминават максималния брой на триъгълниците измежду останалите 6 точки всеки два от които имат не повече от една обща точка. Вече знаем, че този брой е 4 т.е. броят на върховете в групите е не повече от 7.4 = 28.
Всяка група съдържа 4 точки - броят на групите не може да надминава 28:4=7 (този брой може да се намери и чрез броене на участията на двойките точки - всяка двойка точки участва в не повече от 2 групи, броят на двойките е (7.6)/2 = 21, броят на участията не надминава 21.2 = 42, всяка група има по 6 двойки, броят на групите не надминава 42:6=7). За да намерим пример, нека да направим групата 1-2-6-7 и оцветим отсечките в 3 цвята:
Така "комбинирайки" двете оранжеви отсечки 1-2 и 6-7 с отсечката 3-5, двете сини отсечки 1-7 и 2-6 с 3-4 и двете сиви отсечки 1-6 и 2-7 с 4-5 получаваме още 6 групи - 1-2-3-5, 6-7-3-5, 1-7-3-4, 2-6-3-4, 1-6-4-5 и 2-7-4-5, които имат най-много по 2 точки помежду си заедно със седмата група 1-2-6-7.
Нека точките са 9. Колко е най-големият брой групи от 4 точки, които можем да направим така, че всеки две от групите да имат не повече от 2 общи точки от 9-те (Корейска олимпиада за малки ученици)?
Забелязваме, че всяка двойка точки (1-9 на долната фигура) може да участва в най-много 3 групи - в противен случаи ще има две групи с 3 общи точки.
Тъй като броят на двойките точки е (9.8)/2=36, то броят на участията на двойките в групите не надвишава 36.3=108. Всяка група има 6 различни двойки точки - т.е. броят на групите не надвишава 108:6=18. Дали наистина този брой се достига.
До същия извод можем да достигнем и ако използваме, че за 8 точки броят на триъгълниците с една обща точка е най-много 8 (пробвайте сами). Така общо точките може да имат най-много 9.8 = 72 участия в групите. Във всяка група има по 4 точки - т.е. броят на групите не надвишава 72:4=18.
Оказва се, че съществува пример с 18 групи. Нека да построим 8 триъгълника с точките от 2 до 9, всеки два от които имат най-много 1 обща точка от тях - 2-3-8, 3-4-9, 4-5-2, 5-6-3, 6-7-4, 7-8-5, 8-9-6, 9-2-7.
Добавяйки точка 1 към тях получаваме 8 групи, които имат не повече от 2 общи точки от дадените: 1-2-3-8, 1-3-4-9, 1-4-5-2, 1-5-6-3, 1-6-7-4, 1-7-8-5, 1-8-9-6, 1-9-2-7. Измежду точките от 2 до 9 можем да построим 8 групи с ротация - 2-3-4-7, 3-4-5-8, 4-5-6-9, 5-6-7-2, 6-7-8-3, 7-8-9-4, 8-9-2-5, 9-2-3-6. Към тях добавяме и групите 2-4-6-8 и 3-5-7-9. Може да се провери, че 3-те вида групи нямат общи триъгълници помежду си.
Можете да изследвате в обучителната тема "Брой групи" в Графи и вериги:
Copyright: Mladen Valkov