Примеры матроидов — различия между версиями
(→Универсальный матроид) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 3 промежуточные версии 3 участников) | |||
Строка 15: | Строка 15: | ||
# <tex>A \subset B, \ B \in I \Rightarrow A \in I</tex> | # <tex>A \subset B, \ B \in I \Rightarrow A \in I</tex> | ||
#:Если в <tex>B</tex> все элементы разного цвета, то и в <tex>A \subset B</tex> это будет выполняться. | #:Если в <tex>B</tex> все элементы разного цвета, то и в <tex>A \subset B</tex> это будет выполняться. | ||
− | # <tex>A \in I, \ B \in I, \ \left\vert A \right\vert < \left\vert B \right\vert \Rightarrow \mathcal \exists x \in B \setminus A, \ A \cup \ | + | # <tex>A \in I, \ B \in I, \ \left\vert A \right\vert < \left\vert B \right\vert \Rightarrow \mathcal \exists x \in B \setminus A, \ A \cup \{ x \} \in I</tex> |
− | #:В каждом из множеств <tex>A</tex> и <tex>B</tex> все элементы разных цветов. Так как <tex>\left\vert A \right\vert < \left\vert B \right\vert</tex>, значит в <tex>B</tex> есть хотя бы один элемент <tex>x</tex> такого цвета, которого нет среди элементов множества <tex>A</tex>, таким образом <tex>A \cup \ | + | #:В каждом из множеств <tex>A</tex> и <tex>B</tex> все элементы разных цветов. Так как <tex>\left\vert A \right\vert < \left\vert B \right\vert</tex>, значит в <tex>B</tex> есть хотя бы один элемент <tex>x</tex> такого цвета, которого нет среди элементов множества <tex>A</tex>, таким образом <tex>A \cup \{ x \} \in I</tex> |
}} | }} | ||
Строка 63: | Строка 63: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | Пусть <tex>V</tex> {{---}} векторное пространство над телом <tex>F</tex>, пусть набор векторов <tex>V_i = \ | + | Пусть <tex>V</tex> {{---}} векторное пространство над телом <tex>F</tex>, пусть набор векторов <tex>V_i = \{ v_1, \ \dots, \ v_n\}</tex> из пространства <tex>V</tex> является носителем <tex>X</tex>. Элементами независимого множества <tex>I</tex> данного матроида являются множества линейно независимых векторов из набора <tex>v_ 1, \ \dots, \ v_n</tex>. |
Тогда <tex>M = \langle V_i, I \rangle </tex>, называется '''матричным матроидом''' (англ. ''vector matroid'') | Тогда <tex>M = \langle V_i, I \rangle </tex>, называется '''матричным матроидом''' (англ. ''vector matroid'') | ||
}} | }} | ||
Строка 83: | Строка 83: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | Пусть <tex>G = \langle X, Y, E \rangle</tex> {{---}} двудольный граф. <tex>I = \ | + | Пусть <tex>G = \langle X, Y, E \rangle</tex> {{---}} двудольный граф. <tex>I = \{ A \subset X \mid \exists </tex> паросочетание <tex> P</tex>, покрывающее <tex>A \} </tex>. Тогда <tex>M = \langle X, I \rangle </tex> называют '''трансверсальным матроидом''' (англ. ''transversal matroid''). |
}} | }} | ||
Текущая версия на 19:39, 4 сентября 2022
Содержание
Разноцветный матроид
Определение: |
Пусть | — множество элементов, каждый из которых раскрашен в некоторый цвет. Множество , если все элементы множества разного цвета. Тогда называется разноцветным матроидом (англ. multicolored matroid).
Утверждение: |
Разноцветный матроид является матроидом. |
Докажем аксиомы независимости для .
|
Универсальный матроид
Определение: |
Универсальным матроидом (англ. uniform matroid) называют объект | , где
Утверждение: |
Универсальный матроид является матроидом. |
Проверим выполнение аксиом независимости:
|
Графовый матроид
Определение: |
Пусть | — неориентированный граф. Тогда , где состоит из всех ацикличных множеств ребер (то есть являющихся лесами), называют графовым (графическим) матроидом (англ. graphic matroid).
Утверждение: |
Графовый матроид является матроидом. |
Проверим выполнение аксиом независимости:
|
Матричный матроид
Определение: |
Пусть | — векторное пространство над телом , пусть набор векторов из пространства является носителем . Элементами независимого множества данного матроида являются множества линейно независимых векторов из набора . Тогда , называется матричным матроидом (англ. vector matroid)
Утверждение: |
Матричный матроид является матроидом. |
Проверим выполнение аксиом независимости:
|
Трансверсальный матроид
Определение: |
Пусть | — двудольный граф. паросочетание , покрывающее . Тогда называют трансверсальным матроидом (англ. transversal matroid).
Утверждение: |
Трансверсальный матроид является матроидом. |
Проверим выполнение аксиом независимости:
|
Матроид паросочетаний
Определение: |
Пусть | — неориентированный граф. паросочетание , покрывающее . Тогда называют матроидом паросочетаний (англ. matching matroid).
Утверждение: |
Матроид паросочетаний является матроидом. |
Проверим выполнение аксиом независимости:
|
Матроид разбиений
Определение: |
Пусть | , при этом , , и — положительные целые числа. . Тогда называют матроидом разбиений (англ. partition matroid)
Утверждение: |
Матроид разбиений является матроидом. |
Проверим выполнение аксиом независимости:
|
Бинарный матроид
Определение: |
Матроид изоморфен некоторому векторному матроиду над этим полем. | представим над полем , если он
Определение: |
Бинарный матроид (англ. binary matroid) — матроид, представимый над полем целых чисел по модулю | .
Утверждение: |
Графовый матроид является бинарным. |
Составим матрицу инцидентности для графа . Строки этой матрицы соответствуют вершинам графа, а столбцы — ребрам.
Необходимо доказать, что если мы возьмем множество ребер , то множество столбцов матрицы инцидентности, соответствующее выбранным ребрам, линейно-независимо, и наоборот, если мы возьмем линейно-независимое множество столбцов, то соответствующее ему множество ребер, не будет образовывать цикла. Докажем эквивалентное утверждение: столбцы линейно-зависимы тогда и только тогда, когда соответствующие им ребра графа содержат цикл.Пусть столбцы линейно-зависимы, докажем, что соответствующие ребра графа содержат цикл. Если некоторые столбцы матрицы линейно-зависимы, то среди них можно выделить столбцы с нулевой суммой. Есть два варианта:
Пусть на множестве ребер есть цикл, докажем линейную-зависимость соответствующих столбцов. Если среди данного множества ребер есть петля, то соответствующий ей столбец будет нулевым (по построению матрицы инцидентности), он и обеспечивает линейную-зависимость всего набора векторов. Если петли нет, то рассмотрим столбцы, отвечающие ребрам простого цикла. Любая строка матрицы содержит в этих столбцах ровно 2 единицы. Поэтому сумма по модулю указанных столбцов равна нулевому столбцу, что означает линейную зависимость исходного множества столбцов. |
Другие матроиды
Несложно доказать, что следующие конструкции тоже являются матроидами.
Определение: |
Матроид с выкинутым элементом. Пусть | — матроид. Определим . Для любых и получившаяся конструкция является матроидом.
Определение: |
Матроид, стянутый по элементу. Пусть | — матроид. Определим . Для любых и , таких что получившаяся конструкция является матроидом.
Определение: |
Пусть | — матроид. Обозначим как следующую констркуцию: , тогда называют урезанным матроидом.
Определение: |
Полный матроид — матроид | такой, что .
Определение: |
Тривиальный матроид — матроид | такой, что .
См. также
Источники
- Асанов М. О., Баранский В. А., Расин В. В. — Дискретная математика: Графы, матроиды, алгоритмы (глава 4. Матроиды)
- Уилсон Р. — Введение в теорию графов (глава 9. Теория матроидов)
- Примеры матроидов
- Wikipedia — Matroid
- Википедия — Матроид