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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 4: Строка 4:
 
'''Матроид''' — пара <tex>(X,I)</tex>, где <tex>X</tex> — конечное множество, называемое '''носителем матроида''', а <tex>I</tex> — некоторое множество подмножеств <tex>X</tex>, называемое семейством '''независимых множеств''' , то есть <tex>I \subset 2^X </tex>. При этом должны выполняться следующие условия:
 
'''Матроид''' — пара <tex>(X,I)</tex>, где <tex>X</tex> — конечное множество, называемое '''носителем матроида''', а <tex>I</tex> — некоторое множество подмножеств <tex>X</tex>, называемое семейством '''независимых множеств''' , то есть <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</tex> такой, что <tex>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>
 
}}
 
}}
  

Версия 22:47, 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 : B \cup \{x\} \in I[/math]


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


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


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


См. также

Литература

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