137
правок
Изменения
м
Нет описания правки
{{Определение
|definition=
Пусть <tex>V</tex> - — векторное пространство над телом <tex>F</tex>, пусть набор векторов <tex>V_i = \mathcal{f} v_1,...,v_n\mathcal {g}</tex> из пространства <tex>V</tex> является носителем <tex>X</tex>. Элементами независимого множества <tex>I</tex> данного матроида являются множества линейно-независимых векторов из набора <tex>v_1v_ 1,...\dots,v_n</tex>.
Тогда <tex>M = \langle V_i, I \rangle </tex>, называется '''матричным матроидом (vector matroid)'''
}}
3) <tex>| A | < | B | \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>| A \cup \mathcal{f} x \mathcal {g} | > | B | </tex>, так как мощность базиса больше мощности любого линейно-независимого множества, а <tex>B</tex> - линейно-независимо. Противоречие с условием. По , а по условию <tex>| A | + 1 \leq leqslant | B | </tex>. Противоречие, значит предположение не верно и 3-е свойство тоже выполнено.
}}
{{Определение
|definition=
Пусть <tex>G = \langle V, E \rangle</tex> - — неориентированный граф. Тогда <tex>M = \langle E, I \rangle </tex>, где <tex>I</tex> состоит из всех ацикличных множеств ребер (то есть являющихся лесами), называют '''графовым (графическим) матроидом (graphic matroid).'''.
}}
{{Лемма
В графе <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>| A | \ge geqslant | B |</tex> , что противоречит условию. Значит предположение не верно , и в <tex>B</tex> существует искомое ребро <tex>x</tex> из разных компонент связанности <tex>G_B</tex>.
}}
