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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Дубликат секции из статьи "Примеры матроидов")
 
(не показана 1 промежуточная версия 1 участника)
Строка 1: Строка 1:
{{Определение
+
#REDIRECT [[Примеры матроидов#Графовый матроид]]
|definition=
 
Пусть <tex>G = (V, E)</tex> - неориентированный граф. Тогда <tex>M = (E, I_G)</tex>, где <tex>I_G</tex> состоит из всех ацикличных множеств ребер (то есть являющихся лесами), называют '''матричным матроидом.'''
 
}}
 
 
 
{{Лемма
 
|statement = Матричный матроид является матроидом.
 
|proof =
 
Проверим выполнение аксиом независимости:
 
 
 
1) <tex>\varnothing \in I_G</tex>
 
 
 
Пустое множество является ациклическим, а значит входит в <tex>I_G</tex>.
 
 
 
2) <tex>A \subset B, B \in I_G \Rightarrow A \in I_G</tex>
 
 
 
Очевидно, что любой подграф леса, так же является лесом, а значит входит в <tex>I_G</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_G</tex>
 
 
 
В графе <tex>G_A = (V, A)</tex> как минимум две компоненты связанности, иначе <tex>G_A</tex> являлся бы остовным деревом и не существовало бы ациклического множества с большей мощностью.
 
 
 
Допустим в <tex>B</tex> не существует ребра, соединяющего две различные компоненты связанности из <tex>G_A</tex>, значит любая компонента связанности из <tex>G_B</tex> целиком вершинно-входит в какую-либо компоненту из <tex>G_A</tex>. Рассмотрим любую компоненту связанности Q из <tex>G_A</tex>, у неё <tex>k</tex> вершин и <tex>k - 1</tex> рёбер. Теперь рассмотрим все компоненты связанности <tex>P_i</tex> из <tex>G_B</tex> вершинно-входящие в <tex>Q</tex>, пусть их <tex>m</tex> штук, тогда суммарное кол-во рёбер из равно <tex>k - m</tex> что не превосходит <tex>k - 1</tex> (кол-во рёбер в <tex>Q</tex>). Просуммируем неравенство по всем компонентам связанности из <tex>G_A</tex> и получим  <tex>\mid A \mid > \mid B \mid</tex> что протеворечит условию. Значит предположение не верно и в <tex>B</tex> существует искомое ребро <tex>x</tex> из разных компонент связанности <tex>G_B</tex>.
 
 
 
}}
 

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