Halmazrendszerek speciálkollégium, Hajnal Péter XII. 16. (1 óra)

Matroidok II.

Tétel: (i) Legyen M egy matroid az S halmazon, ϕ : S → T egy ráképezés. Ekkor az M matroid ϕ(M) homomorf képének rangfüggvénye: r_{ϕ(M)}(X) = min{ |A| + r_{M}(ϕ^{−1}(B)) : X = A ˙∪B }

(ii) Legyen M_{1} és M_{2} két matroid az S halmazon. Ekkor az M_{1} ∨ M_{2} összegmatroid rangfüggvénye: r_{M_{1}∨M_{1}}(X) = min{ r_{M_{1}}(A) + r_{M_{2}}(A) + |B| : X = A ˙∪B },

(iii) Legyen M_{1} és M_{2} két matroid az S halmazon. Ekkor a két matroid legnagyobb közös függetlenjének mérete: max{ |X| : X ∈ M_{1}, X ∈ M_{2} } = min{ r_{M_{1}}(A) + r_{M_{2}}(B) : S = A ˙∪B }.

Bizonyítás: Elég (i)-t és (ii)-t az X = T, illetve X = S esetén belátni.

(i), (ii) és (iii) ekvivalens. (iii): Bizonyítási séma: Tétel=max{ |X| : X ∈ M_{1}, X ∈ M_{2} } = k. Bizonyítás=(X, A, B) : |X| = k, X ∈ M_{1}, X ∈ M_{2}, S =

A ˙∪B, X ∩ A bázis A-ban, X ∩ B bázis B-ban

Bizonyítás létezése esetén a tétel igaz. Ha igaz a tétel, akkor szükségszerű-e, hogy létezik hozzá bizonyítás? Ha igen, akkor (iii) adódik. Belátjuk, hogy igen a válasz. Ez |S|-re vonatkozó teljes indukcióval igazolható:

1. eset: x hurokél M_{1}-ben.

2. eset: x hurokél M_{2}-ben.

3. eset: x nem hurokél sem M_{1}-ben, sem M_{2}-ben.

Az indukciós feltevést alkalmazzuk M_{1} \ { x } és M_{2} \ { x }-re. Az indukciós feltevést alkalmazzuk M_{1}{ x } és M_{2}{ x }-re.

⋆

Következmény: Legyen H egy matroid bázisai által alkotott halmazrendszer. Független élrendszer.

Következmény: Összefüggő gráfban diszjunkt feszítőfák száma.

Következmény: Legyen H egy matroid bázisai által alkotott halmazrendszer. Fedés.

Következmény: Összefüggő gráf lefedése feszítőfákkal.

⋆  ⋆  ⋆

Legyen H egy matroid körei által alkotott halmazrendszer. Lefogási feladat NP -teljes marad.

Legyen H egy gráf körmatroidjának körei által alkotott halmazrendszer. Ekkor a színezési feladat P -beli.