Изменения

Перейти к: навигация, поиск
м
Ориентированный лес
Так как <tex>|B| > |A|</tex>, следовательно количество ребер в множестве <tex>B</tex> не меньше <tex>k</tex>.
Пусть все ребра из множества <tex>B</tex> ведут в вершины множества <tex>A</tex>, значит в каждую вершину множества <tex>A</tex> входит по одному ребру множества <tex>B</tex>.
Тогда возьмем то ребро, которое указывает в корень (в вершину с нулевой степенью захода), получим ориентированное дерево с новым корнем('''ну или же получим цикл lol''').
Пусть не все ребра множества <tex>B</tex> указывают в вершины множества <tex>A</tex>, тогда возьмем то ребро <tex>uv</tex>, которое указывает в вершину не принадлежащую <tex>A</tex>. Покажем, что оно нам подойдет.
Если <tex>u \in V(A)</tex>, тогда наше текущее ориентированное дерево пополнится еще одной вершиной и ведущем к ней ребру.
Таким образом, мы нашли ребро в множестве <tex>B \setminus A</tex>, которое можем добавить в множество <tex>A</tex> с сохранением независимости.
}}
 
{{Утверждение
|statement = Пересечение данных матроидов не является матроидом.
|proof =
Не выполняется третье свойство матроидов, см. пример.
 
Дан граф <tex>D=(V,X)</tex>, где <tex>V = \{ 1, 2, 3, 4 \}</tex>, а <tex>X = \{ a=(1,2), b=(2,3), c=(3,4), d=(4,2) \}</tex>, тогда достаточно рассмотреть два множества $A=\{ a,b,c \}$ и $B=\{ b,d \}$, чтобы понять, что не выполняется третье свойство матроидов.
}}
1
правка

Навигация