Киев: Наукова думка, 1982. — 144 с.
В монографии рассматривается ряд экстремальных и комбинаторных задач, возникающих при алгебраическом исследовании проблемы раскраски плоских графов. С помощью системы линейных и нелинейных уравнений исследуется проблема четырех красок. Приводятся более простые доказательства справедливости теоремы для некоторых классов плоских графов и алгоритм раскраски плоских графов четырьмя красками.
Рассчитана на широкий круг читателей, интересующихся вопросами теории графов.
Оглавление:
Основные этапы доказательства гипотезы четырех красок.
Историческая справка.
Доказательства Тэйта, Кемпе и Хивуда.
Приводимость графов и конфигураций.
Четыре типа приводимости конфигурации.
Метод нейтрализации и его развитие.
Уравнения Хивуда.
Задача о четырех красках и группа подстановок.
О системах уравнений по модулю.
Алгебраические неравенства, связанные с раскраской треугольных графов тремя красками.
Об алгоритмах раскраски плоских графов четырьмя красками.
Комбинаторика паросочетаний и раскраска графов.
Пфаффиан и совершенные паросочетания графа.
О подсчете числа паросочетаний графа, двойственного к максимальному плоскому графу.
Подсчет коэффициентов некоторых полиномов по модулю 2 и модулю 3 с использованием формул, связанных с подсчетом числа паросочетаний.
Анализ системы уравнений по модулю.
Задача выбора и раскраска графов.
Об одном алгоритме раскраски плоских графов.
Вывод системы уравнений. Частный случай.
Некоторые условия разрешимости канонической системы.
Общее условие разрешимости системы.
Исследование системы уравнений для общего случая.
Условие решения общей канонической системы и вопросы построения алгоритма раскраски.
В монографии рассматривается ряд экстремальных и комбинаторных задач, возникающих при алгебраическом исследовании проблемы раскраски плоских графов. С помощью системы линейных и нелинейных уравнений исследуется проблема четырех красок. Приводятся более простые доказательства справедливости теоремы для некоторых классов плоских графов и алгоритм раскраски плоских графов четырьмя красками.
Рассчитана на широкий круг читателей, интересующихся вопросами теории графов.
Оглавление:
Основные этапы доказательства гипотезы четырех красок.
Историческая справка.
Доказательства Тэйта, Кемпе и Хивуда.
Приводимость графов и конфигураций.
Четыре типа приводимости конфигурации.
Метод нейтрализации и его развитие.
Уравнения Хивуда.
Задача о четырех красках и группа подстановок.
О системах уравнений по модулю.
Алгебраические неравенства, связанные с раскраской треугольных графов тремя красками.
Об алгоритмах раскраски плоских графов четырьмя красками.
Комбинаторика паросочетаний и раскраска графов.
Пфаффиан и совершенные паросочетания графа.
О подсчете числа паросочетаний графа, двойственного к максимальному плоскому графу.
Подсчет коэффициентов некоторых полиномов по модулю 2 и модулю 3 с использованием формул, связанных с подсчетом числа паросочетаний.
Анализ системы уравнений по модулю.
Задача выбора и раскраска графов.
Об одном алгоритме раскраски плоских графов.
Вывод системы уравнений. Частный случай.
Некоторые условия разрешимости канонической системы.
Общее условие разрешимости системы.
Исследование системы уравнений для общего случая.
Условие решения общей канонической системы и вопросы построения алгоритма раскраски.