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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Аксиоматическое определение)
(→‎Аксиоматическое определение)
Строка 2: Строка 2:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
'''Матроид''' <tex>\mathrm{(matroid)}</tex> {{---}} пара <tex>\langle X,I \rangle</tex>, где <tex>X</tex> {{---}} конечное множество, называемое '''носителем матроида''' <tex>\mathrm{\ (ground \ set)}</tex>, а <tex>I</tex> {{---}} некоторое множество подмножеств <tex>X</tex>, называемое семейством '''независимых множеств''' <tex>\mathrm{\ (independent \ sets)}</tex> , то есть <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>
Строка 10: Строка 10:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
'''База матроида''' <tex>\mathrm{(basis)}</tex> {{---}} максимальное по включению независимое множество .
+
'''База матроида''' (англ. ''basis'') {{---}} максимальное по включению независимое множество .
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
'''Зависимое множество''' <tex>\mathrm{\ (dependent \ set)}</tex> {{---}} подмножество носителя матроида, не являющееся независимым.
+
'''Зависимое множество''' (англ. ''dependent'' ''set'')  {{---}} подмножество носителя матроида, не являющееся независимым.
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
'''Цикл матроида''' <tex>\mathrm{(circuit}</tex> {{---}} минимальное по включению зависимое множество.
+
'''Цикл матроида''' (англ. ''circuit'') {{---}} минимальное по включению зависимое множество.
 
}}
 
}}
  

Версия 22:38, 6 мая 2014

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

Определение:
Матроид (англ. matroid) — пара [math]\langle X,I \rangle[/math], где [math]X[/math] — конечное множество, называемое носителем матроида (англ. ground set), а [math]I[/math] — некоторое множество подмножеств [math]X[/math], называемое семейством независимых множеств (англ. independent sets), то есть [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 : B \cup \{x\} \in I[/math]


Определение:
База матроида (англ. basis) — максимальное по включению независимое множество .


Определение:
Зависимое множество (англ. dependent set) — подмножество носителя матроида, не являющееся независимым.


Определение:
Цикл матроида (англ. circuit) — минимальное по включению зависимое множество.


См. также

Источники информации

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