Rendszeroptimalizálás, 11. 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{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).

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

Ezen a helyen volt linkelve a matroidosztalyok.png nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

• 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 ⇒ 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 ⇒ nem körmentes.
• Tétel*: M₁ és M₂ koordinázható F felett ⇔ M₁⊕M₂ is.

Fano matroid és Anti Fano matroid

Ezen a helyen volt linkelve a fanomatroid.png nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

• Def.*: F₇(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.*: F₇^–(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*: F₇ csak a 2 karakterisztikájú, F₇^– 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, F₇⊕F₇^– semmilyen test fölött nem koordinátázható.

Matroid osztályok és tiltott minorok

• Tutte tételei*:
• M bináris ⇔ nem tartalmazza minorként az U_4,2-t.
• M reguláris ⇔ nem tartalmazza az U_4,2, F₇ és F₇* minorokat.
• M grafikus ⇔ nem tartalmazza az U_4,2, F₇ és F₇*, M*(K₅), M*(K_3,3) minorokat.

• Paul Seymour-tétel*: M reguláris ⇔ előáll 1 grafikus, 1 kografikus és egy R₁₀ matroid néhány példányából a direkt összeg, 2-összeg és 3-összeg műveletek segítségével.

• [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]
• Direkt összeg: M₁-nek és M₂-nek nincs közös éle. M₁⊕M₂-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]
• 2-összeg: tegyük fel, hogy M₁ (A₁',E) alakban, M₂ (E, A₂') alakban van koordinátázva, továbbá hogy M₁ utolsó éle megegyezik M₂ első élével és más közös élük nincs. Ekkor M₁+²M₂-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]
• 3-összeg: tegyük fel, hogy a M₁-nek és M₂-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]

-- 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. -- Peti - 2009.01.13.