Cтраница 4
Результирующий граф, полученный после закрепления с, и эквивалентный граф со слившимися вершинами показаны на рис. 3.3, в. Ясно, что после конечного числа преобразований этого типа получится граф, эквивалентный такому графу, который в качестве подграфа содержит граф, изображенный на рис. 3.3, г и, очевидно, означающий победу Закоротить. Таким образом, признаком игры Закоротить является граф, содержащий систему из двух стягивающих деревьев, не имеющих ни одного общего ребра. Это и есть то свойство графа, которое может сохранить Закоротить, гарантируя тем самым свой выигрыш. [46]
Звездочка означает, что при умножении коэффициентов внутри скобок мы приравниваем нулю любой член, который содержит произведение передач двух контуров или произведение передач пути и контура, которые касаются друг друга в графе. Справедливость этого правила подтверждается примерами. Доказательства будут получены из свойств графов, рассмотренных в последующих разделах. [47]
Во второй группе задач ( 10.6 - 10.8) требуется составить нормализованные графы по заданным однородным системам уравнений я системы уравнений по известным графам. Задачи третьей группы ( 10.9 - 10.11) посвящены составлению ненормализованных графов по заданным неоднородным системам и систем уравнений: по известным графам. Пятая прупла ( 10.14 - 10.17) состоит из задач по составлению нормализованных и ненормализованных графов по одной и той же системе уравнений и доказательству равносильности этих графов. Шестая группа задач ( 10.18 - 10.19) посвящена выяснению некоторых свойств графов по заданным системам и свойств систем уравнений по заданным графам. В седьмой группе ( 10.20 - 10.21) собраны задачи по преобразованиям матрицы А, связанным с построением графов по определенным условиям. [48]
Значения элементов, отличные от нуля, будут обозначать вес связи. Например, вес может быть равен вероятности перехода из одной вершины в другую или длительности работы при переходе из одного состояния в другое. В тех случаях, когда всем ненулевым элементам присваивается значение единицы, матрица будет обозначать наличие дуги независимо от ее веса. Изображение графа в виде матрицы А позволяет использовать аппарат матричного исчисления для выявления свойств графов. [49]
Первая часть книги состоит из пяти глав. В главах 1 и 2 даны основные определения и теоремы, касающиеся соответственно неориентированных и ориентированных графов. В главе 3 продолжается развитие теории, причем основное внимание концентрируется на различных методах разбиения и измерения расстояний в графах. В четвертой главе рассматриваются плоские графы и задачи раскраски, наиболее ярким примером которых является классическая проблема четырех красок. В главе 5 основное внимание уделяется использованию алгебраических методов для исследования свойств графа с помощью представляющих его матриц. [50]
Любое слово, представляющее элемент I, соответствует замкнутому пути на графе. Если принять вершину, соответствующую элементу /, за начальную точку, то путь, определяемый словом W, окончится в / - вершине. Мы называем путь замкнутым, если его начальная и конечная точки совпадают. Таким образом, если W-слово, представляющее элемент I, то путь, определяемый этим словом, будет замкнутым вне зависимости от того, какая точка принята за начальную. Из этого свойства графа группы следует, что его вершины можно пометить так, чтобы любая наперед заданная вершина соответствовала элементу /; см. упр. [51]