Примеры матроидов: графовый матроид — различия между версиями

Текущая версия на 21:25, 8 декабря 2021

Перенаправление на:

@@ Строка 1: / Строка 1: @@
-{{Определение
+#REDIRECT [[Примеры матроидов#Графовый матроид]]
-|definition=
-Пусть <tex>G = (V, E)</tex> - неориентированный граф. Тогда <tex>M = (E, I_G)</tex>, где <tex>I_G</tex> состоит из всех ацикличных множеств ребер (то есть являющихся лесами), называют '''матричным матроидом.'''
-}}
-{{Лемма
-|statement = Матричный матроид является матроидом.
-|proof =
-Проверим выполнение аксиом независимости:
-) <tex>\varnothing \in I_G</tex>
-Пустое множество является ациклическим, а значит входит в <tex>I_G</tex>.
-) <tex>A \subset B, B \in I_G \Rightarrow A \in I_G</tex>
-Очевидно, что любой подграф леса, так же является лесом, а значит входит в <tex>I_G</tex>.
-) <tex>\mid A \mid < \mid B \mid \Rightarrow \mathcal {9} x \in B \setminus A, A \cup \mathcal{f} x \mathcal {g} \in I_G</tex>
-}}