Определение матроида — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 2: Строка 2:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
'''Матроид''' — пара <math>(X,I)</math>, где <math>X</math> — конечное множество, называемое носителем
+
'''Матроид''' — пара <tex>(X,I)</tex>, где <tex>X</tex> — конечное множество, называемое носителем
−
матроида, а <math>I</math> — некоторое множество подмножеств <math>X</math>, называемое
+
матроида, а <tex>I</tex> — некоторое множество подмножеств <tex>X</tex>, называемое
−
семейством ''независимых'' множеств , то есть <math>I \subset 2^X </math>. При этом должны
+
семейством ''независимых'' множеств , то есть <tex>I \subset 2^X </tex>. При этом должны
 
выполняться следующие условия:
 
выполняться следующие условия:
−
# <math>\varnothing \in I</math>
+
# <tex>\varnothing \in I</tex>
−
# Если <math>A \in I </math> и <math> B \subset A</math>, то <math>B \in I</math>
+
# Если <tex>A \in I </tex> и <tex> B \subset A</tex>, то <tex>B \in I</tex>
−
# Если <math>A,B \in I</math> и мощность A больше мощности B, то существует <math>x \in A \setminus B</math> такой, что <math>B \cup \{x\} \in I</math>
+
# Если <tex>A,B \in I</tex> и <tex>|A| > |B|</tex>, то <tex> \exists \, x \in A \setminus B</tex> такой, что <tex>B \cup \{x\} \in I</tex>
 
}}
 
}}
  
−
== Определение в терминах правильного замыкания ==
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
'''Матроидом''' называется непустое множество <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> существует такое множество <math>B \subset A</math>, что <math>\langle A \rangle = \langle B \rangle </math>
+
{{Определение
 +
|definition=
 +
'''Зависимое множество''' - подмножество носителя матроида, не являющееся независимым.
 +
}}
 +
{{Определение
 +
|definition=
 +
'''Цикл матроида''' - минимальное по включению зависимое множество.
 +
}}
 +
{{Определение
 +
|definition=
 +
'''Ранг матроида''' - мощность баз данного матроида.
 +
}}
 +
 
 +
==Определение в терминах циклов==
 +
{{Определение
 +
|definition=
 +
'''Матроид''' - пара <tex>(X, C)</tex>, где <tex>X</tex> - носитель матроида, <tex>C</tex> - семейство подмножеств <tex>X</tex>, называемое множеством '''циклов матроида''', для которых выполняются условия:
 +
#<tex>\varnothing \notin C</tex>
 +
#Если <tex>C_1, C_2 \in C</tex> и <tex>C_1 \subset C_2</tex>, то <tex>C_1 = C_2</tex>
 +
#Если <tex>C_1, C_2 \in C, \, C_1 \ne C_2, \, x \in C_1 \cap C_2</tex>, то <tex>\exists \, C_3 \in C : C_3 \subset (C_1 \cup C_3 \setminus x)</tex>
 
}}
 
}}
−
== Дополнительные понятия ==
 
−
*'''Базами''' матроида называются максимальные по включению независимые множества.
 
−
*'''Рангом''' матроида называется мощность его баз. Ранг тривиального матроида равен нулю.
 
−
*'''Зависимое множество''' - подмножество носителя, не являющееся независимым.
 
−
*'''Циклами''' матроида называются минимальные по включению зависимые множества.
 
  
 +
==Определение в терминах баз==
 +
{{Определение
 +
|definition=
 +
'''Матроид''' - пара <tex>(X, B)</tex>, где <tex>X</tex> - носитель матроида, <tex>B</tex> - семейство подмножеств <tex>X</tex>, называемое множеством '''баз матроида''', для которых выполняются условия:
 +
#<tex>B \ne \varnothing</tex>
 +
#Если <tex>B_1, B_2 \in B</tex> и <tex>B_1 \ne B_2</tex>, то <tex>B_1 \not\subset B_2</tex> и <tex>B_2 \not\subset B_1</tex>
 +
#Если <tex>B_1, B_2 \in B</tex>, то <tex>\forall \, b_1 \in B_1 \: \exists \, b_2 \in B_2 : (B_1 \setminus b_1) \cup b_2 \in B</tex>
 +
}}
 
== Литература ==
 
== Литература ==
 
''Асанов М. О., Баранский В. А., Расин В. В.'' - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br />
 
''Асанов М. О., Баранский В. А., Расин В. В.'' - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br />

Версия 22:19, 26 июня 2011

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

Определение:
Матроид — пара [math](X,I)[/math], где [math]X[/math] — конечное множество, называемое носителем

матроида, а [math]I[/math] — некоторое множество подмножеств [math]X[/math], называемое семейством независимых множеств , то есть [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[/math] такой, что [math]B \cup \{x\} \in I[/math]


Определение:
База матроида - максимальное по включению независимое множество.


Определение:
Зависимое множество - подмножество носителя матроида, не являющееся независимым.


Определение:
Цикл матроида - минимальное по включению зависимое множество.


Определение:
Ранг матроида - мощность баз данного матроида.


Определение в терминах циклов

Определение:
Матроид - пара [math](X, C)[/math], где [math]X[/math] - носитель матроида, [math]C[/math] - семейство подмножеств [math]X[/math], называемое множеством циклов матроида, для которых выполняются условия:
  1. [math]\varnothing \notin C[/math]
  2. Если [math]C_1, C_2 \in C[/math] и [math]C_1 \subset C_2[/math], то [math]C_1 = C_2[/math]
  3. Если [math]C_1, C_2 \in C, \, C_1 \ne C_2, \, x \in C_1 \cap C_2[/math], то [math]\exists \, C_3 \in C : C_3 \subset (C_1 \cup C_3 \setminus x)[/math]


Определение в терминах баз

Определение:
Матроид - пара [math](X, B)[/math], где [math]X[/math] - носитель матроида, [math]B[/math] - семейство подмножеств [math]X[/math], называемое множеством баз матроида, для которых выполняются условия:
  1. [math]B \ne \varnothing[/math]
  2. Если [math]B_1, B_2 \in B[/math] и [math]B_1 \ne B_2[/math], то [math]B_1 \not\subset B_2[/math] и [math]B_2 \not\subset B_1[/math]
  3. Если [math]B_1, B_2 \in B[/math], то [math]\forall \, b_1 \in B_1 \: \exists \, b_2 \in B_2 : (B_1 \setminus b_1) \cup b_2 \in B[/math]

Литература

Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Определение_матроида&oldid=10266»