ИННОВАЦИИ БИЗНЕСУ

Проведенные исследования по решению проблемы минимизации количества красок при раскраске произвольного графа привели к следующим результатам .

Гипотеза четырех красок:

"Предполагается, что любую карту на плоскости или на поверхности шара можно раскрасить только четырьмя красками таким образом, что никакие две смежные страны не были одного и того же цвета…".

Или формулируя задачу в теории графов:

Каждый планарный граф 4-раскрашиваем.

Попробуем доказать теорему не с минимума используемых красок, а с максимума возможных.

И так:

1.n- полный графn-раскрашиваем, так как достаточно убрать одну связь, и граф становитсяn-1- раскрашиваем - не связные вершины имеют один цвет.

2.Максимально возможный полный планарный граф К ₄ , откуда следует любой планарный граф 4-раскрашиваем.

Гипотеза 4-х красок доказана, как частный случай 1.

Нечётные циклы сведём к К ₃ (треугольнику) по изоморфизму, ребро также рассмотрим, как К ₂ и т.д.

На основе данного доказательства автором был разработан алгоритм оптимальной раскраски произвольного графа, составлена программа на языкеqbasicи экпериментально проверенна его верность.