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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition = <tex>M =\; \langle X,I \rangle</tex> - матроид. Тогда '''замыкание (closure)''' множества <tex>A \subset X</tex> - это множество <tex>\langle A \rangle \subset X</tex> такое, что <tex>\langle A \rangle = A \cup {x\; |\; \forall B \subset A : B \in I ,\; B \cup x \notin I}</tex>
 
|definition = <tex>M =\; \langle X,I \rangle</tex> - матроид. Тогда '''замыкание (closure)''' множества <tex>A \subset X</tex> - это множество <tex>\langle A \rangle \subset X</tex> такое, что <tex>\langle A \rangle = A \cup {x\; |\; \forall B \subset A : B \in I ,\; B \cup x \notin I}</tex>
 +
}}
 +
 +
 +
{{Теорема
 +
|statement = Оператор замыкания для матроидов обладает следующими свойствами:
 +
1) <tex>A \subset B \Rightarrow \langle A \rangle \subset \langle B \rangle</tex>
 +
 +
2) <tex>q \notin \langle A \rangle q \in \langle A \cup p \rangle \Rightarrow p \in \langle A \cup q \rangle</tex>
 +
 +
3) <tex>\langle \langle A \rangle \rangle = \langle A \rangle </tex>
 +
|proof =
 
}}
 
}}

Версия 03:37, 12 мая 2011

Определение:
[math]M =\; \langle X,I \rangle[/math] - матроид. Тогда замыкание (closure) множества [math]A \subset X[/math] - это множество [math]\langle A \rangle \subset X[/math] такое, что [math]\langle A \rangle = A \cup {x\; |\; \forall B \subset A : B \in I ,\; B \cup x \notin I}[/math]


Теорема:
Оператор замыкания для матроидов обладает следующими свойствами:

1) [math]A \subset B \Rightarrow \langle A \rangle \subset \langle B \rangle[/math]

2) [math]q \notin \langle A \rangle q \in \langle A \cup p \rangle \Rightarrow p \in \langle A \cup q \rangle[/math]

3) [math]\langle \langle A \rangle \rangle = \langle A \rangle [/math]