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