Изменения

'''Матроид''' — (англ. ''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>. При этом должнывыполняться следующие условия:# <mathtex>\varnothing \in I</mathtex># Если если <mathtex>A \in I </mathtex> и <mathtex> B \subset A</mathtex>, то <mathtex>B \in I</mathtex># Если если <mathtex>A,B \in I</mathtex> и мощность <tex>|A больше мощности | > |B|</tex>, то существует <mathtex>\exists \, x \in A \setminus B</math> такой, что <math>\mid B \cup \{x\} \in I</mathtex>

'''МатроидомБаза матроида''' называется непустое множество <math>E</math> вместе с [[Оператор_замыкания_для_матроидов | оператором замыкания]]<math>A \to \langle A \rangle</math> такое, что#<math>\forall p,q \in E</math> и <math>A \subset E</math> из <math>q \notin \langle A \rangle</math> и <math> q \in \langle A \cup p \rangle \Rightarrow p \in \langle A \cup q \rangle</math>#<math>\forall A \subset E</math> существует такое (англ. ''base'') {{---}} максимальное по включению независимое множество <math>B \subset A</math>, что <math>\langle A \rangle = \langle B \rangle </math>.

{{Определение|id=def_rank_of_matroid|definition= Литература '''Рангом''' матроида называется мощность его баз. Ранг тривиального матроида равен нулю.}} {{Определение|definition='''Зависимое множество''' (англ. ''dependent'' ''set'') {{---}} подмножество носителя матроида, не являющееся независимым.}}{{Определение|definition='''Цикл матроида''' (англ. ''cicruit'') {{---}} минимальное по включению зависимое множество.}} {{Определение|id = def5|definition=Матроиды <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>.}} ==См. также==* [[Примеры матроидов|Примеры матроидов]]* [[Аксиоматизация матроида базами|Аксиоматизация матроида базами]]* [[Аксиоматизация матроида циклами|Аксиоматизация матроида циклами]]== Источники информации == *''Асанов М. О., Баранский В. А., Расин В. В.'' - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br />*[[wikipedia:Matroid | Wikipedia {{---}} Matroid]]*[[wikipedia:ru:Матроид | Википедия {{---}} Матроид]] [[Категория:Алгоритмы и структуры данных]][[Категория:Матроиды]][[Категория:Основные факты теории матроидов]]