Пересечение матроидов, определение, примеры
Версия от 21:42, 9 июня 2015; DariaYakovleva (обсуждение | вклад)
Определение: |
Пусть даны два матроида | и . Пересечением матроидов (англ. matroid intersection) и называется пара , где — носитель исходных матроидов, а .
- Пересечение матроидов не всегда является матроидом.
- Пересечение трех и более матроидов — это NP-полная задача.
Разноцветный лес
графовый матроид, — разноцветный матроид (англ. multicolored matroid) (Множество независимо, если в нём нет двух ребер одного цвета). Тогда их пересечение — это разноцветный лес (англ. rainbow forests).
—![](/wiki/images/thumb/f/fc/Rainbow_forest_DY.png/500px-Rainbow_forest_DY.png)
Пересечение матроидов, база матроида
Утверждение: |
Пересечение данных матроидов не является матроидом. |
Рассмотрим пару , — ребра разноцветного леса, . Данная пара не является матроидом, так как не выполняется третье свойство матроида, то есть и (См. пример 1) |
Двудольный граф
Пусть двудольный граф и заданы два матроида , , где — множество ребёр графа, , . Тогда их пересечение — это множество всевозможных паросочетаний графа.
—Утверждение: |
Пересечение данных матроидов не является матроидом. |
Рассмотрим пару , — носитель, . Данная пара не является матроидом, так как не выполняется третье свойство матроида, то есть и (См. пример 2) |
Ориентированный лес
Определение: |
Ориентированное дерево (англ. arborescence) — ацикличный орграф (ориентированный граф, не содержащий циклов), в котором только одна вершина имеет нулевую степень захода (в неё не ведут дуги), а все остальные вершины имеют степень захода | (в них ведёт ровно по одной дуге).
Пусть графовый матроид , — лес в . — матроид разбиений графа , . Пересечение данных матроидов являются множества ориентированных лесов.
— ориентированнный граф. Граф — неориентированный граф, соответствующий графу . Тогда рассмотрим два матроида , где — множество ребёр графа. —Утверждение: |
Пересечение данных матроидов является матроид. |
Рассмотрим матроид пересечения , — множество ребер,Проверим выполнение аксиом независимости: 1) Пустое множество является ориентированным деревом, а значит входит в .2) Любой подграф ориентированного леса также является ориентированным лесом, так как во-первых, степень захода каждой вершины в подграфе могла только уменьшится, во-вторых, подграф ацикличного графа — ацикличен.3) Пусть количество вершин в множестве Таким образом, мы нашли ребро в множестве равно . Тогда количество ребер в равно . Так как , следовательно количество ребер в множестве не меньше . Пусть все ребра из множества ведут в вершины множества , значит в каждую вершину множества входит по одному ребру множества . Тогда возьмем то ребро, которое указывает в корень (в вершину с нулевой степенью захода), получим ориентированное дерево с новым корнем. Пусть не все ребра множества указывают в вершины множества , тогда возьмем то ребро , которое указывает в вершину не принадлежащую . Покажем, что оно нам подойдет. Если , тогда наше текущее ориентированное дерево пополнится еще одной вершиной и ведущем к ней ребру. Если , то мы получим еще одно ориентированное дерево. , которое можем добавить в множество с сохранением независимости. |
См. также
Источники информации
- Асанов М. О., Баранский В. А., Расин В. В. — Дискретная математика: Графы, матроиды, алгоритмы (глава 4. Матроиды)
- Lecture notes on matroid intersection