Примеры матроидов: графовый матроид

Материал из Викиконспекты
Версия от 01:10, 22 мая 2011; 192.168.0.2 (обсуждение) (Новая страница: «{{Определение |definition= Пусть <tex>G = (V, E)</tex> - неориентированный граф. Тогда <tex>M = (E, I_G)</tex>, где <tex…»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Определение:
Пусть [math]G = (V, E)[/math] - неориентированный граф. Тогда [math]M = (E, I_G)[/math], где [math]I_G[/math] состоит из всех ацикличных множеств ребер (то есть являющихся лесами), называют матричным матроидом.


Лемма:
Матричный матроид является матроидом.
Доказательство:
[math]\triangleright[/math]

Проверим выполнение аксиом независимости:

1) [math]\varnothing \in I_G[/math]

Пустое множество является ациклическим, а значит входит в [math]I_G[/math].

2) [math]A \subset B, B \in I_G \Rightarrow A \in I_G[/math]

Очевидно, что любой подграф леса, так же является лесом, а значит входит в [math]I_G[/math].

3) [math]\mid A \mid \lt \mid B \mid \Rightarrow \mathcal {9} x \in B \setminus A, A \cup \mathcal{f} x \mathcal {g} \in I_G[/math]
[math]\triangleleft[/math]