497
правок
Изменения
Нет описания правки
Пусть <tex> E = \{1, 2, 3, 4, 5, 6, 7, 8\}</tex>. Матроид Вамоса <tex>V</tex> удобно задать, назвав все его '''зависимые''' множества: это все подмножества <tex>E</tex>, в которых не менее пяти элементов, а также <tex>\{1, 2, 5, 6\}, \{1, 2, 7, 8\}, \{3, 4, 5, 6\}, \{3, 4, 7, 8\}, \{5, 6, 7, 8\}</tex>.
== Доказательство матроидной природы ==
Сначала убедимся в том, что перед нами действительно матроид. Фактически нуждается в проверке лишь тот факт, что если <tex>A</tex> и <tex>B</tex> независимые множества и <tex>|B| = 3</tex>, <tex>|A| = 4</tex>, то в <tex>A</tex> найдется такой элемент <tex>e<tex>, что <tex>B \unite \{e\}</tex> {{---}} независимое множество. Когда <tex>B \subset A</tex>, это очевидно. В противном же случае множество <tex> A \setminus B</tex> содержит по меньшей мере два различных элемента. Обозначим их через <tex>e1</tex> и <tex>e2</tex>. Теперь осталось заметить, что из множеств <tex>B \unite \{e1\}</tex> и <tex>B \unite \{e2\}</tex> хотя бы одно независимое, так как по условию нет двух зависимых множеств из
четырtх элементов, отличающихся одним элементом.
