Cтраница 2
Граф, у которого все вершины имеют одну и ту же степень, называется регулярным графом. Если степень каждой вершины равна г, то граф называется регулярным степени г. Регулярные графы степени 3, называемые также кубическими ( или трехвалентными) графами ( см., например, рис. 2.5, 3.2 и 3.4), представляют особый интерес в связи с задачей раскраски, которая будет обсуждаться в гл. [16]
С рассмотренными задачами тесно связан еще один класс задач, который является предметом многих исследований. Требуется разделить вершины данного графа на наименьшее число независимых множеств. Задачи подобного типа часто называются задачами раскраски и формулируются следующим образом: назначить каждой вершине цвет ( или абстрактную пометку) таким образом, чтобы смежные вершины всегда имели различные цвета ( пометки) и число различных используемых цветов ( пометок) было как можно меньше. [17]
Первая часть книги состоит из пяти глав. В главах 1 и 2 даны основные определения и теоремы, касающиеся соответственно неориентированных и ориентированных графов. В главе 3 продолжается развитие теории, причем основное внимание концентрируется на различных методах разбиения и измерения расстояний в графах. В четвертой главе рассматриваются плоские графы и задачи раскраски, наиболее ярким примером которых является классическая проблема четырех красок. В главе 5 основное внимание уделяется использованию алгебраических методов для исследования свойств графа с помощью представляющих его матриц. [18]
Книга состоит из двух частей. В первой части, включающей главы 1 - 4 - 5, дается основной теоретический мате, риал. В главе 1 приводятся основные определения, термины и символы, необходимые для описания и классификации неориентированных графов. Глава заканчивается большим списком широко известных книг по основной теме и связанным с ней вопросам. В конце книги приводится исчерпывающая библиография, составленная Му-ном и Мозером. Она показывает чрезвычайно широкий диапазон обсуждаемых вопросов. В главе 2 приводятся определения, понятия и символы, используемые при рассмотрении ориентированных или направленных графов. Глава 3 является продолжением развития основных понятий. Основное внимание в ней уделяется способам разбиения элементов графа и измерению расстояния на графах. В главе 4 рассматриваются свойства и характеристики важного класса плоских графов и обсуждается класс проблем, получивших название задачи раскраски. В последней, пятой главе первой части помимо геометрических понятий для характеристики графов начинают использоваться алгебраические понятия. Обсуждается роль матриц при описании и структурном анализе графов. [19]