Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel10}} %BEGINLATEXPREAMBLE% \usepackage{colortbl} \definecolor{orange}{rgb}{1,0.7,0} \newcommand{\yellowtd}[3]{\multicolumn{1}{#1>{\co…”

2012-10-22T09:43:27Z

Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel10}} %BEGINLATEXPREAMBLE% \usepackage{colortbl} \definecolor{orange}{rgb}{1,0.7,0} \newcommand{\yellowtd}[3]{\multicolumn{1}{#1>{\co…”

Új lap

{{GlobalTemplate|Infoszak|RopiTetel10}}

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

__TOC__

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

*Def.*: X élhalmaz elhagyása. Legyen M(E,F) egy matroid, X&sube;E. Ekkor M(E,F)\X = M(E-X, F\X) is matroid, ahol F\X={Y:Y∈F és Y&sube;E-X}. 
*Def.*: X élhalmaz összehúzása. Legyen M(E,F) egy matroid, X&sube;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.*: M1=(E1,F1), M2=(E2,F2) olyan matroidok, amire E1∩E2=<big>∅</big>. Ekkor M1<big>&oplus;</big>M2=(E1∪E2, F), ahol F={X&sube;E1∪E2: X∩E1∈F1 és X∩E2∈F2} 
*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 <big>⇒</big> ha a bázisnak megfelelő beloldali részmátrix nemszinguláris, akkor a jobboldali is. A bázisok 1-1 megfeleltethetők egymásnak <big>⇒</big> 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}{|>{\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>

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

[[Category:Infoszak]]

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

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel10}} %BEGINLATEXPREAMBLE% \usepackage{colortbl} \definecolor{orange}{rgb}{1,0.7,0} \newcommand{\yellowtd}[3]{\multicolumn{1}{#1>{\co…”