Примеры матроидов: графовый матроид — различия между версиями
(Новая страница: «{{Определение |definition= Пусть <tex>G = (V, E)</tex> - неориентированный граф. Тогда <tex>M = (E, I_G)</tex>, где <tex…») |
|||
(не показана 1 промежуточная версия этого же участника) | |||
Строка 1: | Строка 1: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | Пусть <tex>G = (V, E)</tex> - неориентированный граф. Тогда <tex>M = (E, | + | Пусть <tex>G = (V, E)</tex> - неориентированный граф. Тогда <tex>M = (E, I)</tex>, где <tex>I</tex> состоит из всех ацикличных множеств ребер (то есть являющихся лесами), называют '''графовым(графическим) матроидом.''' |
}} | }} | ||
{{Лемма | {{Лемма | ||
− | |statement = | + | |statement = Графовый матроид является матроидом. |
|proof = | |proof = | ||
Проверим выполнение аксиом независимости: | Проверим выполнение аксиом независимости: | ||
− | 1) <tex>\varnothing \in | + | 1) <tex>\varnothing \in I</tex> |
− | Пустое множество является ациклическим, а значит входит в <tex> | + | Пустое множество является ациклическим, а значит входит в <tex>I</tex>. |
− | 2) <tex>A \subset B, B \in | + | 2) <tex>A \subset B, B \in I \Rightarrow A \in I</tex> |
− | Очевидно, что любой подграф леса, так же является лесом, а значит входит в <tex> | + | Очевидно, что любой подграф леса, так же является лесом, а значит входит в <tex>I</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 | + | 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>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>. | ||
}} | }} |
Версия 02:13, 22 мая 2011
Определение: |
Пусть | - неориентированный граф. Тогда , где состоит из всех ацикличных множеств ребер (то есть являющихся лесами), называют графовым(графическим) матроидом.
Лемма: |
Графовый матроид является матроидом. |
Доказательство: |
Проверим выполнение аксиом независимости: 1) Пустое множество является ациклическим, а значит входит в .2) Очевидно, что любой подграф леса, так же является лесом, а значит входит в .3) В графе Допустим в как минимум две компоненты связанности, иначе являлся бы остовным деревом и не существовало бы ациклического множества с большей мощностью. не существует ребра, соединяющего две различные компоненты связанности из , значит любая компонента связанности из целиком вершинно-входит в какую-либо компоненту из . Рассмотрим любую компоненту связанности Q из , у неё вершин и рёбер. Теперь рассмотрим все компоненты связанности из вершинно-входящие в , пусть их штук, тогда суммарное кол-во рёбер из равно что не превосходит (кол-во рёбер в ). Просуммируем неравенство по всем компонентам связанности из и получим что протеворечит условию. Значит предположение не верно и в существует искомое ребро из разных компонент связанности . |