Матроид Вамоса — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство матроидной природы)
(Доказательство матроидной природы)
Строка 8: Строка 8:
 
== Доказательство матроидной природы ==
 
== Доказательство матроидной природы ==
  
Сначала убедимся в том, что перед нами действительно матроид. Фактически нуждается в проверке лишь тот факт, что если <tex>A</tex> и <tex>B</tex> независимые множества и <tex>|B| = 3</tex>, <tex>|A| = 4</tex>, то в <tex>A</tex> найдется такой элемент <tex>e<tex>, что <tex>B \cup \{e\}</tex> {{---}} независимое множество. Когда <tex>B \subset A</tex>, это очевидно. В противном же случае множество <tex> A \setminus B</tex> содержит по меньшей мере два различных элемента. Обозначим их через <tex>e1</tex> и <tex>e2</tex>. Теперь осталось заметить, что из множеств <tex>B \cup \{e1\}</tex> и <tex>B \cup \{e2\}</tex> хотя бы одно независимое, так как по условию нет двух зависимых множеств из
+
Сначала убедимся в том, что перед нами действительно матроид. Фактически нуждается в проверке лишь тот факт, что если <tex>A</tex> и <tex>B</tex> независимые множества и <tex>|B| = 3</tex>, <tex>|A| = 4</tex>, то в <tex>A</tex> найдется такой элемент <tex>e</tex>, что <tex>B \cup \{e\}</tex> {{---}} независимое множество. Когда <tex>B \subset A</tex>, это очевидно. В противном же случае множество <tex> A \setminus B</tex> содержит по меньшей мере два различных элемента. Обозначим их через <tex>e1</tex> и <tex>e2</tex>. Теперь осталось заметить, что из множеств <tex>B \cup \{e1\}</tex> и <tex>B \cup \{e2\}</tex> хотя бы одно независимое, так как по условию нет двух зависимых множеств из
 
четырtх элементов, отличающихся одним элементом.
 
четырtх элементов, отличающихся одним элементом.

Версия 13:19, 16 июня 2014

Vamos matroid N.png

Матроид Вамоса или куб Вамоса — это матроид над восьми элементным множеством, который не изоморфен матричному ни над каким полем. Он назван в честь английского математика Питера Вамоса (Peter Vámos), который первым описал его в неопубликованной рукописи в 1968.

Задание матроида

Пусть [math] E = \{1, 2, 3, 4, 5, 6, 7, 8\}[/math]. Матроид Вамоса [math]V[/math] удобно задать, назвав все его зависимые множества: это все подмножества [math]E[/math], в которых не менее пяти элементов, а также [math]\{1, 2, 5, 6\}, \{1, 2, 7, 8\}, \{3, 4, 5, 6\}, \{3, 4, 7, 8\}, \{5, 6, 7, 8\}[/math].

Доказательство матроидной природы

Сначала убедимся в том, что перед нами действительно матроид. Фактически нуждается в проверке лишь тот факт, что если [math]A[/math] и [math]B[/math] независимые множества и [math]|B| = 3[/math], [math]|A| = 4[/math], то в [math]A[/math] найдется такой элемент [math]e[/math], что [math]B \cup \{e\}[/math] — независимое множество. Когда [math]B \subset A[/math], это очевидно. В противном же случае множество [math] A \setminus B[/math] содержит по меньшей мере два различных элемента. Обозначим их через [math]e1[/math] и [math]e2[/math]. Теперь осталось заметить, что из множеств [math]B \cup \{e1\}[/math] и [math]B \cup \{e2\}[/math] хотя бы одно независимое, так как по условию нет двух зависимых множеств из четырtх элементов, отличающихся одним элементом.