Tóth Krisztián Dávid, 2017. május 24., 05:59-n

2017-05-24T05:59:55Z

← Régebbi változat		A lap 2017. május 24., 07:59-kori változata
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> (&lowast;), akkor x kielégíti a M<sub>1</sub>&or;M<sub>2</sub>-re vonatkozó 3. axiómát is. Ha x∈Y<sub>2</sub>, (&lowast;&lowast;), 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.		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> (&lowast;), akkor x kielégíti a M<sub>1</sub>&or;M<sub>2</sub>-re vonatkozó 3. axiómát is. Ha x∈Y<sub>2</sub>, (&lowast;&lowast;), 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">

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel12}} ==!! Matroidok összege. k-matroid-metszet probléma, ennek bonyolultsága k>3 esetén.== TOC ===Matroidok összege==…”

2012-10-22T09:43:33Z

Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel12}} ==!! Matroidok összege. k-matroid-metszet probléma, ennek bonyolultsága k>3 esetén.== __TOC__ ===Matroidok összege==…”

Új lap

{{GlobalTemplate|Infoszak|RopiTetel12}}

==!! Matroidok összege. k-matroid-metszet probléma, ennek bonyolultsága k>3 esetén.==

__TOC__

===Matroidok összege===

*Def.*: M1=(E,F1) és M2=(E,F2) összege M1&or;M2=(E,F1&or;F2), ahol X∈F1&or;F2 <big>⇔</big> ∃X1,X2: X=X1∪X2, X1∈F1 és X2∈F2. Magyarul X előáll egy F1-beli és egy F2-beli elem uniójaként. Megjegyzés: nem változtat a definíción, ha feltesszük, hogy X1 és X2 diszjunkt.

*Tétel*: M1&or;M2 is matroid. 
*Biz.*: 
{{InLineImageLink|Infoszak|RopiTetel12|matroidosszeg.png}}
Az 1. és 2. függetlenségi axióma triviálisan teljesül.
A 3. axióma bizonyításához vegyük azt a felbontást, ahol |(X2∩Y1)∪(Y2∩X1) (a (><) alakú terület elemszáma) minimális és X1∩X2=Y1∩Y2=<big>∅</big>.

{| border="1"
|X||>||Y|| miatt ||X1||>||Y1|| és ||X2||>||Y2 közül legalább az egyik teljesül, legyen mondjuk az első. M1 3. axiómája miatt ∃x∈X1-Y1: Y1∪{x}∈F1. Ha x∉Y2 (&lowast;), akkor x kielégíti a M1&or;M2-re vonatkozó 3. axiómát is. Ha x∈Y2, (&lowast;&lowast;), akkor Y1∪{x}, Y2-{x} is egy jó felbontás és kisebb az (X2∩Y1)∪(Y2∩X1) elemszáma, ami ellentmondás.
 

===Matroid csonkolása===

*Def.*: M=(E,F). M csonkoltja M'=(E,F'), ahol F' az F elemeit tartalmazza a bázisok kivételével. A függetlenségi axiómák triviálisan teljesülnek. A csonkolástól a matroid rangja 1-gyel csökken. 
*Pl.*: Un,k csonkoltja Un,k-1.

<div id="MMP2"></div>
===2-matroid-metszet probléma===

*MMPk*: adott k matroid (Mi=(E,Fi), i=1...k) és egy p egész szám. Kérdés: létezik-e Fi-knek legalább p méretű közös elemük?

*Tétel*: MMP2∈P. 
*Biz*: M1=(E,F1), M2=(E,F2), p egész. Ha p>min(r1,r2), nem a válasz. Csonkoljuk a matroidokat addig, amíg a rangjuk min(r1,r2,p)-re nem csökken. Ezzel a problémát redukáltuk közös bázis keresésére. r1=r2=p-re a válasz akkor és csak akkor igenlő, ha M1&or;M2*=(E,2E).
* <big>⇒</big>: ha M1-nek és M2-nek van közös B bázisa, akkor M2*-ban E-B bázis, E=B∪(E-B) egy felbontása az összegnek, azaz az összegben E független, tehát M1&or;M2* szabadmatroid.
* <big>⇐</big>: legyen E=C∪D egy olyan felbontása a szabadmatroidnak, ahol C∈F1 és D∈F2*. |E|| ≤ ||C||+||D|| = r1(C)+r2*(D) ≤ r1(E)+r2*(E) = r1(E)+||E||-r2(E) = ||E. C és D diszjunkt bázisok <big>⇒</big> C közös bázisa M1-nek és M2-nek.

===k-matroid-metszet probléma bonyolultsága===

'''Tétel:''' MMP3 NP-teljes. 
*Biz.*:
<ul>
<li> NP-beli, mert tanú egy p elemű közös bázis.
<li> G irányított gráfban az u és v közötti Hamilton-út keresése visszavezethető MMP3-ra.
* M1=(E,F1)-ben X&sube;E-re X∈F1 <big>⇔</big> az X részgráfban minden pont be-foka legfeljebb 1 és u be-foka 0.
* M2=(E,F2)-ben X&sube;E-re X∈F2 <big>⇔</big> az X részgráfban minden pont ki-foka legfeljebb 1 és v ki-foka 0.
* M3 a gráf körmatroidja.
M1, M2 és M3 közös |V-1 elemű bázisai G irányított Hamilton-útjai.
</ul>

*Tétel*: MMPk k>3-ra NP-teljes. 
*Biz.*: az előző bizonyításban definiálit M1, M2 és M3 matroidokhoz vegyünk hozzá k-3 db szabadmatroidot.

-- [[PallosPeter|Peti]] - 2007.01.02.

[[Category:Infoszak]]

Rendszeroptimalizálás, 12. tétel - Laptörténet

Tóth Krisztián Dávid, 2017. május 24., 05:59-n

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel12}} ==!! Matroidok összege. k-matroid-metszet probléma, ennek bonyolultsága k>3 esetén.== __TOC__ ===Matroidok összege==…”

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel12}} ==!! Matroidok összege. k-matroid-metszet probléma, ennek bonyolultsága k>3 esetén.== TOC ===Matroidok összege==…”