Русская Википедия:Матроид

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Матроид — классификация подмножеств некоторого множества, представляющая собой обобщение идеи независимости элементов, аналогично независимости элементов линейного пространства, на произвольное множество.

Аксиоматическое определение

Матроид — пара <math>(X,I)</math>, где <math>X</math> — конечное множество, называемое носителем матроида, а <math>I</math> — некоторое множество подмножеств <math>X</math>, называемое семейством независимых множеств , то есть <math>I \subset</math> <math> 2^X </math>. При этом должны выполняться следующие условия:

  1. Пустое множество является независимым множеством, т.е. <math>\varnothing \in I</math>.
  2. Все подмножества независимого множества также независимые множества, т.е. если <math>A \in I </math> и <math> B \subset A</math>, то <math>B \in I</math>.
  3. Если <math>A,B \in I</math> и мощность A больше мощности B, то существует <math>x \in A \setminus B</math> такой, что <math>B \cup \{x\} \in I</math>.

Базами матроида называются максимальные по включению независимые множества. Подмножества <math>X</math>, не принадлежащие <math>I</math>, называются зависимыми множествами. Минимальные по включению зависимые множества называются циклами матроида. Это понятие используется в альтернативном определении матроида.

Определение в терминах циклов

Матроид — пара <math>(X,C)</math>, где <math>X</math> — носитель матроида, а <math>C</math> — семейство непустых подмножеств <math>X</math>, называемое множеством циклов матроида, для которых выполняются следующие условия:[1]

  1. Ни один цикл не является подмножеством другого.
  2. Если <math>x \in C_1 \cap C_2</math>, то <math>C_1 \cup C_2 \setminus \{x\}</math> содержит цикл.

Определение в терминах правильного замыкания

Пусть <math>(P, \le)</math> — частично упорядоченное множество. <math>H: P \to P</math> — замыкание в <math>(P, \le)</math>, если

  1. Для любого x из P : <math>H(x) \ge x</math>.
  2. Для любых x, y из P : <math>x \le y \Rightarrow H(x) \le H(y)</math>.
  3. Для любого x из P : <math>H\big(H(x)\big) = H(x)</math>.

Рассмотрим <math>(P, \le) = (2^S, \le)</math> случай, когда частично упорядоченное множество — булева алгебра. Пусть <math>A \to H(A)</math> — замыкание <math>A \subset S</math>.

  1. Замыкание правильно (аксиома правильного замыкания), если <math>(p \not \in A, p \in H(A \cup \{ q \}) ) \Rightarrow q \in H(A \cup \{ p \})</math>
  2. для любого <math>A \subset S</math> существует такое <math>B \subset A</math>, что
    1. <math> |B|<+\infty </math>
    2. <math> H\left(B\right)=H\left(A\right) </math>

Пара <math>(S, A\to H(A))</math>, где <math>A \to H(A)</math> — правильное замыкание на <math>(2^S,\le)</math>, называется матроидом.

Примеры

  1. Универсальный матроид Un k. Множество X имеет мощность n, независимыми множествами являются подмножества мощностью не больше k. Базы — подмножества мощностью k.
  2. Матроид циклов графа. Множество X — множество ребер графа, независимые множества — ациклические подмножества этих ребер, циклы — простые циклы графа. Базами являются остовные леса графа. Матроид называется графическим, если он является матроидом циклов некоторого графа.[2]
  3. Матроид подмножеств множества ребер графа, таких что удаление подмножества оставляет граф связным.
  4. Матроид коциклов графа. Множество X — множество ребер, коциклы — минимальные множества, удаление которых приводит к потере связности графа. Матроид называется кографическим, если он является матроидом коциклов некоторого графа.[2]
  5. Матричный матроид. Семейство всех линейно независимых подмножеств любого конечного множества векторов произвольного непустого векторного пространства является матроидом.

Определим множество E, как множество состоящее из {1, 2, 3, .., n} — номеров столбцов некоторой матрицы, а множество I, как множество состоящее из подмножеств E, таких, что векторы, определяемые ими, являются линейно независимыми над полем вещественных чисел R. Зададимся вопросом — какими свойствами обладает построенное множество I?

  1. Множество I непусто. Даже если исходное множество E было пусто — E = ∅, то I будет состоять из одного элемента — множества, содержащего пустое. I = { {∅} }.
  2. Любое подмножество любого элемента множества I также будет элементом этого множества. Это свойство понятно — если некоторый набор векторов линейно независим над полем, то линейно независимым будет также любой его поднабор.
  3. Если A, B ∈ I, причем |A| = |B| + 1, тогда существует элемент x ∈ A − B , такой что B ∪ {x} ∈ I.

Докажем, что в рассмотренном примере множество линейно независимых столбцов действительно является матроидом. Для этого достаточно доказать третье свойство из определения матроида. Проведем доказательство методом от противного.

Доказательство. Пусть A, B ∈ I и |A| = |B| + 1. Пусть W будет пространством векторов, охватываемым A ∪ B . Понятно, что его размерность будет не менее |A|. Предположим, что B ∪ {x} будет линейно зависимо для всех x ∈ A − B (то есть третье свойство не будет выполняться). Тогда B образует базис в пространстве W. Из этого следует, что |A| ≤ dim W ≤ |B|. Но так как по условию A и B состоят из линейно независимых векторов и |A| > |B|, получаем противоречие. Такое множество векторов будет являться матроидом.

Дополнительные понятия

  • Двойственным данному матроиду называется матроид, носитель которого совпадает с носителем данного матроида, а базы — дополнения баз данного матроида до носителя. То есть X* = X, а множество баз двойственного матроида — это множество таких B*, что B* = X \ B, где B — база данного матроида.
  • Циклом (или цепью) в матроиде называется такое множество A ⊂ X, что A ∉ I, и для любого B ⊂ A, если B ≠ A, то B ∈ I
  • Рангом матроида называется мощность его баз. Ранг тривиального матроида равен нулю.

Матроид Фано

Файл:Fano plane.svg
Матроид Фано

Матроиды с маленьким числом элементов часто изображают в виде диаграмм. Точки — это элементы основного множества, а кривые «протянуты» через каждую трёхэлементную цепь. Диаграмма показывает 3-ранговый матроид, называемый матроидом Фано, пример, который появился в 1935 в статье Уитни.

Название возникло из того факта, что матроид Фано представляет собой проективную плоскость второго порядка, известную как плоскость Фано, чьё координатное поле — это двухэлементное поле. Это означает, что матроид Фано — это векторный матроид, связанный с семью ненулевыми векторами в трехмерном векторном пространстве над полем двух элементов.

Из проективной геометрии известно, что матроид Фано непредставим произвольным множеством векторов в вещественном или комплексном векторном пространстве (или в любом векторном пространстве над полем, чьи характеристики отличаются от 2).

Теоремы

  • Все базы матроида имеют одинаковую мощность.
  • Матроид однозначно задается носителем и базами.
  • Цикл не может быть подмножеством другого цикла.
  • Если <math>C_1</math> и <math>C_2</math> — циклы, то для любого <math>x \in C_1 \cap C_2 : C_1 \cup C_2 \setminus \{x\}</math> содержит цикл.
  • Если <math>B</math> — база и <math>x \notin B</math>, то <math>B \cup \{x\}</math> содержит ровно один цикл.

Применение

Литература

Ссылки и примечания

https://web.archive.org/web/20080619011117/http://rain.ifmo.ru/cat/view.php/theory/unsorted/matroids-2004 Шаблон:Примечания

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Ф. Харари. Теория графов, с. 57.
  2. ↑ 2,0 2,1 Ф. Харари. Теория графов, с. 186.
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Матроид&oldid=10350536