Главная > Методы обработки данных > Графы, сети и алгоритмы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

10.8. Ориентируемые матроиды

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

Раскрашивание ориентируемого матроида М — это разбиение его элементов на три множества — R, G и В — и выделение одного из элементов — G. Визуально можно представить это разбиение как раскраску элементов матроида М в три цвета: красный, зеленый и голубой, причем точно один зеленый элемент раскрашен в темнозеленый цвет. Однако заметим, что этот элемент рассматривается как зеленый.

Основной результат этого раздела — «лемма о раскраске дуг» — получен Минти [10.2].

Теорема 10.31. (Лемма о раскраске дуг.) Пусть М — ориентируемый матроид. Для любого раскрашивания элементов матроида М справедливо точно одно из следующих утверждений:

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

2. Существует коцикл, содержащий темно-зеленый элемент, но не имеющий красных. Все зеленые элементы в нем ориентированы одинаково.

Доказательство. Докажем индукцией по числу зеленых элементов. Если имеется единственный зеленый элемент, результат следует из аксиомы

Допустим, что теорема справедлива, когда число зеленых элементов равно . Тогда рассмотрим раскрашивание, в котором число зеленых элементов равно Выберем зеленый элемент отличный от темно-зеленого (рис. 10.4).

Рис. 10.4.

Раскрасим элемент в красный цвет. В получившемся раскрашивании стало зеленых элементов. Если теперь найдется коцикл типа 2, то теорема доказана.

Допустим, мы раскрасили в голубой цвет. Если в получившемся раскрашивании имеется цикл типа 1, то теорема доказана.

Предположим, что ни одно из этих допущений не имеет места. Тогда по индуктивному предположению мы имеем:

а) существует коцикл типа 2, если раскрашен в голубой цвет;

б) существует цикл типа 1, если раскрашен в красный цвет.

Теперь пусть соответствующие строки цикломатической матрицы и коцикломатической матрицы имеют следующий вид:

Не нарушая общности, мы здесь допустили, что в позиции темно-зеленого элемента в обоих векторах стоит

По определению произведение двух этих векторов равно нулю. Вклад в произведение от темно-зеленого элемента равен 1; от всех красных и голубых элементов — нулю; от зеленых элементов — неотрицательному целому и от неизвестному целому q, которое равно 0, 1 или —1. Таким образом, Это равенство выполняется только при Поэтому в одном из векторов под знаком вопроса скрывается +1, а в другом —1. Выбрав вектор, в котором знак вопроса скрывает 1, получим требуемый цикл или коцикл.

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

Лемма о раскраске дуг в частном случае графов [10.5, 10.6] очевидна, она используется в гл. 11 в доказательстве свойства «неусиления» резисторных схем.

<< Предыдущий параграф Следующий параграф >>
Оглавление