Аксиоматизация матроида циклами
| Теорема (Аксиоматизация матроида циклами): |
Пусть — семейство подмножеств конечного непустого множества такое, что:
|
| Доказательство: |
|
Пусть семейство удовлетворяет условию теоремы. Множество назовем -независимым, если оно не содержит ни одного из множеств . Через обозначим семейство всех -независимых множеств, подмножеств . Проверим, что семейство удовлетворяет аксиомам из определения матроида. Поскольку , имеем , и первая аксиома, очевидно, выполняется. Очевидно, что если и то , и, следовательно, вторая аксиома выполнена. Проверим справедливость третьей аксиомы для семейства . Предположим, что существуют множества такие, что , для которых третья аксиома не выполнена. Среди всех таких пар выберем ту, у которой мощность минимальна. Положим . Если , то, очевидно, и аксиома выполняется. Поэтому достаточно рассмотреть . В силу нашего предположения для любого . Следовательно, существует такое, что и в силу -независимости множества имеем для любого . Ясно, что множества попарно различны. Рассмотрим множество Для него верно В силу -независимости существует такой, что Рассмотрим теперь множество Если , то существует , для которого существует такое что Пришли к противоречию с условием Пусть . Заметим, что . Поэтому в силу выбора пары для пары существует элемент , где , такой, что . Возьмем множество . Для него выполняется Если , то , что невозможно. Следовательно, и . Тогда по 3 пункуту теоремы, существует , для которого , которое равно , что невозможно. Итак, семейство удовлетворяет аксиомам матроида. Следовательно, существует матроид на множестве , для которого семейство является семейством независимых множеств. Из определения -независимости легко следует, что семейство совпадает с множеством циклов матроида Докажем, что матроид определен однозначно. Пусть есть два матроида с носителем , семейством циклов и множествами баз соответственно. Не ограничивая общности можно считать, что существует . Тогда для всех , но — семейство циклов , следовательно для всех выполнено , что невозможно. |
| Утверждение (Следствие 1 из теоремы): |
Пусть — матроид. Если и , тогда или существует единственный цикл Более того, для любого |
|
Если тогда в нем должен существовать цикл Предположим, что существует другой цикл и Поскольку тогда и , и одновременно содержат . По 3 пункту теоремы, содержит цикл Возникает противоречие, так как Поэтому, содержит единственный цикл Если для какого-либо то не является независимым и содержит цикл Более того, так как что противоречит единственности |
| Утверждение (Следствие 2 из теоремы): |
Пусть и — базы. Тогда для любого существует такой что — база. |
|
— база, следовательно при этом а Тогда, по прошлому утверждению, существует а содержится в так как |
См. также
Источники информации
- Асанов М. О., Баранский В. А., Расин В. В. — Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2
