Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel8}} ==!! Matroid definíciója, alapfogalmak (bázis, rang, kör). Példák: lineáris mat…”

2012-10-22T09:44:41Z

Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel8}} <style> ol { margin-top: 0px; } </style> ==!! Matroid definíciója, alapfogalmak (bázis, rang, kör). Példák: lineáris mat…”

Új lap

{{GlobalTemplate|Infoszak|RopiTetel8}}

<style> ol { margin-top: 0px; } </style>

==!! Matroid definíciója, alapfogalmak (bázis, rang, kör). Példák: lineáris matroid (mátrixmatroid), grafikus matroid, uniform matroid. A rangfüggvény szubmodularitása.==

__TOC__

===Matroid alapfogalmak===

*Def.*: legyen E tetszőleges véges halmaz, F&sube;2<sup>E</sup>. (E,F) matroid, ha teljesülnek rá a függetlenségi axiómák:
# ∅∈F
# X∈F és Y&sube;X <big>⇒</big> Y∈F
# X,Y∈F és |X||>||Y <big>⇒</big> ∃x∈X-Y: Y∪{x}∈F
*Def.*: (E,F) matroidban ha X&sube;E és X∈F, akkor X független. <br>
*Def.*: (E,F) matroidban ha X&sube;E és X∉F, akkor X összefüggő. <br>
*Def.*: ha X maximális elemszámú független halmaz, akkor bázisnak hívjuk. <br>
*Def.*: ha X minimális elemszámú összefüggő halmaz, akkor körnek hívjuk. <br>
*Def.*: X rangja r(X) = az X által tartalmazott maximális független részhalmazok (közös) elemszáma.

===Matroid osztályok===

*Def.*: (E,F) grafikus matroid, ha ∃G gráf, hogy E=E(G) és F a G-beli erdők halmaza. <br>
*Def.*: (E,F) lineáris matroid, ha ∃M mátrix, hogy E az M oszlopainak halmaza, X∈F akkor, ha X oszlopai lineárisan függetlenek. <br>
*Def.*: (E,F) U<sub>n,k</sub> uniform matroid, ha |E||=n és X∈F akkor, ha ||X≤k.

===Rangfüggvény tulajdonságai===

*Tétel*: r:2<sup>E</sup>→<b>N</b> egy matroid rangfüggvénye <big>⇒</big>
# r(∅)=0
# 0≤r(X)≤|X ∀X&sube;E-re
# Ha X&sube;Y, r(X)≤r(Y)
# r(X) szubmoduláris, azaz ∀A,B&sube;E-re r(A)+r(B)≥r(A∪B)+r(A∩B)

*Megj.*: a tétel visszafelé is igaz. Ha r:2<sup>E</sup>→<b>N</b>-re teljesül a 3 axióma, ∃! olyan matroid, aminek ez a rangfüggvénye, mégpedig F={X:r(X)=|X}.

*Biz.*: 1. és 2. a definícióból adódik. Szubmodularitás:

{{InLineImageLink|Infoszak|RopiTetel8|submodularity.png}}
Tekintsünk egy X,Y halmazpárt. Legyen a maximális független részhalmaz X∩Y-ban A, elemszáma |A=α. Egészítsük ki A-t maximális független részhalmazzá X∪Y-ban, ekkor X-ből β, Y-ból γ új elem kerül belé. A független részhalmazok elemszáma a következőképpen alakul:
<ul style="margin-bottom:0px">
<li style="margin-left:2.5em"> r(X∩Y) = α
<li style="margin-left:2.5em"> r(X∪Y) = β+α+γ
<li style="margin-left:2.5em"> r(X) ≥ β+α, mert mutattunk benne ekkora független részhalmazt
<li style="margin-left:2.5em"> r(Y) ≥ α+γ
</ul>
<br clear="all">
Összesítve: r(X)+r(Y) ≥ r(X∪Y)+r(X∩Y)

-- [[PallosPeter|Peti]] - 2007.01.01.

[[Category:Infoszak]]

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

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel8}} ol { margin-top: 0px; } ==!! Matroid definíciója, alapfogalmak (bázis, rang, kör). Példák: lineáris mat…”

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel8}} ==!! Matroid definíciója, alapfogalmak (bázis, rang, kör). Példák: lineáris mat…”