Примеры матроидов
Версия от 21:24, 5 июня 2014; Maryann (обсуждение | вклад)
Содержание
Матричный матроид
Определение: |
Пусть | — векторное пространство над телом , пусть набор векторов из пространства является носителем . Элементами независимого множества данного матроида являются множества линейно-независимых векторов из набора . Тогда , называется матричным матроидом (vector matroid)
Лемма: |
Матричный матроид является матроидом. |
Доказательство: |
Проверим выполнение аксиом независимости: 1) Множество в котором нет векторов является линейно-независимым. 2) Если из набора линейно-независимых векторов убрать некоторые, то этот набор не станет зависимым. 3) Пусть не так. Тогда такой, что множество векторов — линейно зависимо. Значит, оно образует базис в пространстве векторов "натянутом" на множество векторов . Но тогда , так как мощность базиса больше мощности любого линейно-независимого множества, а — линейно-независимо, а по условию . Противоречие, значит предположение не верно и 3-е свойство тоже выполнено. |
Графовый матроид
Определение: |
Пусть | — неориентированный граф. Тогда , где состоит из всех ацикличных множеств ребер (то есть являющихся лесами), называют графовым (графическим) матроидом (graphic matroid).
Лемма: |
Графовый матроид является матроидом. |
Доказательство: |
Проверим выполнение аксиом независимости: 1) Пустое множество является ациклическим, а значит входит в .2) Очевидно, что любой подграф леса, так же является лесом, а значит входит в вследствие своей ацикличности.3) В графе Допустим в как минимум две компоненты связанности, иначе являлся бы остовным деревом и не существовало бы ациклического множества с большей мощностью. не существует ребра, соединяющего две различные компоненты связанности из , значит любая компонента связанности из целиком вершинно-входит в какую-либо компоненту из . Рассмотрим любую компоненту связанности Q из , у неё вершин и рёбер. Теперь рассмотрим все компоненты связанности из , вершинно-входящие в , пусть их штук, тогда суммарное количество рёбер из равно , что не превосходит (количество рёбер в ). Просуммируем неравенство по всем компонентам связанности из и получим , что противоречит условию. Значит предположение не верно, и в существует искомое ребро из разных компонент связанности . |
Трансверсальный матроид
Определение: |
Пусть | — двудольный граф. Тогда паросочетание называют трансверсальным матроидом (transversal matroid).
Лемма: |
Трансверсальный матроид является матроидом. |
Доказательство: |
Проверим выполнение аксиом независимости: 1) Пустое паросочетание удовлетворяет условию. 2) Подмножество паросочетания также является паросочетанием. Удалим из исходного паросочетания ребра, концами которых являются вершины из множества . Оставшееся множество ребер будет являться паросочетанием, которое обозначим за . И будет выполняться условие , что значит, .3) Раскрасим ребра из паросочетания, соответствующего в синий цвет, а соответствующего — в красный. Причем ребра, соответствующие двум паросочетаниям, будут окрашены в пурпурный цвет. Таким образом, получится ребер синего цвета, ребер красного цвета, и будет выполняться соотношение . Рассмотрим подграф , индуцированный красными и синими ребрами из исходного графа. Каждая вершина соответствует либо двум ребрам — синему и красному, либо одному — синему или красному. Любая компонента связности представляет собой либо путь, либо цикл, состоящий из чередующихся красных и синих ребер. Так как граф двудольный, любой цикл состоит из четного числа ребер. Так как синих ребер больше, чем красных, то должен существовать путь, начинающийся и оканчивающийся синим ребром. Обозначим этот путь . Поменяем в синий и красный цвета. Получаем, что ребра, окрашенные в красный и пурпурный цвета образуют паросочетание в графе. Очевидно, что подмножество соответствующее этому новому паросочетанию имеет вид , где . Что значит, что . |
Универсальный матроид
Определение: |
Универсальным матроидом (uniform matroid) называют объект | , где
Лемма: |
Универсальный матроид является матроидом. |
Доказательство: |
Проверим выполнение аксиом независимости: 1)
2)
3) Так как Рассмотрим и числа в каждом множестве различны, найдётся такое число , которое не будет принадлежать меньшему по мощности множеству . . |
См. также
Источники
- Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы (глава 4. Матроиды)
- Примеры матроидов
- Wikipedia — Matroid
- Википедия — Матроид