Определение матроида

Материал из Викиконспекты
Перейти к: навигация, поиск
НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.

Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.

Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.

Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.

Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

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

Определение:
Матроид (англ. matroid) — пара [math]\langle X,I \rangle[/math], где [math]X[/math] — конечное множество, называемое носителем матроида (англ. ground set), а [math]I[/math] — некоторое множество подмножеств [math]X[/math], называемое семейством независимых множеств (англ. independent sets), то есть [math]I \subset 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] и [math]|A| \gt |B|[/math], то [math] \exists \, x \in A \setminus B \mid B \cup \{x\} \in I[/math]


Определение:
База матроида (англ. base) — максимальное по включению независимое множество.


Определение:
Рангом матроида называется мощность его баз. Ранг тривиального матроида равен нулю.


Определение:
Зависимое множество (англ. dependent set) — подмножество носителя матроида, не являющееся независимым.


Определение:
Цикл матроида (англ. circuit) — минимальное по включению зависимое множество.


Определение:
Матроиды [math]M_1 = \langle X_1,I_1 \rangle[/math] и [math]M_2 = \langle X_2,I_2 \rangle[/math] называются изоморфными (англ. isomorphic matroids), если существует биекция (взаммно-однозначное отображение) [math]\varphi\colon \ X_1 \rightarrow X_2[/math], сохраняющая независимость, то есть множество [math]A \subset I_1[/math] является независимым в матроиде [math]M_1[/math] тогда и только тогда, когда образ этого множества при заданном отображении [math]\varphi(A)[/math] есть независимое множество в матроиде [math]M_2[/math].


См. также

Источники информации