Операции с матрицами на C++. Класс DMatrix
A
Victorian Age Proof of the Four Color Theorem
( Доказательство (викторианских
времен) теоремы о четырех красках )
I.Cahit
2009
В данной работе мы обратимся к некоторым
старым работам по проблеме четырех красок. Предложим генеральный метод
конструирования контрпримеров к доказательству Alfred’a Kempe теоремы о четырех
красках и затем покажем, что все контрпримеры могут быть отметены с помощью
преобразования в специальную декомпозицию в виде двойной спиральной цепочки на
максимальном планарном графе.
В следующей части работы дано
алгоритмическое доказательство теоремы четырех красок, основанное лишь на
закрашивании поверхностей кубических пленарных карт. Алгоритмическое
доказательство состоит из трех шагов. Первые два шага — это максимальное
монохроматическое и, затем, максимальное дихроматическое закрашивание
поверхностей таким образом, что оставшиеся в результате незакрашенными (белыми)
области неполностью раскрашенной карты не образуют нечетных циклов, что
позволяет на третьем шаге элементарно сделать четырехцветную раскраску.