Rendszeroptimalizálás, 11. tétel

A VIK Wikiből
A lap korábbi változatát látod, amilyen (vitalap) 2012. október 22., 11:43-kor történt szerkesztése után volt. (Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel11}} %BEGINLATEXPREAMBLE% \usepackage{multirow} %ENDLATEXPREAMBLE% ==!! Grafikus, kografikus, reguláris, bináris és lineáris ma…”)
(eltér) ← Régebbi változat | Aktuális változat (eltér) | Újabb változat→ (eltér)
Ugrás a navigációhoz Ugrás a kereséshez

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*: M1 és M2 koordinázható F felett M1M2 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.*: 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, F7F7 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 U4,2-t.
  • M reguláris nem tartalmazza az U4,2, F7 és F7* minorokat.
  • M grafikus nem tartalmazza az U4,2, F7 és F7*, M*(K5), M*(K3,3) minorokat.
  • Paul Seymour-tétel*: M reguláris 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.
  • [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: M1-nek és M2-nek nincs közös éle. M1M2-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 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]
  • 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]

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