Rendszeroptimalizálás, 10. 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

%BEGINLATEXPREAMBLE% \usepackage{colortbl} \definecolor{orange}{rgb}{1,0.7,0} \newcommand{\yellowtd}[3]{\multicolumn{1}{#1>{\columncolor{yellow}}c#3}{#2}} \newcommand{\orangetd}[3]{\multicolumn{1}{#1>{\columncolor{orange}}c#3}{#2}} \newcommand{\redtd}[3]{\multicolumn{1}{#1>{\columncolor{red}}c#3}{#2}} %ENDLATEXPREAMBLE%

!! Elhagyás és összehúzás. Matroidok direkt összege, összefüggősége. T test felett reprezentálható matroid duálisának T feletti reprezentálhatósága.

Él elhagyása és összehúzása

• Def.*: X élhalmaz elhagyása. Legyen M(E,F) egy matroid, X⊆E. Ekkor M(E,F)\X = M(E-X, F\X) is matroid, ahol F\X={Y:Y∈F és Y⊆E-X}.
  
• Def.*: X élhalmaz összehúzása. Legyen M(E,F) egy matroid, X⊆E. Ekkor M(E,F)/X = M(E-X, F/X) is matroid, ahol M(E-X, F/X)-et a következő rangfüggvénnyel definiáljuk: r(U)=r(U∪X)-r(X).
  
• Tétel*: elhagyások és összehúzások sorozata ugyanahhoz a matroidhoz vezet függetlenül a műveletek sorrendjétől. (M\A)/B-t az M matroid minorjának hívjuk.
  
• Tétel*: az elhagyás és az összehúzás duális műveletek: (M\X)*=M*/X és (M/X)*=M*\X

Matroidok direkt összege, összefüggősége

• Def.*: M₁=(E₁,F₁), M₂=(E₂,F₂) olyan matroidok, amire E₁∩E₂=∅. Ekkor M₁⊕M₂=(E₁∪E₂, F), ahol F={X⊆E₁∪E₂: X∩E₁∈F₁ és X∩E₂∈F₂}
  
• Def.*: egy matroid összefüggő, ha nem áll elő két kisebb matroid direkt összegeként.
  
• Tétel*: egy grafikus matroid akkor összefüggő, ha a gráf kétszeresen összefüggő.

T test feletti reprezentálhatóság

• Def.*: egy M(E,F) matroid T felett reprezentálható==koordinátázható, ha E minden eleme T feletti vektor.

Legyen r=r(E) és n=|E. M(E,F) leírható egy r×n-s A mátrixszal, aminek sorai lineárisan függetlenek. r sor mindenképpen szükséges, ha pedig több sorból áll a mátrix, kiválaszthatunk r lineárisan függetlent, és elhagyhatjuk a maradékot, a matroid ugyanaz marad.

A kapott mátrix pedig egy alkalmas nemszinguláris r×r-es mátrixszal való szorzással leképezhető úgy, hogy a baloldalán egységmátrix legyen. A transzformált mátrix ugyanazt a matroidot koordinátázza.

[math] r \mathop{\begin{array}{|ccc|} \hline & & \\ \multicolumn{3}{|c|}{\det \ne 0} \\ & & \\ \hline \end{array}}\limits^r \:\:\cdot\:\: r \mathop{\begin{array}{|ccccc|} \hline & & & & \\ & & A & & \\ & & & & \\ \hline \end{array}}\limits^n = r \mathop{\begin{array}{|ccccc|} \hline & & & & \\ & & B & & \\ & & & & \\ \hline \end{array}}\limits^n = \mathop{\begin{array}{|ccc|cc|} \hline 1 & & 0 & & \\ & 1 & & \multicolumn{2}{|c|}{A'} \\ 0 & & 1 & & \\ \hline \end{array}} [/math]

Duális matroid reprezentálhatósága T felett

Elég belátni, ha baloldalt egy r×r-es részmátrix nemszinguláris, akkor jobboldalt a megfelelő (n-r)×(n-r)-es részmátrix is nemszinguláris.

Az ábrán a két narancssárga részmátrix megegyezik, a két piros részmátrix oszlopai pedig valamilyen sorrendben mindkét oldalon egységmátrixot alkotnak ⇒ ha a bázisnak megfelelő beloldali részmátrix nemszinguláris, akkor a jobboldali is. A bázisok 1-1 megfeleltethetők egymásnak ⇒ M és M* egymás duálisai.

[math] M = \left. \begin{array}{|ccc|ccccc|} \hline 1 & & \yellowtd{}{0}{|} & \orangetd{|}{}{} & \orangetd{}{}{} & & & \\ & 1 & \yellowtd{}{0}{|} & \orangetd{|}{}{} & \orangetd{}{}{} & A' & & \\ 0 & & \redtd{}{1}{|} & \yellowtd{|}{}{} & \yellowtd{}{}{} & & & \\ \hline \end{array} \right\}r \quad \Rightarrow \quad M^* = \left. \begin{array}{|ccc|ccccc|} \hline \orangetd{|}{}{} & \orangetd{}{}{} & & 1 & & \yellowtd{}{}{} & \yellowtd{}{}{} & \yellowtd{}{0}{|} \\ \orangetd{|}{}{} & \orangetd{}{}{} & & & 1 & \yellowtd{}{0}{} & \yellowtd{}{}{} & \yellowtd{}{}{|} \\ \multicolumn{2}{|\gt {\columncolor{yellow}\hspace{0.8em}}r}{A'^T} & & & & \redtd{}{1}{} & \redtd{}{}{} & \redtd{}{0}{|} \\ \yellowtd{|}{}{} & \yellowtd{}{}{} & & & & \redtd{}{}{} & \redtd{}{1}{} & \redtd{}{}{|} \\ \yellowtd{|}{}{} & \yellowtd{}{}{} & & & & \redtd{}{0}{} & \redtd{}{}{} & \redtd{}{1}{|} \\ \hline \end{array} \right\}n-r [/math]

-- Peti - 2007.01.02.