" 0 C F G H K L N P S T W Z А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Э Ю Я

ЧЕТЫРЕХ КРАСОК ЗАДАЧА

Значение ЧЕТЫРЕХ КРАСОК ЗАДАЧА в математической энциклопедии:

можно ли области любой плоской карты (см. Граф плоский )раскрасить четырьмя цветами так, чтобы любые две соседние области были раскрашены в различные цвета?
Гипотеза о том, что ответ на Ч. к. з. утвердительный, была сформулирована в сер. 19 в. В 1890 было доказано более слабое утверждение, а именно, что любая плоская карта раскрашивается в пять цветов. Сопоставляя любой плоской карте двойственный ей плоский граф, получают эквивалентную формулировку Ч. к. з. в терминах графов: верно ли, что хроматич. число (см. Графа, раскраска )любого плоского графа G не превосходит Многочисленные попытки решения Ч. к. з. оказали влияние на развитие ряда направлений графов теории. В 1976 анонсировано положительное решение Ч. к. з. с использованием ЭВМ (см. [3]).

Лит.:[1] Xарари Ф., Теория графов, пер. с англ., М., 1973; [2] Ore О., The four-color problem, N. у.- L., 1967; [3] Арреl К., Нakеn W., лIII. J. Math.