ЧАСТЬ I. ОСНОВЫ ТЕОРИИ

Первая часть книги состоит из пяти глав. В главах 1 и 2 даны основные определения и теоремы, касающиеся соответственно неориентированных и ориентированных графов. В главе 3 продолжается развитие теории, причем основное внимание концентрируется на различных методах разбиения и измерения расстояний в графах. В четвертой главе рассматриваются плоские графы и задачи раскраски, наиболее ярким примером которых является классическая проблема четырех красок. В главе 5 основное внимание уделяется использованию алгебраических методов для исследования свойств графа с помощью представляющих его матриц.

Глава 1. ОСНОВНЫЕ ПОНЯТИЯ: НЕОРИЕНТИРОВАННЫЕ ГРАФЫ

1.1. Введение

В настоящей главе вводится понятие графа. Граф определяется сначала как геометрическая структура, состоящая из разбросанных в пространстве точек (вершин), соединенных системой кривых (ребер). В последующем дается его определение в абстрактных терминах теории множеств. Приводится основная терминология и вводятся обозначения, необходимые для описания локальных и глобальных структурных свойств графа. «Таким образом, данная глава, вместе со второй главой, в которой рассматриваются графы с ориентированными ребрами, дает необходимый словарь для описания графов. Чтобы

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

Учитывая, что в настоящее время в теории графов нет стандартной терминологии и обозначений, мы настоятельно советуем читателю изучить содержание этих двух глав до того, как он перейдет к последующему материалу.