10.5. Ограничение, сужение и миноры матроида

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

Рис. 10.3. а — граф , ограничение G на сужение G на Г.

Фактически граф является порожденным графом G на Т. Граф называемый сужением G на Т, получается стягиванием ребер, принадлежащих На рис. 10.3 представлены граф G, графы для

Легко убедиться в следующем:

1. Граф G, порожденный подмножеством ребер X графа G, является ациклическим подграфом тогда и только тогда, когда G ациклический подграф графа

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

Если — множество независимых множеств матроида М на S и , тогда пусть Легко видеть, что — множество независимых множеств матроида на Т. Этот матроид обозначается и называется ограничением М на Т. Очевидны следующие утверждения:

1. — независимое множество в тогда и только тогда, когда X — независимое множество в М.

2. — цикл тогда и только тогда, когда X — цикл матроида М.

3. Если К — функция ранга тогда для любого

4. Если М (G) — циклический матроид графа G с множеством ребер Е, то для любого ТЕ.

Определим теперь подматроид . Пусть — набор всех таких подмножеств , что существует максимальное независимое подмножество для которого .

Теорема — набор независимых множеств матроида на Т. Доказательство. Пусть такие члены что Тогда существуют максимальные независимые подмножества для которых , и независимые множества М. Очевидно, что Следовательно, по аксиоме 1.3 существует такой элемент к что — независимое множество в М. Заметим, что Кроме того, поскольку максимальное независимое подмножество Поэтому входит в Таким образом, удовлетворяет аксиоме 1.3. Легко видеть, что аксиомы 1.1 и 1.2 также выполняются.

Определенный в теореме матроид называется сужением М на Т и обозначается Заметим, что если М (G) — циклический матроид графа G с множеством ребер Е, то для любого

Пусть — функция ранга Тогда из определения получим, что для любого

В гл. 7 мы заметили, что размыкание или удаление ребер и стягивание ребер графа — двойственные операции. В частности, если G и — двойственные графы, — соответствующие подмножества ребер G к — двойственный к граф (теорема 7.10). Следующая теорема — матроидный аналог этой взаимосвязи.

Теорема 10.22. Если М — матроид на , тогда .

Доказательство. 1. Пусть к — функция ранга , а k — функция ранга . Тогда из выражения (10.5) следует, что для любого .

Пусть — функция ранга , а — функция ранга М Т, Тогда из выражений (10.5) и (10.9) следует, что

согласно выражению (10.8).

Так как имеют одну функцию ранга, то

2. В п. 1 заменяя М на М и взяв двойственные матроиды, получим п. 2.

Пусть М — матроид на 5 и матроид N на Т называется минором М, если N получен последовательностью ограничений и сужений М. Тема, связанная с минорами матроидов, глубоко изучена Таттом [10.3].

Используя терминологию теории матроидов, можно сформулировать множество результатов, касающихся планарных и двойственных графов. Например, теорему 7.5 можно сформулировать следующим образом:

Граф планарей тогда и только тогда, когда циклический матроид М (G) графа не содержит в качестве миноров матроидов