2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Матроид
Сообщение24.04.2010, 17:41 
Никак не могу проверить следующий факт: пусть $(E,F_1)$ и $(E,F_2)$ - матроиды, тогда $(E,F)$, где $F=\{I_1\cup I_2|I_1\in F_1, I_2 \in F_2\}$, -матроид. Подскажите, как это вообще доказывать?

 
 
 
 Матроид
Сообщение25.04.2010, 09:20 
Задача должна решаться по определению. Но что-то не решается...

Свойство наследственности провеяется легко.
Кстати, второе свойство по-разному формулируется. В такой формулировке для матроида $(E,F)$:

$\forall C \subseteq E$, $\forall A,B \subseteq C$, $A,B\in F$ ($A$ и $B$ максимальны по включению в этом смысле) => $|A|=|B|$

у меня получилось показать, что если $A=I'_1\cup I'_2$, $B=I''_1\cup I''_2$, то $|I'_1|=|I''_1|$ и $|I'_2|=|I''_2|$. Но это не помогает.

 
 
 
 Re: Матроид
Сообщение25.04.2010, 11:37 
Странно, я взял аксиоматическое определение из Википедии и проверил три свойства, всё получилось.
Можете в тех терминах сказать, что у вас не получается?

 
 
 
 Re: Матроид
Сообщение25.04.2010, 12:20 
2ая аксиома оттуда - это наследственность. С ней все понятно. 3я эквивалентна тому что я говорил.
Но если в тех терминах:
Если взять 2 множества $A,B\subseteq E$, $A,B\in F$, $|A|>|B|.$ Нужно показать, что существует $x\in A\setminus B$, такой, что $B \cup \{x\} \in F$.
$A$ и $B$ представимы в виде: $A=I'_1\cup I'_2$, $B=I''_1\cup I''_2$, где $I'_1,I''_1\in F_1$, $I'_2,I''_2\in F_2$.
И никаких идей, где взять этот $x$.
Кстати, верно ли, что либо $|I'_1|>|I''_1|$,либо $|I'_2|>|I''_2|$?

 
 
 
 Re: Матроид
Сообщение25.04.2010, 17:49 
cyb12 в сообщении #313094 писал(а):
Кстати, верно ли, что либо $|I'_1|>|I''_1|$,либо $|I'_2|>|I''_2|$?


Неверно. Например, если $|I'_1|=|I'_2|=3$, $I'_1$ и $I'_2$ не пересекаются, $I''_1=I''_2$, $|I''_1|=4$.
Непонятно как пользоваться тем, что исходные две пары -- матроиды.

 
 
 
 Re: Матроид
Сообщение26.04.2010, 01:27 
Вторая аксиома гарантирует, что множество $I_1'$ можно заменить на $I_1' \setminus I_2'$ так, что условие $A=I_1'\cup I_2'$ сохранится, но при этом будет $I_1'\cap I_2' = \varnothing$, и аналогично с $I''_1$. После этого одно из приведенных вами неравенств будет верно. Для соответствующей пары и применяем аксиому 3.

 
 
 
 Re: Матроид
Сообщение26.04.2010, 09:43 
Cave, спасибо!

 
 
 
 Re: Матроид
Сообщение26.04.2010, 20:49 
Однако.
Если применить аксиому 3 для новых $|I'_1|>|I''_1|$, то получим, что существует $x\in I'_1\setminus I''_1$, т.ч. $\{x\}\cup I''_1 \in F_1.$ И тогда $\{x\}\cup I''_1 \cup I''_2 \in F$ . Но не факт, что $x\in A\setminus B$.Как это показать? Возможно же, что $x \in I''_2$.

 
 
 
 Re: Матроид
Сообщение26.04.2010, 22:06 
Тогда такой $x$ не будет искомым, однако его можно добавить к $I_1''$, при этом мощность этого множества увеличится на 1, а множество $B$ не изменится никак. Значит, мы вновь приходим к такой же ситуации, и процесс можно повторить (для строго рассуждения примените индукцию). В конце будет невозможной ситуация, что $x\in I_2''$, он и будет искомым.

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group