Rendszeroptimalizálás, 11. tétel forrásának megtekintése

{{GlobalTemplate|Infoszak|RopiTetel11}}

%BEGINLATEXPREAMBLE% \usepackage{multirow} %ENDLATEXPREAMBLE%

==!! Grafikus, kografikus, reguláris, bináris és lineáris matroid fogalma, ezek kapcsolata (ebből bizonyítás csak a grafikus és reguláris matroidok közötti kapcsolatra), példák. Fano-matroid, példa nemlineáris matroidra. Bináris, reguláris és grafikus matroidok jellemzése tiltott minorokkal: Tutte tételei (biz. nélkül). Seymour tétele (biz. nélkül).==

__TOC__

===Matroid osztályok===

*Def.*: M(E,F) grafikus matroid, ha &exist;G gráf, hogy E=E(G) és F a G-beli erdők halmaza. <br>
*Def.*: a grafikus matroidok duálisát kografikus matroidnak hívjuk. <br>
*Def.*: M reguláris matroid, ha minden test felett koordinátázható. <br>
*Def.*: M bináris matroid, ha koordinátázható a bináris test felett. <br>
*Def.*: M lineáris matroid, ha van olyan test, ami felett koordinátázható. <br>

===Matroid osztályok kapcsolata példákkal===

{{InLineImageLink|Infoszak|RopiTetel11|matroidosztalyok.png}}

*Tétel*: minden grafikus matroid reguláris <br>
*Biz.*: a gráf n csúcsára írjuk fel az n-1 elemű egységvektorokat és a nullvektort valamilyen sorrendben. Az élekre kerüljön a két végpontjának különbsége. E vektorai csak 0 és &plusmn;1 elemeket tartalmaznak, tehát minden test fölött reprezentálhatók.
* Ha egy élhalmaz vektorai lineárisan függetlenek, akkor az élhalmaz körmentes. <br> Biz.: indirekt, a kör éleit &plusmn;1 együtthatókkal összeadva minden csúcs egyszer szerepel +1 és egyszer -1 együtthatóval <big>&rArr;</big> a csúcsok kiesnek, összegnek 0-t kapunk.
* Ha egy részgráf körmentes, az élvektorai lineárisan függetlenek. <br> Biz.: indirekt, a 0 összegű lineáris kombinációból válsszuk ki a nem 0 együtthatójú vektorokat. A vektorok által meghatározott részgráfban minden pont foka legalább 2, különben valamelyik csúcs nem nullázódna ki <big>&rArr;</big> nem körmentes.
*Tétel*: M<sub>1</sub> és M<sub>2</sub> koordinázható F felett <big>&hArr;</big> M<sub>1</sub><big>&oplus;</big>M<sub>2</sub> is.

===Fano matroid és Anti Fano matroid===

{{InLineImageLink|Infoszak|RopiTetel11|fanomatroid.png}}
*Def.*: F<sub>7</sub>(E,F) Fano matroid, ha E={1,2,3,4,5,6,7} és F={E &le;2 elemű részhalmazai}&cup;{E azon 3 elemű részhalmazai, aminek az elemei az ábrán nincsenek egy egyenesen vagy körön} <br>
*Def.*: F<sub>7</sub><sup>&ndash;</sup>(E,F) Anti Fano matroid, ha E={1,2,3,4,5,6,7} és F={E &le;2 elemű részhalmazai}&cup;{E azon 3 elemű részhalmazai, aminek az elemei az ábrán nincsenek egy egyenesen}

*Tétel*: F<sub>7</sub> csak a 2 karakterisztikájú, F<sub>7</sub><sup>&ndash;</sup> csak a nem 2 karakterisztikájú testek fölött koordinátázható. <br>
*Köv.*: mivel a direkt összeg a koordinátázhatóságot megtartja, F<sub>7</sub><big>&oplus;</big>F<sub>7</sub><sup>&ndash;</sup> semmilyen test fölött nem koordinátázható.
<br clear="all">

===Matroid osztályok és tiltott minorok===

*Tutte tételei*:
* M bináris <big>&hArr;</big> nem tartalmazza minorként az U<sub>4,2</sub>-t.
* M reguláris <big>&hArr;</big> nem tartalmazza az U<sub>4,2</sub>, F<sub>7</sub> és F<sub>7</sub>* minorokat.
* M grafikus <big>&hArr;</big> nem tartalmazza az U<sub>4,2</sub>, F<sub>7</sub> és F<sub>7</sub>*, M*(K<sub>5</sub>), M*(K<sub>3,3</sub>) minorokat.

*Paul Seymour-tétel*: M reguláris <big>&hArr;</big> előáll 1 grafikus, 1 kografikus és egy R<sub>10</sub> matroid néhány példányából a direkt összeg, 2-összeg és 3-összeg műveletek segítségével.
<ul>
<li> <math> R_{10} = \left( \begin{array}{cccccccccc}
  0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\
  0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\
  1 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 1 \\
  1 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 \\
  1 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0
\end{array} \right) </math>
<li> Direkt összeg: M<sub>1</sub>-nek és M<sub>2</sub>-nek nincs közös éle. M<sub>1</sub><big>&oplus;</big>M<sub>2</sub>-t a következő mátrix definiálja:
<math> \begin{array}{|c|c|} 
  \hline 
  A_1 & 0 \\
  \hline
  0 & A_2 \\
  \hline
\end{array} </math>
<li> 2-összeg: tegyük fel, hogy M<sub>1</sub> (A<sub>1</sub>',E) alakban, M<sub>2</sub> (E, A<sub>2</sub>') alakban van koordinátázva, továbbá hogy M<sub>1</sub> utolsó éle megegyezik M<sub>2</sub> első élével és más közös élük nincs. Ekkor M<sub>1</sub>+<span style="position:relative; left:-8px; top:-3px"><sup>2</sup></span>M<sub>2</sub>-t a következő mátrix koordinátázza:
<math>  M_1 = 
\begin{array}{|cc|cc|c|}
  \hline
  \multicolumn{2}{|c|}{}	  & 1 &	& 0	 \\
  \multicolumn{2}{|c|}{A_1'} &	& 1 &	 \\
  \multicolumn{2}{|c|}{}	  & 0 &	& 1  \\
  \hline
\end{array} 
\quad
M_2 = 
\begin{array}{|c|cc|cc|}
  \hline
 1 &	& 0 & \multicolumn{2}{|c|}{}			\\
	& 1 &	& \multicolumn{2}{|c|}{A_2'}	 \\
 0 &	& 1 & \multicolumn{2}{|c|}{}		 \\
  \hline
\end{array} 
\quad
 M_1 \mathop{+}\limits^2 M_2 = \begin{array}{|cccc||cccc|}
  \hline
  \multicolumn{2}{|c|}{} & 1 &  0 & & & & \\
  \multicolumn{2}{|c|}{A_1'} & & 1 & & & & 0 \\
  \cline{5-8}
  \multicolumn{2}{|c|}{} & 0 &  & & 0 & \multicolumn{2}{|c|}{} \\
  \cline{1-4}
	 & & 0 & & 1 & & \multicolumn{2}{|c|}{A_2'} \\
	 & & & & 0 & 1 & \multicolumn{2}{|c|}{} \\
  \hline
\end{array} </math>
<li> 3-összeg: tegyük fel, hogy a M<sub>1</sub>-nek és M<sub>2</sub>-nek 3 közös éle van, amelyek egy kört alkotnak. Ekkor a következőképpen alakul a 3-összeg:
<math>
M_1 = \begin{array}{|@{\hspace{1em}}c@{\hspace{1em}}|ccc|}
  \hline
  \multirow{2}{*}{$A_1'$} & & \multirow{2}{*}{0} & \\
  & & & \\
  \hline
  \multirow{2}{*}{$A_1''$} & 1 & 0 & 1 \\
  & 0 & 1 & 1 \\
  \hline
\end{array}
\quad
M_2 = \begin{array}{|ccc|@{\hspace{1em}}c@{\hspace{1em}}|}
  \hline
  1 & 0 & 1 & \multirow{2}{*}{$A_2'$} \\
  0 & 1 & 1 & \\
  \hline
  & \multirow{2}{*}{0} & & \multirow{2}{*}{$A_2''$} \\
  & & & \\
  \hline
\end{array}
\quad
M_1 \mathop{+}\limits^3 M_2 = \begin{array}{|@{\hspace{1em}}c@{\hspace{1em}}|@{\hspace{1em}}c@{\hspace{1em}}|}
  \hline
  \multirow{2}{*}{$A_1'$} & \multirow{2}{*}{0} \\
  & \\
  \hline
  \multirow{2}{*}{$A_1''$} & \multirow{2}{*}{$A_2'$} \\
  & \\
  \hline
  \multirow{2}{*}{0} & \multirow{2}{*}{$A_2''$} \\
  & \\
  \hline
\end{array}
</math>
</ul>

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

Szerintem a 2-összegben a középső, (0,...,0,1,0,...,0) oszlopot el kell hagyni, úgy kapjuk meg a 2 összeget, valaki erősítse meg / írja át! (Gabo)

Szerintem is, átírtam.
-- [[FodorPeter|Peti]] - 2009.01.13.


[[Category:Infoszak]]