Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel11}} %BEGINLATEXPREAMBLE% \usepackage{multirow} %ENDLATEXPREAMBLE% ==!! Grafikus, kografikus, reguláris, bináris és lineáris ma…”

2012-10-22T09:43:30Z

Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel11}} %BEGINLATEXPREAMBLE% \usepackage{multirow} %ENDLATEXPREAMBLE% ==!! Grafikus, kografikus, reguláris, bináris és lineáris ma…”

Új lap

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

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

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

*Tétel*: minden grafikus matroid reguláris 
*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 ±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. Biz.: indirekt, a kör éleit ±1 együtthatókkal összeadva minden csúcs egyszer szerepel +1 és egyszer -1 együtthatóval <big>⇒</big> a csúcsok kiesnek, összegnek 0-t kapunk.
* Ha egy részgráf körmentes, az élvektorai lineárisan függetlenek. 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>⇒</big> nem körmentes.
*Tétel*: M1 és M2 koordinázható F felett <big>⇔</big> M1<big>&oplus;</big>M2 is.

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

{{InLineImageLink|Infoszak|RopiTetel11|fanomatroid.png}}
*Def.*: F7(E,F) Fano matroid, ha E={1,2,3,4,5,6,7} és F={E ≤2 elemű részhalmazai}∪{E azon 3 elemű részhalmazai, aminek az elemei az ábrán nincsenek egy egyenesen vagy körön} 
*Def.*: F7–(E,F) Anti Fano matroid, ha E={1,2,3,4,5,6,7} és F={E ≤2 elemű részhalmazai}∪{E azon 3 elemű részhalmazai, aminek az elemei az ábrán nincsenek egy egyenesen}

*Tétel*: F7 csak a 2 karakterisztikájú, F7– csak a nem 2 karakterisztikájú testek fölött koordinátázható. 
*Köv.*: mivel a direkt összeg a koordinátázhatóságot megtartja, F7<big>&oplus;</big>F7– semmilyen test fölött nem koordinátázható.
 

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

*Tutte tételei*:
* M bináris <big>⇔</big> nem tartalmazza minorként az U4,2-t.
* M reguláris <big>⇔</big> nem tartalmazza az U4,2, F7 és F7* minorokat.
* M grafikus <big>⇔</big> nem tartalmazza az U4,2, F7 és F7*, M*(K5), M*(K3,3) minorokat.

*Paul Seymour-tétel*: M reguláris <big>⇔</big> előáll 1 grafikus, 1 kografikus és egy R10 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: M1-nek és M2-nek nincs közös éle. M1<big>&oplus;</big>M2-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 M1 (A1',E) alakban, M2 (E, A2') alakban van koordinátázva, továbbá hogy M1 utolsó éle megegyezik M2 első élével és más közös élük nincs. Ekkor M1+2M2-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 M1-nek és M2-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]]

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

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel11}} %BEGINLATEXPREAMBLE% \usepackage{multirow} %ENDLATEXPREAMBLE% ==!! Grafikus, kografikus, reguláris, bináris és lineáris ma…”