68
правок
Изменения
Нет описания правки
Пусть <tex>V</tex> - векторное пространство над телом <tex>F</tex>, пусть набор векторов <tex>v_1,...,v_n</tex> из пространства <tex>V</tex> является носителем <tex>X</tex>. Элементами независимого множества <tex>I</tex> данного матроида являются множества линейно-независимых векторов из набора <tex>v_1,...,v_n</tex>.
}}
{{Лемма
|statement = Матричный матроид является матроидом.
|proof =
Проверим выполнение аксиом независимости:
1) <tex>\varnothing \in I</tex>
Множество в котором нет векторов является линейно-независимым.
2) <tex>A \subset B, B \in I \Rightarrow A \in I</tex>
Если из набора линейно-независимых векторов убрать некоторые, то этот набор не станет зависимым.
3) <tex>\mid A \mid < \mid B \mid \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>A \cup B</tex>
}}
==Графовый матроид==
{{Определение
Пусть <tex>G = \langle V, E \rangle</tex> - неориентированный граф. Тогда <tex>M = \langle E, I \rangle </tex>, где <tex>I</tex> состоит из всех ацикличных множеств ребер (то есть являющихся лесами), называют '''графовым (графическим) матроидом.'''
}}
{{Лемма
|statement = Графовый матроид является матроидом.
