Изменения

{{Определение|id=def_matroid|definition='''Матроид''' — (англ. ''matroid'') {{---}} пара <mathtex>(\langle X,I)\rangle</mathtex>, где <mathtex>X</mathtex> — {{---}} конечное множество, называемое '''носителемматроида''' (англ. ''ground'' ''set''), а <mathtex>I</mathtex> — {{---}} некоторое множество подмножеств <mathtex>X</mathtex>, называемоесемейством '''независимыхмножеств''' множеств (англ. ''independent'' ''sets''), то есть <mathtex>I \subset 2^X </mathtex>. При этом должнывыполняться следующие условия:# <tex>\varnothing \in I</tex># если <tex>A \in I </tex> и <tex> B \subset A</tex>, то <tex>B \in I</tex># если <tex>A,B \in I</tex> и <tex>|A| > |B|</tex>, то <tex> \exists \, x \in A \setminus B \mid B \cup \{x\} \in I</tex>}}

# <math>\varnothing \in I</math>{{Определение# Если <math>A \in I </math> и <math> B \subset A</math>, то <math>B \in I</math>|definition=# Если <math>A,B \in I</math> и [[мощность множества|мощность]] A больше [[мощность множества|мощности]] B, то существует <math>x \in A \setminus B</math> такой, что <math>B \cup \'''База матроида''' (англ. ''base'') {{x\---}} максимальное по включению независимое множество.}} \in I</math>

{{Определение|id=def_rank_of_matroid|definition='''БазамиРангом''' матроида называются максимальные по включению независимые множестваназывается мощность его баз.Подмножества <math>X \notin I</math> называются ''зависимыми'' множествамиРанг тривиального матроида равен нулю.Минимальные по включению зависимые множества называются ''циклами'' матроида, это понятие используется в альтернативном определении матроида.}}

{{Определение|definition== '''Зависимое множество''' (англ. ''dependent'' ''set'') {{---}} подмножество носителя матроида, не являющееся независимым.}}{{Определение в терминах правильного замыкания =|definition='''МатроидЦикл матроида''' (англ. ''cicruit'' — пара ) {{---}} минимальное по включению зависимое множество.}} {{Определение|id = def5|definition=Матроиды <mathtex>(XM_1 = \langle X_1,I_1 \rangle</tex> и <tex>M_2 = \langle X_2, AI_2 \to Hrangle</tex> называются '''изоморфными''' (Aангл. ''isomorphic matroids''), если существует биекция (взаммно-однозначное отображение)<tex>\varphi\colon \ X_1 \rightarrow X_2</mathtex>, где сохраняющая независимость, то есть множество <mathtex>XA \subset I_1</mathtex> — конечное множествоявляется независимым в матроиде <tex>M_1</tex> тогда и только тогда, называемое носителемматроида, а когда образ этого множества при заданном отображении <mathtex>A \to Hvarphi(A)</mathtex> — правильное замыкание на есть независимое множество в матроиде <mathtex>(2^X,\le)M_2</mathtex>.}} ==См. также==* [[Примеры матроидов|Примеры матроидов]]* [[Аксиоматизация матроида базами|Аксиоматизация матроида базами]]* [[Аксиоматизация матроида циклами|Аксиоматизация матроида циклами]]== Источники информации == *''Асанов М. О., Баранский В. А., Расин В. В.'' - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''*[[wikipedia:Matroid | Wikipedia {{---}} Matroid]]*[[wikipedia:ru:Матроид | Википедия {{---}} Матроид]] [[Категория:Алгоритмы и структуры данных]][[Категория:Матроиды]][[Категория:Основные факты теории матроидов]]