Изменения
Нет описания правки
{{Определение
|definition=
Пусть <tex>G = (V, E)</tex> - неориентированный граф. Тогда <tex>M = (E, I_GI)</tex>, где <tex>I_GI</tex> состоит из всех ацикличных множеств ребер (то есть являющихся лесами), называют '''матричным графовым(графическим) матроидом.'''
}}
{{Лемма
|statement = Матричный Графовый матроид является матроидом.
|proof =
Проверим выполнение аксиом независимости:
1) <tex>\varnothing \in I_GI</tex>
Пустое множество является ациклическим, а значит входит в <tex>I_GI</tex>.
2) <tex>A \subset B, B \in I_G I \Rightarrow A \in I_GI</tex>
Очевидно, что любой подграф леса, так же является лесом, а значит входит в <tex>I_GI</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_GI</tex>
В графе <tex>G_A = (V, A)</tex> как минимум две компоненты связанности, иначе <tex>G_A</tex> являлся бы остовным деревом и не существовало бы ациклического множества с большей мощностью.
