„Rendszeroptimalizálás, 12. tétel” változatai közötti eltérés
Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel12}} ==!! Matroidok összege. k-matroid-metszet probléma, ennek bonyolultsága k>3 esetén.== __TOC__ ===Matroidok összege==…” |
Nincs szerkesztési összefoglaló |
||
| 17. sor: | 17. sor: | ||
{| border="1" | {| border="1" | ||
X>Y miatt X<sub>1</sub>>Y<sub>1</sub> és X<sub>2</sub>>Y<sub>2</sub> közül legalább az egyik teljesül, legyen mondjuk az első. M<sub>1</sub> 3. axiómája miatt ∃x∈X<sub>1</sub>-Y<sub>1</sub>: Y<sub>1</sub>∪{x}∈F<sub>1</sub>. Ha x∉Y<sub>2</sub> (∗), akkor x kielégíti a M<sub>1</sub>∨M<sub>2</sub>-re vonatkozó 3. axiómát is. Ha x∈Y<sub>2</sub>, (∗∗), akkor Y<sub>1</sub>∪{x}, Y<sub>2</sub>-{x} is egy jó felbontás és kisebb az (X<sub>2</sub>∩Y<sub>1</sub>)∪(Y<sub>2</sub>∩X<sub>1</sub>) elemszáma, ami ellentmondás. | |||
<br clear="all"> | <br clear="all"> | ||