170
правок
Изменения
→Ориентированное дерево
'''Ориентированное дерево''' (англ. ''arborescence'') {{---}} ацикличный орграф (ориентированный граф, не содержащий циклов), в котором только одна вершина имеет нулевую степень захода (в неё не ведут дуги), а все остальные вершины имеют степень захода <tex>1</tex> (в них ведёт ровно по одной дуге).
}}
Пусть <tex>D = \langle V, A X \rangle </tex> {{---}} ориентированнный граф.
Граф <tex>G</tex> {{---}} неориентированный граф, соответствующий графу <tex>D</tex>.
Тогда рассмотрим два матроида <tex>M_1 = \langle AX, \mathcal{I}_1 \rangle, M_2 = \langle AX, \mathcal{I}_2 \rangle</tex>, где <tex>AX</tex> {{---}} множество ребёр графа.
<tex>M_1</tex> {{---}} [[Примеры_матроидов|графовый матроид]] <tex>G</tex>,
<tex>\mathcal{I}_1 = \{AX' \subseteq AX: AX'</tex> {{---}} лес в <tex>G \}</tex>.
<tex>M_2</tex> {{---}} [[Примеры_матроидов|матроид разбиений]] графа <tex>D</tex>,
<tex>\mathcal{I}_2 = \{AX' \subseteq AX: |\deg^-(v) \cap AX'| \leqslant 1, \forall v \in V \}</tex>. Пересечением данных матроидов являются множества ориентированных деревьевлесов. {{Утверждение|statement = Пересечением данных матроидов является матроид.|proof =Рассмотрим матроид пересечения <tex>M = \langle X, \mathcal{I} \rangle</tex>, <tex>A</tex> {{---}} множество ребер, <tex>\mathcal{I} = \mathcal{I}_1 \cap \mathcal{I}_2</tex> Проверим выполнение аксиом независимости: 1) <tex>\varnothing \in \mathcal{I}</tex> Пустое множество является ориентированным деревом, а значит входит в <tex>\mathcal{I}</tex>. 2) <tex>A \subset B, \ B \in \mathcal{I} \Rightarrow A \in \mathcal{I}</tex>Любой подграф ориентированного леса также является ориентированным лесом, так как во-первых, степень захода каждой вершины в подграфе могла только уменьшится, во-вторых, подграф ацикличного графа {{---}} ацикличен. 3) <tex>A \in \mathcal{I}, \ B \in I, \ \left\vert A \right\vert < \left\vert B \right\vert \Rightarrow \mathcal {9} x \in B \setminus A, \ A \cup \mathcal{f} x \mathcal {g} \in \mathcal{I}</tex> Найдем такое ребро в множестве <tex>B \setminus A</tex>, которое не указывает ни в одну из вершин, в которые указывают ребра из множества <tex>A</tex>.Пусть количество вершин в множестве <tex>A</tex> равно <tex>k</tex>. Тогда количество ребер в <tex>A</tex> равно <tex>k - 1</tex>. Так как <tex>|B| > |A|</tex>, следовательно количество ребер в множестве <tex>B</tex> не меньше <tex>k</tex>.Пусть все ребра из множества <tex>B</tex> ведут в вершины множества <tex>A</tex>, значит в каждую вершину множества <tex>A</tex> входит по одному ребру множества <tex>B</tex>. Тогда возьмем то ребро, которое указывает в корень (в вершину с нулевой степенью захода), получим ориентированное дерево с новым корнем.Пусть не все ребра множества <tex>B</tex> указывают в вершины множества <tex>A</tex>, тогда возьмем то ребро <tex>uv</tex>, которое указывает в вершину не принадлежащую <tex>A</tex>. Покажем, что оно нам подойдет. Если <tex>u \in V(A)</tex>, тогда наше текущее ориентированное дерево пополнится еще одной вершиной и ведущем к ней ребру.Если <tex>u \notin V(A)</tex>, то мы получим еще одно ориентированное дерево.Таким образом, мы нашли ребро в множестве <tex>B \setminus A</tex>, которое можем добавить в множество <tex>A</tex> с сохранением независимости. }}
== См. также==
