Rendszeroptimalizálás, 8. tétel

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

<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.

Matroid alapfogalmak

• Def.*: legyen E tetszőleges véges halmaz, F⊆2^E. (E,F) matroid, ha teljesülnek rá a függetlenségi axiómák:

1. ∅∈F
2. X∈F és Y⊆X ⇒ Y∈F
3. X,Y∈F és |X||>||Y ⇒ ∃x∈X-Y: Y∪{x}∈F

• Def.*: (E,F) matroidban ha X⊆E és X∈F, akkor X független.
  
• Def.*: (E,F) matroidban ha X⊆E és X∉F, akkor X összefüggő.
  
• Def.*: ha X maximális elemszámú független halmaz, akkor bázisnak hívjuk.
  
• Def.*: ha X minimális elemszámú összefüggő halmaz, akkor körnek hívjuk.
  
• 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.
  
• 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.
  
• Def.*: (E,F) U_n,k uniform matroid, ha |E||=n és X∈F akkor, ha ||X≤k.

Rangfüggvény tulajdonságai

• Tétel*: r:2^E→N egy matroid rangfüggvénye ⇒

1. r(∅)=0
2. 0≤r(X)≤|X ∀X⊆E-re
3. Ha X⊆Y, r(X)≤r(Y)
4. r(X) szubmoduláris, azaz ∀A,B⊆E-re r(A)+r(B)≥r(A∪B)+r(A∩B)

• Megj.*: a tétel visszafelé is igaz. Ha r:2^E→N-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:

Ezen a helyen volt linkelve a submodularity.png nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

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:

• r(X∩Y) = α
• r(X∪Y) = β+α+γ
• r(X) ≥ β+α, mert mutattunk benne ekkora független részhalmazt
• r(Y) ≥ α+γ

Összesítve: r(X)+r(Y) ≥ r(X∪Y)+r(X∩Y)

-- Peti - 2007.01.01.