Карта на общините в България и Теоремата за 4-те цвята

Чували ли сте за Теоремата за 4-те цвята? Това е математическа задача възникнала още през 1852, когато англичанина Франсис Гътри правейки карта на английските графства забелязал, че добре се справя и само с 4 цвята. Споделил впечатленията си и това предизвикало интереса на математиците, което и довело до създаването на теоремата, която гласи – За оцветяването на регионите на която и да е карта, така че да няма два съседни региона с еднакъв цвят не са необходими повече от четири цвята.

Въпреки, че е проблем от средата на 19 век, едва в края миналият започват да се извеждат доказателства и/или формули за правотата на теоремата, но всичките те са генерирани от компютър. Затова и не са приети от всички математици, включително и последното доказателство от 2005-та. Тези дни в youtube ми попаднаха няколко клипа в които се обясняват изведените формули и макар нищо да не разбрах от формулите, избрах картата с най-много региони за България за която се сетих, а именно тази на общините в България и я отворих в Илюстратора.

Опит 1

Тъй като не бях много сигурен как да генерирам триангуларен граф, направих това, което всеки „прост“ дизайнер би направил – селект – колор –  и започнах една по една да оцветявам общините в 4-те избрани цвята. Не че не се бях подготвил. Вече бях прочел в Wikipedia за теоремата и споменаването, че при наличие на анклав, вероятно няма да работи, което веднага ме подсети за Община Златица, но като всеки пишещ от ляво на дясно, естествено започнах от Видин. И след извесно време стигнах до Златица и селото в което съм прекарал ваканциите си като дете…

Опит 2

Тъй като тази теорема е доказана само от компютърна симулация, се сетих че мога да се допитам до старият ми приятел Чат Джепетая. Естествено като fellow AI на работилите по проблема, още първото му изречение бе:

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

След което ми изкара един сравнително кратък Python код с който да генерирам такава карта. Краткоста на кода естествено ме втрещи, вече знаейки, че за повечето математици теоремата все още не е доказана. И въпреки, че знам какво е Python и съм добър в копи-пейста, нямах капацитета да подкарам кода… Ако сте заинтересовани може да поработите с колегата…

Опит 3

Все пак в течение на чата видях в QGIS командата Topological coloring, която не мисля, че съм имал възможноста да изпробвам. Тя добавя id за цвят базирано на даден признак и имаше нещо което най-много се доближаваше до това което исках – минимум използвани цветове. Но независимо, какви комбинации за генериране използвах, винаги най-добрият резултат бе 6 цвята. Тъй като както казах, не съм математик и явно нямаше как да създам вълшебен код който да генерира резултата автоматично от раз, направих това което всеки средно интелигентен човек би направил. Започнах да броя. При 265 общини в България средно за 4 цвята означаваше по 66-67 на цвят. Видях кой цвят е с най-голямо разпределение и ръчно проверих дали без конфликт в съответствие с теоремата не мога да добавя още общини към този цвят.

Естествено целта ми бе да намаля, не само допълнителните два цвята, а всички останали комбинации. За мое голямо съжаление най-многото общини в един цвят бяха едва малко над 70. Въпреки това продължих с още два цвята докато почти напълно елиминирах 5-и и 6-ти цвят. Въпреки че, за последният цвят останаха около 56 общини комбинациите не бяха много и все пак останаха конфликти.

Резултата

Това наистина ли карта на общините в България по теоремата за 4-те цвята? И да, и не. Колкото и да се стараех и общините да са видимо разграничими, все още има такива които споделят обща граница, като съм гледал да не е повече от няколко стотин метра. Дали тази обща граница се дължи на грешка в ГИС-а? По-скоро не, тъй като напасването на цветовете бе на „око“ и дори да има по грешка линия в района на някой връх, това не е извинение 🙂
Все пак аз съм доволен от резултата, което за мен бе малка главоблъсканица с идеята за която се събудих и за няколко часа нахвърлях. Но, ако аз на „око“ и набързо мога да достигна до толкова задоволителен резултат, то математик или професионален ГИС специалист би генерирал без грешките настояща карта на общините само с 4 цвята, въпреки Златица, Бяла или Кричим…

Карти на общините в България