5.8. Матрица графов и комбинаторная топология

Свяжем введенные выше понятия с основными идеями комбинаторной топологии. При этом некоторые из результатов будут повторять материал, изложенный ранее, но он будет представлен с другой точки зрения. В частности, будет дано еще одно доказательство теоремы о раскрашивании.

1-цепью ориентированного графа вершинами ребрами назовем линейную комбинацию ребер, т. е. действительные числа. В общем случае, такое ограничение не обязательно, могут быть комплексными или просто рациональными. Множество всех -цепей определяет векторное пространство на при этом множество ребер образует базис размерности Сложение цепей в векторном пространстве определяется сложением соответствующих коэффициентов. Аналогично можно определить векторное пространство То, элементами которого являются -цепи, используя линейные комбинации вершин с действительными числами т. е. суммы вида Скалярное произведение двух -цепей или двух -цепей определяется как сумма произведений соответствующих коэффициентов. Если эта сумма равна нулю, то соответствующие цепи называются ортогональными.

Можно ввести граничный (краевой) оператор (и кограничный оператор б), который преобразует и То в соответственно. Если определен на ребре то его также можно определить на -цепи, потребовав, чтобы он был линеен.

Пусть ребро ориентировано от граничной точки к граничной точке Тогда определим

Заметим, что могут совпадать, образуя одну вершину графа. Если некоторая вершина графа, то

кограница определяется «пучком в у»:

где первая сумма берется по ребрам, ориентированным по направлению к у, а вторая — по ребрам, ориентированным по направлению от Аналогично, кограница -цепи определяется следующим образом:

Заметим, что граница цикла или линейной комбинации циклов равна нулю. -цепи, имеющие нулевую границу, образуют векторное пространство, являющееся подпространством Коциклом называется некоторая -цепь и кограница некоторой -цепи. Множество кограниц также образует векторное пространство, являющееся подпространством Отметим, следующие интересные теоремы [8].

1. Скалярное произведение границы любой -цепи и любой -цепи равно скалярному произведению -цепи и кограницы -цепи.

2. Скалярное произведение цикла и кограницы равно нулю.

3. 1-цепь, являющаяся циклом и кограницей, есть нулевой вектор пространства

4. 1-цепь, ортогональная каждой когранице, есть цикл.

5. 0-цепь, ортогональная каждому циклу, есть кограница.

6. 1-цепь единственным образом выражается в виде суммы цикла и кограницы.

7. Размерность пространства циклов равна а размерность пространства кограниц равна

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

Существует интересный способ построения матриц инцидеиций путем использования граничного оператора Рассмотрим вектор и определим вектор Рассмотрим теперь множество граничных точек ребер

и образуем вектор Пусть матрица размером элементы которой равны О, 1 или —1 в зависимости от того, является ли данная точка инцидентной данному ребру ел или нет, а также от того, является ли, она начальной или конечной точкой данного ребра Тогда Если мы теперь свяжем с каждой граничной точкой соответствующую вершину построим вектор и образуем матрицу 3), элемент которой равен нулю или единице в зависимости от того, связана ли данная граничная точка с вершиной или нет, то мы получим Таким образом, где есть матрица инцидеиций А графа.

(см. скан)

Теорема 5.12. Карта на сфере, каждая вершина которой имеет четную степень, может быть раскрашена двумя цветами.

Лемма 5.13. Замкнутая кривая С, не проходящая через вершины карты с четными степенями вершин, пересекает ребра граней четное число раз.

Доказательство теоремы. Лемма (которую мы докажем ниже) позволяет сразу доказать теорему. В самом деле, если мы будем использовать красный и синий цвета и начнем раскрашивать грань красным цветом, то цвет любой другой грани определяется числом ребер, которые пересекаются произвольной кривой, соединяющей некоторую точку в с некоторой точкой в Окрасим красным цветом, если это число четно, и синим, если оно нечетно. Из леммы следует, что любые две кривые, идущие из дадут один и тот же цвет для грани Таким образом, соседние грани будут окрашены в различные цвета, так как кривая, идущая из в одну из соседних, дает один цвет, а при пересечении любого граничного ребра должен появиться другой цвет.

Доказательство леммы. Пусть если С пересекает ребро четное число раз, и если С пересекает ребро нечетное число раз (нуль — четное число).

Так как общее число пересечений С с границей каждой грани четно (каждый раз, когда она входит в грань, она должна выйти из нее), должна быть коциклом, и следовательно, является границей некоторой -ко-цепи Пусть все вершины, на каждой из которых принимает значение 1. Так как общее число ребер, инцидентных этим вершинам, четно (ребро, инцидентное двум из этих вершин, считается дважды), общее число ребер, инцидентных только одной вершине (а не двум), тоже четно. Сюда относятся только такие ребра, для которых принимает единичное значение и, следовательно, приписывает единнчное значение четному числу ребер. Из определения получаем, что существует четное число граничных ребер граней, которые пересекаются С нечетное число раз.

ЛИТЕРАТУРА

(см. скан)

(см. скан)