Cтраница 4
Цепочка соединит вершины третьей степени полных двудольных графов. Получим двудольный граф, в каждой доле которого по восемь вершин. Совершенное паросочетание в этом графе существует - это два крайних ребра соединительной цепочки и по три ребра из каждого из полных двудольных графов. [46]
Существуют и другие циклы задач ( см. Покрытия и упаковки, Графа укладка, Графов числовые характеристики); нек-рые из них сложились под влиянием различных разделов математики. Так, под влиянием топологии производится изучение вложений графов в различные поверхности. К у р а-т о в с к о г о): граф является плоским тогда и только тогда, когда он не содержит подграфов, получаемых с помощью подразбиения ребер из полного 5-вершинного графа и полного двудольного графа с тремя вершинами в каждой доле. В частности, было доказано, что каждая конечная группа изоморфна группе автоморфизмов нек-рого графа. [47]
Если множество вершин графа G может быть разбито на два непересекающихся непустых множества, V ( G) A ( J В, таким образом, что все ребра графа G соединяют вершины из А только с вершинами из В, то мы называем граф G двудольным, а пару ( А, В) - 2-разбиением графа G. Двудольный граф часто называют 2-раскрашиваемым графом. Мы встретимся со специальным двудольным графом Кт п - это так называемый полный двудольный граф, имеющий цветные классы размеров т и п, в котором каждая вершина из каждого цветного класса смежна с каждой вершиной из другого цветного класса. [48]
Os, если после применения любой из этих операций получается граф, не обладающий свойством А. При этом предполагается, что множество графов, не обладающих свойством А, замкнуто относительно рассматриваемых операций. Петерсена ( см. рис.) является критическим по свойству иметь реберное хроматическое число, равное 4, относительно операции удаления ребра. Полный пятивергшшный граф 5 и полный двудольный граф К3 3 ( см. Граф плоский, рис. 1), каждая доля к-рого имеет три вершины, являются критическими по свойству не быть плоским относительно операций удаления ребра, стягивания ребра, удаления вершины. [49]
Поскольку полностью подходящая когомология тривиальна, то это, таким образом, есть кограница 1-коцепи, а последнее, будучи функцией пар в Z2, являет собой граф; тройки два-графа являются носителями нечетного числа ребер этого графа. Две 1-коцепи имеют одну и ту же кограницу тогда и только тогда, когда они отличаются на 1-коцикл, то есть кограницу 0-коцепи ( функцию из точечного множества в Z2); это означает существование разбиения точечного множества Х [) Y и двух графов, согласованных внутри X и внутри У и являющихся дополнительными между этими множествами. В терминологии Зейделя эти графы являются связанными по переключению относительно разбиения XJY. Таким образом, два-граф эквивалентен переключательному классу графов. Пустой два-граф соответствует переключательному классу полных двудольных графов, а полный два-граф - двум полным графам. Эти случаи исключаются из дальнейшего рассмотрения. [50]