Оцветяване без клика - графи на Рамзи
Възможно ли е ребрата на граф да се оцветят в два цвята така, че никъде да не можем да намерим едноцветен триъгълник?
Нека графът е 4-клика.
Можем да оцветим 2 от ребрата и така, че да НЕ остане нито един триъгълник с върхове три от дадените точки и страни от един и същи цвят.
За да проверите това може да изберете "Оцветяване два цвята" от падащото меню и след това да натиснете бутона "Проверете има ли едноцветен триъгълник".
Вярно ли е, че в 6-кликата винаги ще можем да намерим поне 1 едноцветен триъгълник?
Нека да оцветим 3 от ребрата излизащи от един връх с син цвят:
Можем да забележим, че ако оцветим кое да е от ребрата 1-2, 2-3 или 1-3 в син цвят, то заедно с 6 ще направят триъгълник, който е изцяло син. От друга страна, ако и трите останат оранжеви ще се получи оранжев триъгълник.
Същото разсъждение можем да направим и ако от някой връх излизат 3 оранжеви ребра:
От всеки връх излизат 5 ребра - тогава от всяка точка излизат поне 3 едноцветни ребра. Тогава винаги има едноцветен триъгълник. Още повече - известно е, че в 6-кликата със сигурност има поне 2 едноцветни триъгълника.
Вярно ли е, че в 6-кликата винаги има поне 2 едноцветни триъгълника?
Да допуснем противното и да се опитаме да намерим пример само с един едноцветен триъгълник. Нека да допуснем, че от някой връх излизат 4 едноцветни ребра:
Тогава в получената оранжева клика (1-2-3-4) ще трябва да оцветим поне 2 от ребрата в синьо (иначе ще останат поне 2 едноцветни оранжеви триъгълнника).
Затова можем да считаме, че от всеки връх излизат по 3 едноцветни ребра. Нека от връх 6 излиат сини ребра към 1,2 и 3. Тогава 6-4 и 6-5 са оранжеви. Измежду върховете 6,1,2 и 3 със сигурност има един едноцветен триъгълник - да го наречем триъгълник А. Тогава 4-5 е синьо, тъй като в противен случай 4-5-6 ще е оранжев триъгълник различен от триъгълник А.
Показахме, че от всеки връх излизат по 3 ребра в един цвят и 2 ребра в другия цвят. Нека от някой от върховете 4 и 5 (без ограничение можем да изберем 4) да излизат 3 сини ребра. Тогава от 4 ще излизат 2 сини ребра към някои от върховете 1,2 или 3 (например 1 и 2).
Тогава ще има едноцветен триъгълник в кликата 1-2-4-5 т.е. ще има едноцветен триъгълник с някой от върховете 4 или 5. Но той ще е различен от триъгълник А. Тогава от 4 и 5 излизат по 3 оранжеви ребра.
Знаем, че 4-6 е оранжево - затова нека отново без ограничение 4-1 и 4-2 да са оранжеви. Тогава 1-2 трябва да бъде синьо - в противен случай ще получим едноцветен триъгълник с връх 4 - различен от А. Така триъгълник А е 6-1-2.
Оттук получаваме, че 1-3 и 2-3 са оранжеви (иначе ще получим втори триъгълник различен от А):
Както и да оцветяваме останалите ребра, винаги ще се получи втори едноцветен триъгълник (вижте сами!). Също така знаем, че от връх 5 излизат 3 оранжеви ребра и 2 сини. Двете различни от 5-6 оранжеви ребра, трябва да са 5-1 и 5-2 иначе ще се образува оранжев триъгълник 5-1-3 или 5-2-3 различен от А:
Така 3-4-5 става син едноцветен триъгълник различен от А т.е. в 6-кликата винаги има поне 2 едноцветни триъгълника. От последната фигура виждаме, че има пример с точно 2 триъгълника.
В случая, при който от всеки връх излизат точно 3 ребра от единия цвят и точно 2 ребра от другия цвят, можеше да забележим, че всеки връх участва в точно 3.2=6 разноцветни триъгълника:
Тогава броят на разноцветните триъгълници е (6.6)/2 = 18, тъй като всеки разноцветен триъгълник е преброен по два пъти:
Тогава, тъй като общият брой триъгълници е 20, то броят на едноцветните триъгълници е точно 20-18=2.
Можем лесно да видим, че 5-кликата има оцветяване, при което няма нито един едноцветен триъгълник:
Тогава можем да кажем, че 6-кликата е най-малката клика, при която твърдението е вярно - както и да оцветяваме 6-кликата в син и оранжев цвят винаги ще има едноцветен триъгълник. 6 се означава с числото на Рамзи - R(3,3).
Нека да докажем, че най-малката клика, при която или има синя 4-клика, или оранжев триъгълник е 9-кликата т.е. R(4,3)=9.
От всеки връх излизат по 8 ребра. Нека от някой връх излизат 4 или повече оранжеви ребра (ако са повече от 4, то разсъждението е същото):
Тогава върховете, срещу оранжевите ребра (5,6,7 и 8), трябва да образуват синя 4-клика или да се образува оранжев триъгълник с връх 9 и два върха от 5,6,7 и 8.
Нека от някой връх излизат поне 6 сини ребра:
Тогава в 6-кликата срещу тях ще има или син или оранжев триъгълник - т.е. или синия триъгълник ще образува синя 4-клика заедно с връх 9 или ще имаме оранжев триъгълник.
Остава случая, в който от всеки връх излизат по 3 оранжеви и 5 сини ребра. Нека вземем един от върховете (9) и да свържем ребрата от него:
От върховете 1,2,3,4 и 5 излизат по 2 сини и 2 оранжеви към останалите 4 - в противен случай ще имаме едноцветен триъгълник измежду тях т.е. ще се образува или синя 4-клика или оранжев триъгълник. Тъй като от 1,2,3,4 и 5 излизат по общо 3 оранжеви ребра, то от всеки от върховете излиза по точно 1 оранжево ребро към върховете 6,7 и 8 т.е. общо 5 на брой.
От друга страна от всеки от върховете 6,7,8 излизат по 2 оранжеви ребра(общо 6) към върховете 1,2,3,4 и 5, което е невъзможно.
Нека да покажем пример с 8-клика при, която няма нито синя 4-клика, нито оранжев триъгълник.
Така R(4,3)=R(3,4)=9. Също така е известно, че R(4,4)=18, т.е. най-малката клика за която е сигурно, че в нея ще има или синя 4-клика или оранжева 4-клика е 18-кликата. Това, че има едноцветна 4-клика следва от това, че от всеки от върховете излизат поне 9 едноцветни ребра:
Ако 9-те едноцветни ребра са сини, то можем да кажем, че в 9 кликата 1,2,3,4,5,6,7,8,9 ще има или син триъгълник или оранжева 4-клика:
т.е. в цялата 18-клика със сигурност има едноцветна 4-клика.
За да покажем, че това е най-малката клика, в която със сигурност има едноцветна 4-клика ще построим пример за 17-клика, в която няма едноцветна 4-клика. Всяко ребро разделя 17 кликата на две части - нека дължина на ребро да е броят на интервалите в по-малката половина от двете. Всяка 4-клика (без ограничение можем да смятаме, че точките са разположени по окръжност) има формата на изпъкнал четириъгълник заедно с двата диагонала в него:
Можем да забележим, че дължината и на двата диагонала е равна на сумата на две от ребрата, които са по страните на четириъгълника - например 3+4=7 и 3+5 = 8 (обмислете сами защо това е вярно - винаги една от двете половини, на които се разделя кликата от диагонал на 4-кликата е с не повече от 8 интервала в нея). Всички ребра в кликата имат дължина 1,2,3,4,5,6,7 и 8 т.е. остава да разделим тези числа на две групи във всяка, от които не можем да намерим 2 числа със сума трето число от групата. Такъв пример е ребрата с дължини 1,2,4 и 8 да са ребра в син цвят и с 3,5,6 и 7 да са в оранжев цвят:
Можете да изследвате в обучителната тема "Едноцветни триъгълници и клики" в Графи и вериги:
Copyright: Mladen Valkov