137
правок
Изменения
м
Нет описания правки
{{Определение
|definition=
Пусть <tex>V</tex> — векторное пространство над телом <tex>F</tex>, пусть набор векторов <tex>V_i = \mathcal{f} v_1,...\dots,v_n\mathcal {g}</tex> из пространства <tex>V</tex> является носителем <tex>X</tex>. Элементами независимого множества <tex>I</tex> данного матроида являются множества линейно-независимых векторов из набора <tex>v_ 1,\dots,v_n</tex>.
Тогда <tex>M = \langle V_i, I \rangle </tex>, называется '''матричным матроидом (vector matroid)'''
}}
Если из набора линейно-независимых векторов убрать некоторые, то этот набор не станет зависимым.
3) <tex>| \left\vert A | \right\vert < | \left\vert B | \right\vert \Rightarrow \mathcal {9} x \in B \setminus A, A \cup \mathcal{f} x \mathcal {g} \in I</tex>
Пусть не так. Тогда <tex>\forall x \in B \setminus A</tex> такой, что множество векторов <tex>A \cup \mathcal{f} x \mathcal {g}</tex> — линейно зависимо. Значит, оно образует базис в пространстве векторов <tex>U</tex> "натянутом" на множество векторов <tex>A \cup B</tex>. Но тогда <tex>| \left\vert A \cup \mathcal{f} x \mathcal {g} | \right\vert > | \left\vert B | \right\vert </tex>, так как мощность базиса больше мощности любого линейно-независимого множества, а <tex>B</tex> — линейно-независимо, а по условию <tex>| \left\vert A | \right\vert + 1 \leqslant | \left\vert B | \right\vert </tex>. Противоречие, значит предположение не верно и 3-е свойство тоже выполнено.
}}
Очевидно, что любой подграф леса, так же является лесом, а значит входит в <tex>I</tex> вследствие своей ацикличности.
3) <tex>| \left\vert A | \right\vert < | \left\vert B | \right\vert \Rightarrow \mathcal {9} x \in B \setminus A, A \cup \mathcal{f} x \mathcal {g} \in I</tex>
В графе <tex>G_A = \langle V, A \rangle </tex> как минимум две компоненты связанности, иначе <tex>G_A</tex> являлся бы остовным деревом и не существовало бы ациклического множества с большей мощностью.
Допустим в <tex>B</tex> не существует ребра, соединяющего две различные компоненты связанности из <tex>G_A</tex>, значит любая компонента связанности из <tex>G_B</tex> целиком вершинно-входит в какую-либо компоненту из <tex>G_A</tex>. Рассмотрим любую компоненту связанности Q из <tex>G_A</tex>, у неё <tex>k</tex> вершин и <tex>k - 1</tex> рёбер. Теперь рассмотрим все компоненты связанности <tex>P_i</tex> из <tex>G_B</tex>, вершинно-входящие в <tex>Q</tex>, пусть их <tex>m</tex> штук, тогда суммарное количество рёбер из <tex>P_i</tex> равно <tex>k - m</tex>, что не превосходит <tex>k - 1</tex> (количество рёбер в <tex>Q</tex>). Просуммируем неравенство по всем компонентам связанности из <tex>G_A</tex> и получим <tex>| \left\vert A | \right\vert \geqslant | \left\vert B |\right\vert</tex>, что противоречит условию. Значит предположение не верно, и в <tex>B</tex> существует искомое ребро <tex>x</tex> из разных компонент связанности <tex>G_B</tex>.
}}
Подмножество паросочетания также является паросочетанием. Удалим из исходного паросочетания <tex>M</tex> ребра, концами которых являются вершины из множества <tex>B \setminus A</tex>. Оставшееся множество ребер будет являться паросочетанием, которое обозначим за <tex>M'</tex>. И будет выполняться условие <tex> X \cap ends(M') = A </tex> , что значит, <tex> A \in I </tex>.
3) <tex>| \left\vert A | \right\vert < | \left\vert B | \right\vert \Rightarrow \mathcal {9} x \in B \setminus A, A \cup \mathcal{f} x \mathcal {g} \in I</tex>
Раскрасим ребра из паросочетания, соответствующего <tex> B </tex> в синий цвет, а соответствующего <tex> A </tex> — в красный. Причем ребра, соответствующие двум паросочетаниям, будут окрашены в пурпурный цвет. Таким образом, получится <tex> |B \setminus A| </tex> ребер синего цвета, <tex> |A \setminus B| </tex> ребер красного цвета, и будет выполняться соотношение <tex> |B \setminus A| > |A \setminus B|</tex>. Рассмотрим подграф <tex> H </tex>, индуцированный красными и синими ребрами из исходного графа. Каждая вершина соответствует либо двум ребрам — синему и красному, либо одному — синему или красному. Любая компонента связности представляет собой либо путь, либо цикл, состоящий из чередующихся красных и синих ребер. Так как граф двудольный, любой цикл состоит из четного числа ребер. Так как синих ребер больше, чем красных, то должен существовать путь, начинающийся и оканчивающийся синим ребром. Обозначим этот путь <tex> H' </tex>. Поменяем в <tex> H' </tex> синий и красный цвета. Получаем, что ребра, окрашенные в красный и пурпурный цвета образуют паросочетание в графе. Очевидно, что подмножество соответствующее этому новому паросочетанию имеет вид <tex>A \cup \mathcal{f} x \mathcal {g} </tex>, где <tex> x \in B \setminus A </tex>. Что значит, что <tex> A \cup \mathcal{f} x \mathcal {g} \in I</tex>.
{{Определение
|definition=
'''Универсальным матроидом (uniform matroid)''' называют объект <tex>U_n,_k = \langle X, I \rangle </tex>, где <tex>X = \{1, 2, 3, ...\dots, n\}, I = \mathcal{f} A \subset X | | \mid \left\vert A | \right\vert \leqslant k\}</tex>
}}
1) <tex>\varnothing \in I</tex>
<tex> | \left\vert \varnothing | \right\vert = 0 \leqslant k \Rightarrow \varnothing \in I</tex>
2) <tex>A \subset B, B \in I \Rightarrow A \in I</tex>
<tex> | \left\vert A | \right\vert \leqslant | \left\vert B | \right\vert \leqslant k \Rightarrow | \left\vert A | \right\vert \leqslant k \Rightarrow A \in I </tex>
3) <tex>| \left\vert A | \right\vert < | \left\vert B | \right\vert \Rightarrow \mathcal {9} x \in B \setminus A, A \cup \mathcal{f} x \mathcal {g} \in I</tex>
Так как <tex>| \left\vert A | \right\vert < | \left\vert B | \right\vert </tex> и числа в каждом множестве различны, найдётся такое число <tex> x \in B </tex>, которое не будет принадлежать меньшему по мощности множеству <tex> A </tex>.Рассмотрим <tex> A \cup \mathcal{f} x \mathcal {g} </tex>. <tex>| \left\vert A | \right\vert < | \left\vert B | \right\vert \Rightarrow | \left\vert A \cup \mathcal{f} x \mathcal {g} | \right\vert = | \left\vert A | \right\vert + 1 \leq | leqslant \left\vert B | \leq right\vert \leqslant k \Rightarrow A \cup \mathcal{f} x \mathcal {g} \in I</tex>
}}
