Изменения

Перейти к: навигация, поиск

Примеры матроидов

562 байта добавлено, 20:40, 24 июня 2011
Нет описания правки
{{Определение
|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_1,...,v_n</tex>.Тогда <tex>M = \langle V_i, I \rangle </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>U</tex> "натянутыхнатянутом" на множество векторов <tex>A \cup B</tex>. Но тогда <tex>\mid A \cup \mathcal{f} x \mathcal {g} \mid > \mid B \mid </tex>, так как мощность базиса больше мощности любого линейно-независимого множества, а <tex>B</tex> - линейно-независимо. Противоречие с условием. По условию <tex>\mid A \mid + 1 \leq \mid B \mid </tex>.
}}
68
правок

Навигация