5.7. Реализуемость матриц циклов и разрезов

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

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

Вопрос о реализуемости графа изучался многими исследователями. Интересный обзор работ в этом направлении дан в статье и Кима [1]. Строгая и глубокая теория, дающая необходимые и достаточные условия реализуемости, была развита Таттом [17, 18]. Здесь мы ограничимся только самым общим рассмотрением основной теоремы.

Рассмотрим вектор-столбцы некоторой матрицы. Подмножество этих столбцов может оказаться линейно зависимым или линейно независимым. В общем такие подмножества распадаются на два класса, которые не являются произвольными в силу, например, следующих двух теорем [19].

1. Любое подмножество независимого множества также независимо.

2. Если независимые множества, содержащие вектор-столбцов соответственно, то вместе с некоторым столбцом из образует независимое множество, содержащее столбцов.

Система, удовлетворяющая условиям (1) и (2), называется матроидом. Существуют теоремы, не выводимые из (1) и (2), т. е. имеются матроиды, которые не имеют соответствующих матриц. Таким образом, каждая матрица является матроидом, но обратное, вообще говоря, неверно.

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

1. Ни один из элементов не содержит другого в качестве собственного подмножества.

2. Если то существует такое, что

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

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

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

Цепь из группы цепей является элементарной, если она отлична от нуля и не существует ненулевой цепи такой, что есть подмножество Здесь носитель цепи определяется, как множество всех таких, что

Если кольцо целых чисел, то примитивная цепь из определяется как элементарная цепь, где принимают значения 0, 1, —1.

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

Если класс носителей элементарных цепей группы то является матроидом на который называется матроидом Этот матроид называется бинарным или регулярным, если он соответствует бинарным или регулярным группам цепей соответственно.

Пусть обозначают матроид простых разрезов и матроид простых циклов графа соответственно. Матроид называется графическим (кографиче-ским), если существует граф такой, что

Пусть матроид на множестве и пусть обозначает множество минимальных непустых пересечений элементов 5 с (где минимальное непустое перечисление обозначает пересечение, не содержащее другого в качестве подмножества). Тогда есть матроид на 5, называемый редукцией к 5. (Пусть обозначает подграф графа определяемый множеством 5 ребер. Если матроид разрезов графа то есть матроид разрезов

Аналогично, множество элементов которые являются подмножествами 5, есть матроид на 5, который Обозначается и называется сжатием в 5. (Пусть обозначает подграф графа полученный сжатием в точку всех ребер, содержащихся в 5. Если матроид разрезов графа то есть матроид разрезов В циклах роли «нулей» и «единиц» должны поменяться.)

Наконец, если матроид на то матроид вида где называется минором

Теорема 5.11. Матроид является графическим (кографическим) тогда и только тогда, когда он регулярен и не имеет минора, являющегося матроидом циклов (матроидом разрезов) графа Понтрягина — Куратовского.