Редактирование: Определение матроида

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
== Аксиоматическое определение ==
 
== Аксиоматическое определение ==
 
{{Определение
 
{{Определение
|id=def_matroid
 
 
|definition=
 
|definition=
 
'''Матроид''' (англ. ''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>. При этом должны выполняться следующие условия:
 
'''Матроид''' (англ. ''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>. При этом должны выполняться следующие условия:
 
# <tex>\varnothing \in I</tex>
 
# <tex>\varnothing \in I</tex>
 
# если <tex>A \in I </tex> и <tex> B \subset A</tex>, то <tex>B \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>
+
# если <tex>A,B \in I</tex> и <tex>|A| > |B|</tex>, то <tex> \exists \, x \in A \setminus B : B \cup \{x\} \in I</tex>
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''База матроида''' (англ. ''base'') {{---}} максимальное по включению независимое множество.
+
'''База матроида''' (англ. ''basis'') {{---}} максимальное по включению независимое множество .
 
}}
 
}}
 
{{Определение
 
|id=def_rank_of_matroid
 
|definition=
 
'''Рангом''' матроида называется мощность его баз. Ранг тривиального матроида равен нулю.
 
}}
 
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Строка 26: Строка 18:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Цикл матроида''' (англ. ''cicruit'') {{---}} минимальное по включению зависимое множество.
+
'''Цикл матроида''' (англ. ''circuit'') {{---}} минимальное по включению зависимое множество.
}}
 
 
 
{{Определение
 
|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>.
 
 
}}
 
}}
  
Строка 41: Строка 27:
 
== Источники информации ==
 
== Источники информации ==
  
*''Асанов М. О., Баранский В. А., Расин В. В.'' - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''
+
*''Асанов М. О., Баранский В. А., Расин В. В.'' - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br />
*[[wikipedia:Matroid | Wikipedia {{---}} Matroid]]
+
*[[wikipedia:Matroid | Wikipedia {{---}} Matroid]]<br />
 
*[[wikipedia:ru:Матроид | Википедия {{---}} Матроид]]
 
*[[wikipedia:ru:Матроид | Википедия {{---}} Матроид]]
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Матроиды]]
 
[[Категория:Матроиды]]
[[Категория:Основные факты теории матроидов]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: