Cтраница 2
Оказывается, что для всех графов максимальной степени k, исключая графы, которые содержат одну компоненту, являющуюся полным графом, достаточно меньшего числа цветов. Этот результат сформулирован в теореме Брукса [10], применимой не только к плоским графам. Теорема приводится без доказательства. [16]
При таких ограничениях не всякая сеть может быть отпечатана на двух сторонах платы. В главе 4 было показано, что обыкновенный граф G и его дополнения не являются плоскими графами, если G имеет девять или более вершин. Таким образом, полный ( обыкновенный); граф, имеющий девять вершин, нельзя отпечатать, на заданной плате, так как это означало бы, что некоторый подграф G ( часть сети, отпечатанная на одной стороне) и его дополнение ( часть, отпечатанная на другой стороне) являются плоскими. [17]
Описанный выше результат Заранкевича [93] дает оценку минимального числа пересечений ребер для изображенного на плоскости простого графа, состоящего из двух множеств вершин, таких, что каждая вершина одного множества соединена с каждой вершиной второго только одним ребром. Когда каждое множество содержит по три вершины, мы имеем один из двух основных неплоских графов, фигурирующих в теореме Понтряги-на - Куратовского о плоских графах. Построив граф более общего типа, Заранкевич смог доказать результат о минимальном числе пересечений, а также указать схему реализации простых графов с минимальным числом пересечений. [18]
Банальной истиной в теории раскрашивания карт является тот факт, что всякую карту, определяемую плоским графом, имеющим гамильтонов цикл, можно раскрасить в четыре краски. Районы в одной области, выделяемой циклом, можно раскрасить, чередуя красный и синий цвета, а в другой - чередуя зеленый и желтый. Поэтому теперь мы можем утверждать, что гипотеза о четырех красках верна для всех карт, определяемых 4 - свяЗными плоскими графами. [19]
Первая часть книги состоит из пяти глав. В главах 1 и 2 даны основные определения и теоремы, касающиеся соответственно неориентированных и ориентированных графов. В главе 3 продолжается развитие теории, причем основное внимание концентрируется на различных методах разбиения и измерения расстояний в графах. В четвертой главе рассматриваются плоские графы и задачи раскраски, наиболее ярким примером которых является классическая проблема четырех красок. В главе 5 основное внимание уделяется использованию алгебраических методов для исследования свойств графа с помощью представляющих его матриц. [20]