http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=188.162.64.210&*Викиконспекты - Вклад участника [ru]2026-05-25T21:43:57ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BC%D0%B0%D1%82%D1%80%D0%BE%D0%B8%D0%B4%D0%B0&diff=73963Определение матроида2020-04-21T21:52:13Z<p>188.162.64.210: /* Аксиоматическое определение */</p>
<hr />
<div>== Аксиоматическое определение ==<br />
{{Определение<br />
|id=def_matroid<br />
|definition=<br />
'''Матроид''' (англ. ''matroid'') {{---}} пара <tex>\langle X,I \rangle</tex>, где <tex>X</tex> {{---}} конечное множество, называемое '''носителем матроида''' (англ. ''ground'' ''set''), а <tex>I</tex> {{---}} некоторое множество подмножеств <tex>X</tex>, называемое семейством '''независимых множеств''' (англ. ''independent'' ''sets''), то есть <tex>I \subset 2^X </tex>. При этом должны выполняться следующие условия:<br />
# <tex>\varnothing \in I</tex><br />
# если <tex>A \in I </tex> и <tex> B \subset A</tex>, то <tex>B \in I</tex><br />
# если <tex>A,B \in I</tex> и <tex>|A| > |B|</tex>, то <tex> \exists \, x \in A \setminus B \mid B \cup \{x\} \in I</tex><br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
'''База матроида''' (англ. ''base'') {{---}} максимальное по включению независимое множество.<br />
}}<br />
<br />
{{Определение<br />
|id=def_rank_of_matroid<br />
|definition=<br />
'''Рангом''' матроида называется мощность его баз. Ранг тривиального матроида равен нулю.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
'''Зависимое множество''' (англ. ''dependent'' ''set'') {{---}} подмножество носителя матроида, не являющееся независимым.<br />
}}<br />
{{Определение<br />
|definition=<br />
'''Цикл матроида''' (англ. ''circuit'') {{---}} минимальное по включению зависимое множество.<br />
}}<br />
<br />
{{Определение<br />
|id = def5<br />
|definition=<br />
Матроиды <tex>M_1 = \langle X_1,I_1 \rangle</tex> и <tex>M_2 = \langle X_2,I_2 \rangle</tex> называются '''изоморфными''' (англ. ''isomorphic matroids''), если существует биекция (взаммно-однозначное отображение) <tex>\varphi\colon \ X_1 \rightarrow X_2</tex>, сохраняющая независимость, то есть множество <tex>A \subset I_1</tex> является независимым в матроиде <tex>M_1</tex> тогда и только тогда, когда образ этого множества при заданном отображении <tex>\varphi(A)</tex> есть независимое множество в матроиде <tex>M_2</tex>.<br />
}}<br />
<br />
==См. также==<br />
* [[Примеры матроидов|Примеры матроидов]]<br />
* [[Аксиоматизация матроида базами|Аксиоматизация матроида базами]]<br />
* [[Аксиоматизация матроида циклами|Аксиоматизация матроида циклами]]<br />
== Источники информации ==<br />
<br />
*''Асанов М. О., Баранский В. А., Расин В. В.'' - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br />
*[[wikipedia:Matroid | Wikipedia {{---}} Matroid]]<br />
*[[wikipedia:ru:Матроид | Википедия {{---}} Матроид]]<br />
<br />
[[Категория:Алгоритмы и структуры данных]]<br />
[[Категория:Матроиды]]<br />
[[Категория:Основные факты теории матроидов]]</div>188.162.64.210