Нещодавно дізнався про такий дивовижний факт.
Проблема розфарбування карт на двовимірній поверхні була вирішена ще в 19 ст. - для поверхонь "з дірками", тобто поверхня топологічного роду більше 0. Загальна формула така:
X(g)=[(7+(1+48g)^1/2)/2] - це мінімальна кількість кольорів, в яку можна розфарбувати карту на поверхні роду g.
Рід поверхні, або Ейлерову характеристику, визначають за формулою Ейлера
2-2g=V+C-E, де V - кількість вершин графа, C - кількість клітин, E - кількість ребер.
Клітини мають бути гомеоморфними кругу, тоді g буде залежати лише від поверхні, а не від графа.
Доведення цієї формули зовсім елементарне, вміщується на одну сторінку, але - лише як нерівність при g>0. Рівність була доведена пізніше, у 1965 р.
Найдивовижніше те, що для площини (або сфери, що те саме), тобто при g=0 ця формула теж вірна, але це було встановлено тільки у 1980-ті роки комп'ютерним перебором; "нормального" доведення досі не існує.
Але ця формула не дає можливості з'ясувати, у скільки кольорів фарбується заданий граф, тому що визначення мінімального роду графа - дуже складна задача (насправді, NP-повна).
Задачі для математичного гуртка
Немає коментарів:
Дописати коментар