Cuprins

Introducere iii

1 Introducere n teoria grafurilor 1

1.1 Grafuri (simple si neorientate), multigrafuri si pseudografuri . . . . . . . . . 1

1.2 Subgrafuri si minori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.3 Gradul unui vrf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.4 Conexitate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.5 Raze, cicluri finite si infinite . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.6 Izomorfisme de grafuri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.7 Tipuri speciale de grafuri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.7.1 Grafuri complete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.7.2 Grafuri bipartite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.7.3 Arbori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.7.4 Grafuri plane si planare . . . . . . . . . . . . . . . . . . . . . . . . . 8

2 Introducere n teoria matroizilor 11

2.1 Matroizi. Definitii preliminare. . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.1.1 Multimi independente . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.1.2 Baze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.1.3 Circuite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.1.4 Functia rang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.1.5 Operatorul de nchidere . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.2 Izomorfisme de matroizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.3 Tipuri speciale de matroizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.3.1 Matroidul trivial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.3.2 Matroidul discret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.3.3 Matroidul uniform . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.3.4 Matroidul vectorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.3.5 Matroidul matriceal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.3.6 Matroidul geometric . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

i

2.3.7 Matroidul afin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.3.8 Matroizi grafici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.3.9 Matroizi bicirculari . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.3.10 Matroizi partitie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.4 Operatii asupra matroizilor . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.4.1 Intersectia matroizilor . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.4.2 Reuniunea matroizilor . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.5 Dualitate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.6 Minori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.7 Conexitate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.7.1 Matroizi 2-conecsi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.7.2 Matroizi k-conecsi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

2.8 Reprezentabilitatea matroizilor . . . . . . . . . . . . . . . . . . . . . . . . . 39

2.8.1 Reprezentabilitatea peste corpuri finite . . . . . . . . . . . . . . . . . 39

2.8.2 Matroizi binari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

2.8.3 Matroizi regulati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3 Matroizi infiniti 47

3.1 Spatii de pre-independenta, spatii de independenta si dualitate . . . . . . . . 47

3.2 Operatori de nchidere si matroizi infiniti . . . . . . . . . . . . . . . . . . . . 50

3.3 Operatori de nchidere si spatii de independenta . . . . . . . . . . . . . . . . 52

3.4 B-matroizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

4 Grafuri infinite si matroizi 57

4.1 Matroizi grafici infiniti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

4.2 Matroizi bicirculari infiniti . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

ii

Introducere

Matroizii reprezinta o generalizare a unor obiecte combinatorice cum ar fi grafurile, matrice,

spatii liniare si geometrii proiective. Ideea de matroid dateaza din 1935 si a fost introdusa

initial (H. Whitney [5]) drept o abstractizare a dependentei liniare si a proprietatilor ciclurilor

n grafuri.

In aceasta teza snt prezentate rezultatele de baza din teoria matroizilor si snt examinate

cteva posibilitati de extindere a matroizilor finiti la matrozi infiniti n cazul grafurilor infinite.

Teza este structurata n urmatoarele capitole:

In primul capitol snt prezentate notiuni de baza despre grafuri (finite si infinite) care

apar frecvent n aceasta teza: ciclu, arbore de acoperire, dualul geometric al unui graf etc.

In al II-lea capitol snt prezentate notiuni, definitii si rezultate de baza cu privire la teoria

matroizilor.

In al III-lea capitol snt examinate doua posibilitati de extindere a matroizilor finiti

la matrozi infiniti si snt prezentate problemele care apar n aceste conditii: determinarea

dualului si existena bazelor.

In al IV-lea capitol snt considerati matroizii grafici si bicirculari infiniti. In acelasi timp

se demonstreaza ca spre deosebire de matroizii bicirculari infiniti matroizii grafici (infiniti)

nu snt B-matroizi numai atunci cnd graful respectiv nu contine o subdiviziune a grafului

Bean drept subgraf.

iii

iv

Capitolul 1

Introducere n teoria grafurilor

Dat fiind ca terminologia n teoria grafurilor nu este uniforma vom precauta n acest capitol

sistemul de notatii pe care le folosim si vom defini numeroase concepte care apar frecvent n

aceasta teza.

Toate notiunile nedefinite sau neclare pot fi gasite n orice carte introductiva precum [1].

1.1 Grafuri (simple si neorientate), multigrafuri si pseu-

dografuri

Definitia 1.1.1. Un graf (simplu) G este o pereche ordonata (V,E) (notam G = (V,E) ),

unde V este o multime nevida de elemente numite vrfuri (sau noduri), iar E este o

multime de perechi neordonate de elemente distincte din V numite muchii (sau arce).

Prin graf pe V , vom ntelege un graf avnd V n calitate de multimea de vrfuri ale sale.

Numarul de vrfuri ale unui graf G se noteaza prin |G|1 si se numeste ordinul acestuia.

In functie de ordin grafurile pot fi finite, infinit numarabile, infinit nenumarabile si

asa mai departe... In cele ce urmeaza ne vom referi doar la grafuri finite si [mai mult la cele]

infinit numarabile, carora din economie de limbaj le vom spune doar: grafuri infinite.

De obicei reprezentam graful n plan ca o figura formata din puncte (vrfurile) si segmente

de dreapta sau curba (muchiile).

O muchie este deci o submultime {u, v} V ale carei elemente se numesc extremitatile

(sau capetele) muchiei. Pentru o astfel de muchie vom folosi notatiile {u, v} sau {v, u}

(respectiv uv sau vu) avnd aceeasi semnificatie si deci nereprezentnd muchii diferite. In

conformitate cu aceasta notatie vom numi graful definit mai sus graf neorientat. Un

graf simplu este asemanator unui graf orientat cu deosebirea ca arcele nu au specificata o

directie.

1numarul de muchii se noteaza prin ||G||

1

1 2 3 4 99

102 101 100

...

Figura 1.1.1. Un graf finit G = (V,E) unde V = {1, 2, . . . 101, 102}

Daca un vrf v V apartine unei muchii e E (v e) spunem ca v este incident cu

e. Daca u, v e (extremitatile muchiei) spunem ca u si v snt adiacente (sau vecine). Se

mai spune ca muchia e conecteaza nodurile u si v. Daca e1, e2 E snt muchii distincte si

au un vrf comun atunci spunem ca e1 si e2 snt adiacente.

u...

Figura 1.1.2. Un graf infinit.

Date fiind doua multimi X,Y V si o muchie e = {x, y} astfel nct x X si y Y

spunem ca {x, y} este o X Y muchie. Multimea tuturor X Y muchiilor dintr-o multime

Z E se noteaza Z(X,Y ). In particular, prin E(X,Y ) vom nota toate X Y muchiile din

graf. Multimea tuturor muchiilor din E incidente cu un vr v notam prin E(v).

Uneori este necesar de modelat conexiuni multiple ntre noduri, ceea ce este imposibil cu

grafuri simple. In aceste cazuri trebuie utilizate multigrafuri.

Definitia 1.1.2. Un multigraf G = (V,E) consta (la fel ca si un graf simplu) ntr-o

multime V de vrfuri, o multime E de muchii si o functie f : E {(u, v) : u, v V, u 6= v}.

Muchiile e1 si e2 snt denumitemuchii multiple (sau paralele) daca f(e1) = f(e2). [De

notat ca ] muchiile din multigrafuri nu sunt definite n mod necesar ca perchi, dar pot fi de

orice tip.

Exemplul 1.1.3. Un multigraf G cu nodurile V = {a, b, c, d}, muchiile {1, 2, 3, 4, 5} si

functia f cu f(1) = (a, b), f(2) = (a, b), f(3) = (b, c), f(4) = (c, d), si f(5) = (c, d)

O muchie este bucla daca f(e) = (u, u) pentru un u din V . Din definitia de mai sus se

observa ca [n multigrafuri] buclele nu sunt admise (u 6= v).

Daca trebuie de definit (si) bucle, este necesar un alt fel de graf.

Definitia 1.1.4. Un pseudograf G = (V,E) este o multime de vrfuri V , o multime de

muchii E si o functie f de la E la {(u, v) : u, v V }.

2

1.2 Subgrafuri si minori

Definitia 1.2.1. Fie G = (V,E) un graf. Un subgraf al lui G este un graf H = (V , E )

unde V V , iar E este formata din toate muchiile din G care unesc vrfurile din V .

Un graf partial al lui G este graful (V,E ) n care E E. Graful partial se mai numeste

si subgraf de acoperire al lui G.

Definitia 1.2.2. Fie G = (V,E) un graf si V V o submultime nevida a lui V . Numim

subgraf al lui G indus de V si l notam < V >, acel subgraf care are ca noduri multimea

V , iar orice doua vrfuri din V snt adiacente n < V > daca si numai daca snt adiacente

n G.

G G G

Figura 1.2.3. Un graf G cu subgrafurile sale G si G: G este un subgraf indus, iar G nu.

Daca H este un subgraf al lui G obisnuim sa notam aceasta relatie prin H G; daca

H 6= G si H G atunci H este subgraf propriu al lui G.

In ceea ce priveste minorii, acestea pot fi obtinuti prin doua operatii de baza, eliminarea

si contractia unei muchii.

Prin G\e notam graful capatat din G n rezultatul eliminarii muchiei e si cu G/e graful

capatat prin contractia muchiei e ntr-un vrf nou ve, care devine adiacent la toti vecinii

de alta data a vrfurilor u si v.

Mai general,

G \ e = (V,E ) , cu E = E \ {e} ,

iar

G/e = (V , E ) , cu V = {V \ {u, v}} {ve} si

E = {{u, v} E : {u, v} {u, v} = } {{ve, v} : {u, v} E \ {e} sau {v, v} E \ {e}} .

Definitia 1.2.3. Fie G = (V,E) un graf. Daca un graf H poate fi obtinut din G printr-o

serie de eliminari si contractii atunci H este un minor al lui G.

Daca H este un minor al grafului G atunci scriem H G. De notat ca orice subgraf este

un minor; n particular, orice graf este propriul sau minor.

3

G G G

Figura 1.2.4. G este un minor al lui G capatat prin eliminarea muchiilor nengrosate, iar G

este un minor al lui G capatat att prin eliminarea muchiilor nengrosate ct si prin contractia

muchiilor ngrosate din G.

1.3 Gradul unui vrf

Definitia 1.3.1. Fie G = (V,E) un graf. Gradul (sau valenta) unui vrf v V , notat

d(v) (sau dG(v), sau degG(v), sau deg(v)) este numarul de muchii incidente cu v.

Daca d(v) = 0 atunci vrful v este izolat, iar daca d(v) = 1, atunci vrful v este terminal

(sau suspendat, sau pandant), el este adiacent exact unui vrf.

O bucla contribuie de doua ori la gradul vrfului n jurul caruia este construita. De aceea

un vrf cu o bucla n el are cel putin gradul 2 si, prin definitie, nu este izolat chiar daca nu

este adiacent vreunui alt vrf.

Gradul minim si gradul maxim se noteaza

(G) = min {d(v) : v V } ,

respectiv

(G) = max {d(v) : v V } .

Numarul d(G) = 1|V |

vV d(v) estemedia gradelor vrfurilor si este evident ca (G)

d(G) (G).

De notat ca n cazul grafurilor infinite nu ntotdeauna este posibil de calculat (G) si

(G). De exemplu n Figura 1.1.2 toate vrfurile n afara de u au gradul 2, pe cnd gradul

vrfului u este infinit.

Definitia 1.3.2. Un graf se numeste local finit daca toate vrfurile sale au gradele finite.

Un graf n care toate vrfurile au acelasi grad este regulat (sau omogen, sau uniform)

si este k-regulat (sau omogen de gradul k) daca se cunoaste ca d(v1) = d(v2) = . . . =

d(vn) = k. Un graf 2-regulat este o uniune disjuncta de cicluri. Un graf 3-regulat se numeste

cubic (sau trivalent).

4

1.4 Conexitate

Definitia 1.4.1. Fie G = (V,E) un graf si v1, vk V (v1 si vk nu neaparat distincte). Se

numeste drum (sau lant, sau cale) n G cu extremitatile v1 si vk succesiunea (de vrfuri

si muchii):

v1, (v1, v2) , v2, (v2, v3) , . . . , vk1, (vk1, vk) , vk.

Astfel, un drum este un subgraf; v1 se numeste nceput, vk vrf de sfrsit, iar celelalte

vrfuri interne.

Definitia 1.4.2. Un graf G se numeste conex daca pentru orice doua vrfuri u si v diferite

ale sale exista un drum care le leaga.

Definitia 1.4.3. Un graf G se numeste k-conex (k N) daca |G| < k si G \X este conex

oricare ar fi multimea X V (G) cu |X| < k.

Cu alte cuvinte, nu exista doua vrfuri n G care sa fie separate de mai putin de k vrfuri.

Orice graf diferit de cel nul este 0-conex; grafurilor 1-conexe le spunem simplu: conexe. Cel

mai mare numar k pentru care G este k-conex se numeste conectivitatea grafului G si se

noteaza k(G); un graf cu un singur nod are conectivitatea 0.

Teorema 1.4.4. Fie n un ntreg pozitiv. Atunci exista k(n) N astfel nct orice graf

conex G cu cel putin k(n) muchii contine fie un lant cu cel putin n vrfuri fie un vrf de grad

mai mare sau egal cu n.

Altfel spus, orice graf conex suficient de mare contine un drum lung sau o stea2 mare.

Definitia 1.4.5. Un graf neconex este reuniunea mai multor subgrafuri conexe; subgrafurile

n perechi nu au noduri comune. Aceste subgrafuri conexe disjuncte sunt numite compo-

nentele conexe ale grafului.

Date fiind multimile A,B V si o multime X V E astfel nct orice AB drum sa

contina un vrf sau o muchie din X spunem ca X separa multimile A si B n G. De notat

ca acest fapt implica A B X. Mai general, spunem ca X separa G daca G \X nu mai

este conex, adica eliminarea multimii X mparte graful n doua sau mai multe componente

conexe. Daca X consta numai din vrfuri atunci spunem ca X este un separator.

1.5 Raze, cicluri finite si infinite

Un drum infinit de forma

v0, {v0, v1} , v1, {v1, v2} , v2, {v2, v3} , . . .

2Notiunea de stea este definita n Subparagraful 1.7.2

5

se numeste raza [ray], iar un drum de forma

. . . , v2, {v2, v1} , v1, {v1, v0} , v0, {v0, v1} , v1, {v1, v2} , v2, {v2, x3} , . . .

se numeste raza dubla [double ray]. Subrazele unei raze sau a unei raze duble se numesc

cozi. Formal orice raza are o infinitate de cozi, dar oricare doua din ele deosebindu-se doar

printr-un numar finit de vrfuri.

Doua raze R1 si R2 ntr-un graf G sunt echivalente daca nu exista un numar finit de

vrfuri care le separa. Se observa cu usurinta ca aceasta conditie are loc daca si numai daca

exista un numar infinit de R1R2 drumuri finite. Acest fapt la rndul sau este echivalent cu

existenta unei a treia raze care ar avea un numar infinit de vrfuri comune cu ambele raze,

R1 si R2. Clasele de echivalenta determinate de acesta relatie se numesc extremele [ends]

grafului; multimea tuturor extremelor grafului G notam prin (G). Daca o raza R apartine

unei extreme (G) atunci mai spunem ca R este o -raza.

u v

w

Q

R

x

Figura 1.5.5. Un graf infinit si R, Q doua raze duble, iar , extremele grafului.

Daca X este o multime de vrfuri sau de muchii din G spunem ca X separa multimea

V V (G) de extrema (G) daca oricare -raza care porneste din V intersecteaza

numaidect X. Sau, altfel spus, unica componenta conexa din G \X care contine extrema

si V sunt disjuncte.

Un drum este elementar daca, cu exceptia eventuala a extremitatilor, celelalte vrfuri

difera. Un drum elementar pentru care extremitatile sunt egale (coincid) se numeste ci-

clu. Totalitatea muchiilor unui ciclu se numeste circuit. Ciclurile pot fi finite sau infinite

spre exemplu, n Figura 1.5.5 u, {u, v} , v, {v, w} , w, {w, x} , x, {x, u} , u este un cilu finit, iar

v, {v, w} , w,Q, , R, v (muchiile ngrosate) este un cilu. infinit.

Lungimea drumului, deci si a cilului, este numarul de muchii ale acestuia; un ciclu de

lungimea k se numeste k-ciclu si se noteaza Ck.

Despre doua drumuri, deci si cicluri, se spune ca snt independente daca nu au nici un

vrf comun; exceptie fac extremitatile.

O muchie care uneste doua vrfuri ale unui ciclu nsa nu apartine acestuia se numeste

coarda.

6

1.6 Izomorfisme de grafuri

Definitia 1.6.1. Grafurile G1 = (V1, E1) si G2 = (V2, E2) snt izomorfe daca exista o

bijectie de la V1 la V2 cu proprietatea ca doua noduri u si v snt adiacente n G1 daca si

numai daca (u) si (v) snt adiacente n G2 pentru orice u si v din V1.

O asemenea functie se numeste izomorfism daca G1 6= G2 si automorfism n caz

contrar.

Din punct de vedere vizual, grafurile G1 si G2 snt izomorfe daca pot fi aranjate astfel

nct nfatisarea lor sa fie identica (desigur, fara a schimba adiacenta).

1.7 Tipuri speciale de grafuri

1.7.1 Grafuri complete

Definitia 1.7.1. Un graf este complet daca oricare doua vrfuri ale sale snt adiacente; se

noteaza Kn (n semnificnd numarul de vrfuri ale grafului.

K3 K4

K5 K5

Figura 1.7.6.

1.7.2 Grafuri bipartite

Definitia 1.7.2. Un graf este bipartit daca multimea vrfurilor sale V poate fi partitionata

n doua multimi disjuncte nevide, V1 si V2, astfel nct orice muchie din graf leaga un nod

din V1 cu un nod din V2 (nici un nod nu leaga doua noduri din V1 sau doua noduri din V2).

Un graf bipartit complet, Km,n, este un graf care are multimea vrfurilor partitionata

n doua submultimi de m si n noduri. Doua noduri sunt conectate daca si numai daca ele

snt n submultimi diferite.

7

Figura 1.7.7. Un graf bipartit.

Un graf de forma K1,n se numete stea; vrful din partitia cu un singur element se numeste

centrul stelei.

1.7.3 Arbori

Definitia 1.7.3. Un arbore este un graf conex neorientat care nu are cicluri simple.

Deoarece un arbore nu poate avea cicluri, un arbore nu poate avea bucle sau arce multiple.

Asadar, un arbore nu poate fi dect un graf simplu.

u v

w

Q

R

x

Figura 1.7.8. Totalitatea muchiilor ngrosate (creasta cu suportul Q) mpreuna cu extremele

si formeaza un arbore de acoperire.

1.7.4 Grafuri plane si planare

Definitia 1.7.4. Un graf G se numeste planar (sau inscriptibil n plan), daca el poate

fi reprezentat grafic pe un plan astfel nct toate muchiile sale sa se intersecteze numai n

vrfurile sale.

O astfel de reprezentare a grafului se numeste reprezentare planara.

Este evident ca un graf planar G si reprezentarea sa planara G snt doua grafuri izomorfe.

Din aceasta cauza uneori un graf planar se mai numeste graf plan.

Teorema 1.7.5. K5 nu este planar.

In calitate de caracteristica a reprezentarii plane a grafului se introduce notiunea de

fata.Fata n reprezentarea plana a grafului este o parte a planului limitata de un ciclu

8

simplu si care nu contine n interior alte cicluri. Ciclul simplu ce margineste o fata se

numeste frontiera fetei. Drept fata poate fi considerata si acea parte a planului situata n

afara reprezentarii plane a grafului plan, care este limitata n interior de un ciclu simplu si

nu contine alte cicluri, o astfel de fata se numeste fata infinita (sau exteriorara).

Fiecare graf are exact o fata exterioara.

Podul ce uneste ciclurile se numeste bariera.

Teorema 1.7.6 (formula lui Euler). Fie G un graf planar si conex. Atunci numarul de

vrfuri |V |, numarul de muchii |E| si numarul de fete inclusiv si cea infinita |F | snt legate

prin relatia

|V | |E|+ |F | = 2 (1.1)

Pentru fiecare graf G planar poate fi construit un nou graf G, numit graf dual. Acest

graf se construeste astfel: n interiorul fiecarei fete inclusiv cea infinita se alege cte un punct,

aceste doua puncte se unesc apoi printr-o latura numai daca fetele la care apartin au numai

o latura comuna, n caz contrar aceste puncte se unesc prin attea laturi cte laturi comune

au fetele.

... ...

Figura 1.7.9. Dualul unui graf finit (stnga) si a unui graf infinit (dreapta).

Daca {V1, V2} este o partitie a lui V , adica V1V2 = si V1V2 = V , multimea E(V1, V2)

se numeste taietura (sau cociclu).

Teorema 1.7.7. Fiind dat un graf planar G orice circuit din G este o taietura minimala n

G.

9

10

Capitolul 2

Introducere n teoria matroizilor

Matroizii reprezinta o generalizare a unor obiecte combinatorice cum ar fi grafurile, matrice,

spatii liniare si geometrii proiective. Ideea de matroid dateaza din 1935 si a fost introdusa

initial (H. Whitney [5]) drept o abstractizare a dependentei liniare si a proprietatilor ciclurilor

n grafuri. Amanunte despre istoria aparitiei si [mai mult a] dezvoltarii teoriei matroizilor pot

fi gasite n articolul Matroids: The Value of Abstraction care poate fi obtinut prin Internet

de la http://www.ams.org/featurecolumn/archive/matroids1.html.

In acest capitol snt prezentate exclusiv notiuni, definitii si rezultate de baza cu privire

la teoria matroizilor, care de fapt ntr-o mare parte pot fi gasite n [10].

2.1 Matroizi. Definitii preliminare.

2.1.1 Multimi independente

Matroizii pot fi definiti n foarte multe moduri: se cunosc circa (sau mai mult de) 50 de

definitii [13] echivalente, fiecare din ele fiind pretioasa prin faptul ca este mai comoda ntr-o

anume situatie dect celelalte ramase. Din punct de vedere practic, multe situatii cer acest

lucru. Snt des ntlnite cazuri cnd un punct de vedere este mai comod si mai eficient dect

alt punct de vedere.

Noi vom ncepem cu definitia data de H. Whitney [6].

Definitia 2.1.1. Fie S o multime arbitrara nevida si I o familie oarecare de submultimi din

S. Atunci M = (S, I) este un matroid daca si numai daca

(I1) I este nevida;

(I2) daca I1 I si I2 I1, atunci si I2 I;

(I3) daca I1, I2 I si |I1| = |I2| + 1, atunci exista un element x I1 \ I2 astfel nct si

I2 {x} I.

11

Elementele lui I se numesc multimi independente, celelalte submultimi ale lui S, adica

cele din 2S \ I, se numesc dependente.

Axioma (I2) poarta numele de axioma de mostenire (sau de ereditate) [hereditary

axiom], axioma (I3) axioma de interschimbare [exchange axiom], iar toate mpreuna:

de la (I1) pna la (I3) axiomele de independenta [independence axioms].

In legatura definitia de mai sus se impun mai multe remarci.

In primul rnd,

(I1*) I.

Intr-adevar, prin definitie X pentru orice multime X, iar aplicnd (I2) obtinem ca

I.

In al II-lea rnd, proprietatea (I3) poate fi generalizata astfel

(I3*) daca I1, I2 I si |I1| < |I2| < , atunci exista un element x I2 \ I1 astfel nct si

I1 {x} I.

Intr-adevar, fie I1, I2 I si |I1| < |I2| cu |I1| + 1 < |I2|, atunci alegem I2 I2 astfel

nct sa avem |I1| = |I2|+ 1. Din axioma (I2) rezulta ca si I2 este independenta, dar atunci

din (I3) reiese imediat ca exista un element x I2 \ I1 astfel nct si I1 {x} I. Deoarece

x I2 si I2

I2 avem ca x I2.

In al III-lea rnd, un matroid este, n particular, un complex simplicial (aceasta reiese

din axioma (I2)) asa ca a toate consideratiile privind complexele simpliciale ramn valabile

si pentru matroizi.

2.1.2 Baze

Definitia 2.1.2. O multime independenta maximala (n raport cu relatia de incluziune) se

numeste baza.

Corolarul 2.1.3. Fie M = (S, I) un matroid si B I. Atunci B este o baza a lui M daca

si numai daca

x S \B avem ca B {x} / I. (2.1)

Remarca 2.1.1. In cele ce urmeaza vom folosi notatiile B(M) sau, daca nu exista pericol

de confuzie, simplu B pentru multimea bazelor din din M.

Notiunea de baza a unui matroid este similara cu notiunea de baza a unui spatiu vectorial.

Vom arata ca au multe n comun. De exemplu, un matroid poate avea mai multe baze, dar

toate au aceeasi dimensiune (numar de elemente), la fel ca la un spatiu vectorial.

12

Lema 2.1.4. Daca B1, B2 B(M) atunci

|B1| = |B2| .

Demonstratie. Presupunem, prin reducere la absurd, ca |B1| < |B2|. Atunci din (I3), rezulta

ca exista un element x B2 \ B1 astfel nct si B1 {x} I. Ceea ce este evident absurd,

deoarece contrazice (2.1).

Altfel spus, orice doua baze au acelasi cardinal. Ceea ce, n cazul multimilor finite,

nsemana ca orice doua baze snt incomparabile (n raport cu relatia de incluziune), adica

nu exista B1, B2 B(M) astfel nct B1 B2 sau B2 B1.

Lema 2.1.5. Fie M un matroid pe S si B totalitatea bazelor acestuia. Atunci B verifica

urmatoarele proprietati

(B1) B este nevida;

(B2) daca B1, B2 B si x B1 \ B2, atunci exista un element y B2 \ B1 astfel nct si

(B1 \ {x}) {y} B.

Demonstratie. (B1) Din (I1) reiese ca I(M) 6= , iar din faptul ca

B = {I I : @J I : I J}

rezulta imediat (B1).

(B2) Fie B1, B2 B atunci din (I2), B1 \ {x} I, iar din Lema 2.1.4, |B1 \ {x}| = |B2|.

Aplicam (I3) si obtinem ca exista un element y B2 \ (B1 \ {x}) astfel nct si (B1 {x})

{y} I. (Deoarece x B1 \ B2 este evident ca y B2 \ B1.) Dar |B1 {x} {y}| = |B2|

si din Lema 2.1.4 obtinem ca B1 B.

De fapt multimea bazelor din M are proprietatea de interschimbare simetrica, adica n

loc de (B2) putem scrie

(B2*) daca B1, B2 B si x B1 \ B2, atunci exista un element y B2 \ B1 astfel nct si

(B1 \ {x}) {y} B si (B2 \ {y}) {x} B.

Teorema 2.1.6. Fie S o multime arbitrara nevida, fie B o familie oarecare de submultimi din

S care verifica proprietatile (B1), (B2) si fie I familia de submultimi (proprii si improprii)

ale elementelor din B. Atunci (S, I) este un matroid cu multimea bazelor B.

Pentru a demonstra teorema de mai sus, avem nevoie de urmatoarea lema.

Lema 2.1.7. Fie S o multime arbitrara nevida, fie B o familie oarecare de submultimi din

S care verifica proprietatile (B1) si (B2), atunci elementele din B snt echicardinale.

13

Demonstratie. Fie B1, B2 B. [Prin reducere la absurd] presupunem ca |B1| > |B2|, dar le

alegem astfel nct |B1 \B2| sa fie minim. Fie x B1 \ B2 atunci n virtutea proprietatii

(B2) exista un element y B2 \B1 astfel nct si (B1 \ {x}) {y} B. Evident,

|(B1 \ {x}) {y}| = |B1| > |B2| .

Dar

|((B1 \ {x}) {y}) \B2| < |B1 \B2| .

Ceea ce este n contrazice cu presupunerea ca |B1 \B2| este minim.

Demonstratia Teoremei 2.1.6. (I1) (B1) (I1).

(I2) Felul cum a fost construita familia I implica nemijlocit (I2).

(I3) [Prin reducere la absurd] presupunem ca axioma (I3) nu este verificata, adica I1, I2

I cu |I1| = |I2|+1 astfel nct oricare ar fi elementul x I2\I1 nu este adevarat ca I1{x} I

(I1 {x} nu este independenta).

Fie B1 B astfel nct I1 B1, fie B2 B astfel nct I2 B2 si fie ca |B2 \ (I2 B1)|

este minim. Daca x B2 \ (I2B1) atunci din (B2) rezulta ca exista un element y B1 \B2

astfel nct si (B2 \ {x}) {y} B. Insa

|((B2 \ {x}) {y}) \ (I2 B1)| < |B2 \ (I2 B1)|

ceea ce contrazice minimalitatea lui |B2 \ (I2 B1)|. DeciB2\(I2B1) = siB2\B1 = I2\B1.

Combinnd aceasta cu faptul ca I2 \B1 = I2 \ I1 (deoarece |I1| = |I2|+ 1) primim

B2 \B1 = I2 \ I1. (2.2)

Sa aratam ca B1 \ (I1 B2) este vida. [Prin reducere la absurd] presupunem ca exista un

element x B1 \ (I1 B2). Dar atunci din (B2) primim ca y B2 \ B1 astfel nct si

(B1 \ {x}){y} B. Evident, I1{y} (B1 \ {x}){y} este o multime independenta nsa

din (2.2) y I2I1, ceea ce este o contradictie. Astfel B1 \ (I1 B2) = si

B1 \B2 = I1 \B2 I1 \ I2. (2.3)

In virtutea Lemei 2.1.7, |B1| = |B2| asa ca |B1 \B2| = |B2 \B1|. De aici aplicnd (2.2) si

(2.3) primim

|I1 \ I2| |I2 \ I1|

ceea ce implica |I1| |I2|. Contradictie.

Incheiem acest paragraf cu un enunt rezumativ.

Corolarul 2.1.8. Fie S o multime arbitrara nevida, fie B o familie oarecare de submultimi

din S. Atunci B este multimea de baze ale unui matroid pe S daca si numai daca B verifica

proprietatile (B1), (B2)

14

2.1.3 Circuite

Definitia 2.1.9. Fie M = (S, I) un matroid. O multime dependenta minimala (n raport

cu relatia de incluziune) se numeste circuit.

Cu alte cuvinte, C S este un circuit daca si numai daca

x C avem ca C \ {x} I. (2.4)

[De notat ca] daca |C| = 1 atunci C \ {x} = I. Circuitul cu un singur element se

numeste bucla [loop].

In cele ce urmeaza vom folosi notatiile C(M) sau simplu C pentru multimea de circuite

ale unui matroid M .

Lema 2.1.10. FieM un matroid pe S si C totalitatea circuitelor acestuia. Atunci C satisface

urmatoarele proprietati:

(C1) / C;

(C2) daca C1, C2 C si C1 C2, atunci C1 = C2;

(C3) daca C1, C2 C, C1 6= C2 si x C1 C2, atunci exista un circuit C3 C astfel nct

C3 (C1 C2) \ {x}.

Demonstratie. (C1) si (C2) snt evidente. Sa demonstram (C3).

[Prin reducere la absurd] presupunem ca multimea (C1 C2) \ {x} nu contine nici un

circuit, dar atunci (C1 C2) \ {x} este o multime independenta. Din (C2) rezulta ca putem

alege asa un element y C2 astfel nct y C2 \ C1. Multimea C2 \ {y} este independenta.

Fie I cea mai mare multime independenta din C1 C2 care contine C2 \ {y}. Este evident

ca y / I. Pe de alta parte exista un z C1 \ C2 astfel nct z / I. Evident, y 6= z si prin

urmare

|I| |(C1 C2) \ {y, z}| = |C1 C2| 2 < |(C1 C2) \ {x}| .

Acum daca aplicam (I3*) pentru multimile independente I si C1 C2 \ {x} primim ca

e C1 C2 \ {x} astfel nct I e I. Cum I e C1 C2 am ajuns la contradictia ca

I este cea mai mare.

Remarca 2.1.2. (C3) este echivalenta cu

(C3*) daca C1, C2 C, C1 6= C2, x C1 C2 si y C1 \ C2, atunci exista un circuit C3 C

astfel nct y C3 (C1 C2 \ {x}).

Teorema 2.1.11. Fie S o multime arbitrara nevida, fie C o familie oarecare de submultimi

din S care verifica proprietatile (C1) - (C3) si fie I familia de submultimi ale lui S care nu

contin vreun element din C. Atunci (S, I) este un matroid cu multimea circuitelor C.

15

Demonstratie. Din constructia multimii I si (C1) rezulta (I1*), iar din (I1*) avem (I1). [Tot

din constructia lui I] daca I1 I nu contine nici un element din C atunci si aceasta ramne

valabil si pentru orice submultime I2 I1. De aici (I2). In scopul de a demonstra (I3)

consideram I1, I2 I cu |I1| = |I2|+ 1. [Prin reducere la absurd] presupunem ca x I2I1,

I1 {x} / I. Fie I3 I1 I2 si I3 I astfel nct |I3| > |I1| si |I1I3| sa fie minimal. Din

presupunerea ca nu are loc (I3) obtinem ca |I1I3| nu este vida, de aceea putem alege un

element y I1I3. Acum, pentru fiecare element z I3I1, consideram Tz = (I3 \ {z}) {y}.

Atunci Tz I1 I2 si |I1 \ Tz| < |I1I3|. Din felul cum ale I3 urmeaza ca Tz /I. Fie Cz Tz

un circuit. Este evident ca y Cz si z / Cz. Fie e I3I1. Daca Ce (I3I1) = atunci

Cz ((I1 I3) {y}) \ {e} I1, ceea ce este o contradictie. Prin urmare exista un element

f Ce (I3I1). Intruct x Ce Cf avem un circuit C (Ce Cf ) \ {z} I3 din (C3).

Ceea ce contrazice alegerea lui I3.

Corolarul 2.1.12. Fie S o multime arbitrara nevida, fie C o familie oarecare de submultimi

din S. Atunci C este multimea de circuite ale unui matroid daca si numai daca C verifica

proprietatile (C1)(C3).

2.1.4 Functia rang

Vom defini unui matroid M drept o functie r : 2S(M) N astfel nct r (X) este cardinalul

celei mai mari submultimi independente din X, iar n loc de r (S(M)) vom scrie r (M).

Lema 2.1.13. Fie M un matroid pe multimea S si r functia rang. Atunci r satisface

urmatoarele proprietati

(R1) daca X S atunci 0 r (X) |X|;

(R2) daca X Y S atunci r (X) r (Y );

(R3) daca X,Y S atunci r (X Y ) + r (X Y ) r (X) + r (Y ).

Demonstratie. Proprietatile (R1) si (R2) snt evidente; sa demonstram atunci proprietatea

(R3).

Fie B o multime independenta maximala din X Y si B o multime independenta

maximala din X Y astfel nct B B. Atunci B X si B Y snt submultimi

independente (aceasta rezulta din (I2)) ale multimilor X si Y . Prin urmare din (R1) si (R2)

rezulta ca |B X| r (X) si |B Y | r (Y ). Deci

r (X) + r (Y ) |B X|+ |B Y |

= |(B X) (B Y )|+ |(B X) (B Y )|

= |B (X Y )|+ |B (X Y )| .

16

Impreuna cu B (X Y ) = B si B (X Y ) = B avem ca

r (X) + r (Y ) |B|+ |B| = r (X Y ) + r (X Y ) .

Teorema 2.1.14. Fie S o multime arbitrara nevida, fie o functie r : 2S(M) N care verifica

proprietatile (R1)(R3) si fie I familia de submultimi X din S pentru care r (X) = |X|.

Atunci (S, I) este un matroid cu functia de rang r.

Pentru a demonstra teorema de mai sus, avem nevoie de urmatoarea lema.

Lema 2.1.15. Fie ca are loc ipoteza Teoremei 2.1.14. Daca X si Y sunt submultimi din S

astfel nct y Y \X, r (X y) = r (X), atunci r (X Y ) = r (X).

Demonstratie. Fie Y \X = {y1, y2, , yk}. Daca k = 1 lema are loc. Presupunem ca are

loc si pentru k 1. Atunci n baza presupunerii facute si (R3) primim

r (X) + r (X) = r (X {y1, y2, , yk1}) + r (X {yk})

r (X {y1, y2, , yk1}) + r (X)

r (X) + r (X) .

Intruct primul si mebru al inegalitatii coincide cu ultimul, deducem ca r (X {y1, y2, , yk1, yk}) =

r (X).

Demonstratia Teoremei 2.1.14. (I1) Mai nti observam ca daca n (R1) punem X = si

obtinem

0 r () || ,

deci r () = 0 = || si I; n consecinta (I1) se verifica.

(I2) Fie acum I I si I I. Atunci r (I) = |I| si din (R3) primim

r (I (I \ I )) + r (I (I \ I )) r (I ) + r (I \ I ) ,

iar punnd I = primim

r (I) + r () r (I ) + r (I \ I ) .

si cu att mai mult aplicnd faptul ca r (I \ I ) |I \ I | (conditia (R3)) obtinem

|I| r (I ) + r (I \ I ) |I |+ |I \ I | = |I| .

Intruct primul si ultimul membru ale inegalitatii coincid deducem ca r (I ) = |I |. Deci

I I, si conditia (I2) se verifica.

17

(I3) Prin reducere la absurd, vom presupune ca (I3) nu se verifica. Atunci exista I1, I2 I

cu |I1| = |I2|+ 1 astfel nct x I1 \ I2 nicidecum I2 {x} / I. Astfel x I1 \ I2

|I2|+ 1 > r (I2 {x}) r (I2) = |I2|

de unde r (I2 {x}) = |I2|, din Lema 2.1.15, r (I2) = r (I2 I1), dar r (I2) = |I2| si

r (I2 I1) r (I1) = |I1|. Astfel |I2| |I1| ceea ce este o contradictie.

Corolarul 2.1.16. Fie S o multime arbitrara nevida, fie o functie r : 2S(M) N. Atunci r

este functia rang a unui matroid pe S daca si numai daca verifica proprietatile (R1) - (R3).

Teorema 2.1.17. Fie M un matroid, fie r functia rang si fie X S(M). Atunci

(i) X este independenta daca si numai daca |X| = r (X) ;

(ii) X este o baza daca si numai daca |X| = r (X) = r (M);

(iii) X este un circuit daca si numai daca X este nevida si r (X \ {x}) = |X| 1 = r (X),

oricare ar fi x X.

Multimea H S se numeste hiperplan al matroiduluiM daca este multimea maximala

astfel nct r (X) < r (M). Este usor de observat din proprietatile functiei rang ca orice

hiperplan are rangul egal cu exact r (M) 1.

2.1.5 Operatorul de nchidere

Fie M = (S, I) un matroid, n cele ce urmeaza vom defini operatorul de nchidere al lui

M drept o functie f : 2S 2S astfel nct

f (X) = X {x S : C C(M) : x C X {x}}

sau (echivalent)[13, p. 11]

f (X) = {x S : r (X) = r (X {x})}

Exemplul 2.1.18. Fie Uk,n matroidul uniform pe multimea S, atunci

f (X) =

X, daca |X| < k;S, n celelalte cazuri.

Teorema 2.1.19. Fie S o multime arbitrara nevida si o functie f : 2S 2S. Atunci

M = (S, f) este un matroid daca si numai daca, oricare ar fi X Y S

18

(i) X f (X);

(ii) f (X) f (Y );

(iii) f (f (X)) = f (X);

(iv) daca x, y / f (X) si x f (X {y}), atunci y f (X {x}).

In termeni de operatori de nchidere notiunile de multime independenta, dependenta

si baza se definesc n felul urmator. Fiind data o multime X, daca @x X astfel nct

x f (X \ {x}) atunci X se numeste f-independenta sau, daca nu exista pericol de

confuzie, simplu independenta ( se considera ntotdeauna independenta). Daca f (X) = S

atunci X se numeste f-densa (densa). O f-baza (baza) este o multime independenta si

densa n acelasi timp.

2.2 Izomorfisme de matroizi

Definitia 2.2.1. Matroizii M1 = (S1, I1) si M2 = (S2, I2) snt izomorfi daca exista o

bijectie de la S1 la S2 cu proprietatea ca o submultime X S este independenta daca si

numai daca (X) I2. Se noteaza M1 =M2.

Exemplul 2.2.2. Fie S = {0, 1} atunci matroidul M1 = (S, {, {0}}) este izomorf ma-

troidului M2 = (S, {, {1}}).

2.3 Tipuri speciale de matroizi

Fie S o multime arbitrara nevida, n cele ce urmeaza vom trece n revista cteva din cele mai

populare clase de matroizi.

2.3.1 Matroidul trivial

Fie I = {} atunci M = (S, I) este un matroid, numit matroid trivial (sau grosier). Se

observa usor ca n acest matroid singura multime independenta este multimea vida. Rangul

matroidului trivial este 0, iar orice submultime cu un singur element din S este circuit; deci

buclele snt unicele circuite.

2.3.2 Matroidul discret

Fie I = 2S atunci M = (S, I) este un matroid, numit matroid discret. In acest matroid

toate multimile snt independente (multimile dependente lipsesc) si exista o singura baza:

nsasi multimea S; rangul acestui matroid este |S|.

19

2.3.3 Matroidul uniform

Fie k un ntreg astfel ca 0 k |S| si I familia de submultimi din S care au cel mult

k elemente. Atunci usor se verifica ca I satisface [cerintele] (I1) (I3) si deci M = (S, I)

este un matoid, numit matroidul uniform (sau k-uniform). Se noteaza Uk,n, unde n este

cardinalul lui S. Se obsera ca orice submultime de cardinalitatea k este o baza a lui Uk,n,

iar orice submultime de cardinalitate [strict] mai mare dect k este o multime dependenta.

In particular, un circuit este orice submultime de k + 1 elemente.

Exemplul 2.3.1. M = (S, {}) = U0,n si M =(S, 2S

)= Un,n.

Exemplul 2.3.2. Fie S = {0, 1, 2}, atunci

I(U2,3) = {{0, 1} , {0, 2} , {1, 2}} .

2.3.4 Matroidul vectorial

Fie V un spatiu vectorial peste un corp K, fie S = {v1, v2, . . . , vn} o multtime de vectori si

I = {I S : I este liniar independenta n V } .

AtunciM = (S, I) este un matroid, numitmatroid vectorial peste K. Bazele matroidului

M snt exact bazele multimii S sau, daca |S| > dimV , bazele spatiului vectorial V continute

n S. Faptul ca M este matroid se traduce exact prin proprietatea de schimbare a bazelor

unui spatiu vectorial. De fapt, acest exemplu justifica denumirea de baza a a multimilor

maximale independente dintr-un matroid.

Exemplul 2.3.3. Fie K = R, V = R2 si S ={~i,~j, ~i+ j

}, atunci

M ={S,{,~i,~j, ~i+ j, ,

{~i,~j},{~i, ~i+ j

},{

~i+ j,~j}}}

este matroidul vectorial pe S.

2.3.5 Matroidul matriceal

Fie A o matrice de dimensiune m n peste corpul K si S multimea indicilor coloanelor din

A. Definim structura (S, I) n felul urmator

I = {I S : multimea coloanelor date prin S contine doar coloane liniar independente} .

Pentru fiecare submatrice AT avnd coloanele aj pentru j T se stie ca fiecare multime

maxima de coloane liniar independente contine r (T ) = rang(AT ) coloane si astfel (S, I)

este un matroid.

20

In general, daca M este un matroid si exista o matrice A astfel nct multimile de

independenta ale lui M corespund coloanelor liniar independente ale lui A, atunci M se

numeste matroidul matriceal (sau matroidul vectorial al matricei A). Se noteaza

M[A].

Exemplul 2.3.4. Fie m = 3, n = 7, K = {0, 1} si

A =

1 2 3 4 5 6 71 0 0 1 0 1 1

0 1 0 1 1 0 0

0 0 1 0 1 1 0

.

Atunci S = {1, 2, 3, 4, 5, 6, 7} si I consta din toate multimile de un element, toate 21 de

perechi cu exceptia {1, 7} si urmatoarele 24 de triplete:

{1, 2, 3} , {1, 2, 5} , {1, 2, 6} , {1, 3, 4} , {1, 3, 5} , {1, 4, 5} , {1, 4, 6} , {1, 5, 6} ,

{2, 3, 4} , {2, 3, 6} , {2, 3, 7} , {2, 4, 5} , {2, 4, 6} , {2, 5, 6} , {2, 5, 7} , {2, 6, 7} ,

{3, 4, 5} , {3, 4, 6} , {3, 4, 7} , {3, 5, 6} , {3, 5, 7} , {4, 5, 7} , {4, 6, 7} si {5, 6, 7} .

2.3.6 Matroidul geometric

Fie M un matroid pe S, reamintim ca o bucla n M este un element x S astfel nct

r ({x}) = 0 (adica {x} este o multime dependenta, mai mult chiar, este un circuit, x f ()).

Doua elemente x1 si x2 care nu formeaza bucle se numesc paralele daca r ({x1, x2}) = 1

(sau {x1, x2} este un circuit, sau x1 f ({x2})). Paralelismul, ca si n cazul geometriei

Euclidiene, este o relatie de echivalenta.

Matroidul M este geometric daca nu are bucle si toate elementele paralele sint egale;

ceea ce nseamna ca toate submultimile de cardinalitatea cel mult 2 snt independente. Unii

numesc astfel de matroizi geometrii combinatoriale.

Exemplul 2.3.5. U0,n si U1,n nu snt geometrici, pe cnd U2,n si U3,n snt [geometrici].

2.3.7 Matroidul afin

Fie S o multime finita de puncte ntr-un spatiu afin. Atunci familia submultimilor afin

independente ale lui S are structura de matroid.

Reamintim ca un sistem de vectori {v1, v2, . . . , vk} din spatiul V peste corpul K snt

afin dependenti daca exista elementele a1, a2, . . . , ak din K astfel nctk

i=1 aivi = 0,ki=1 ai = 0 si

ki=1 |ai| 6= 0.

Exemplul 2.3.6. Fie S = {(0, 0), (1, 0), (2, 0), (0, 1), (0, 2), (1, 1)}, S R2. Atunci o submultime

X S este afin dependenta daca |X| 4 sau daca este {(0, 0), (1, 0), (2, 0)}, {(0, 0), (0, 1), (0, 2)}

sau {(0, 2), (1, 1), (2, 0)}. Aceast matroid este ilustrat n Figura 2.3.1.

21

(1, 0)

(2, 0)

(1, 1)

(0, 1) (0, 2)

y

x(0, 0)

Figura 2.3.1. Exemplu de matroid afin de rangul 3.

In exemplul de mai sus pe lnga faptul ca au fost indicate care multimi snt dependente

a mai fost data si o reprezentare grafica a matroidului respectiv, ceea ce nu a fost facut pna

acum n nici un exemplu. In cele ce urmeaza vom descrie regulile n baza carora putem

obtine reprezentarea grafica a oricarui matroid afin de rang mai mic ca 4:

(i) daca un element nu formeaza o bucla atunci el se reprezinta printr-un punct;

(ii) daca trei elemente ale matroidului formeaza un circuit, atunci ele se reprezinta prin

trei puncte coliniare sau incidente unei curbe (de exemplu circumferinta);

(iii) daca patru elemente ale matroidului formeaza un circuit, atunci ele se reprezinta prin

patru puncte coplanare.

Exemplul 2.3.7.

x1

x

xx x

xx6

5

7

43

2

x1

x

xx x

xx6

5

7

43

2

Figura 2.3.2. Matroidul Fano F7 (stnga) si matroidul non-Fano F7 (dreapta).

De notat ca nu orice diagrama cu puncte, linii si plane este reprezentarea geometrica a

unui careva matroid. De exemplu, Figura 2.3.3 nu reprezinta un matroid.

22

Intr-adevar, fie X = {1, 2, 3, 6, 7} si Y = {1, 4, 5, 6, 7}. Atunci r (X) = r (Y ) = 3,

r (X Y ) = 4 si cum r (X Y ) = 3 obtinem

r (X Y ) + r (X Y ) r (X) + r (Y ) ,

ceea ce e n contrazicere cu (R3).

Daca am face punctele {1, 6, 7} sa fie coliniare atunci Figura 2.3.3 ar fi un matroid pe

rangul 4.

1

4

6

2

5

7

3

Figura 2.3.3.

2.3.8 Matroizi grafici

Fie G = (V,E) un graf, fie T E o submultime de muchii si fie familia

I = {T E : subgraful GT nu contine cicluri} .

Se stie ca pentru orice T E, cardinalitatea unei multimi maxime de muchii care este

aciclica n GT este r (T ) = |V | c(GT ), unde c(GT ) este numarul de componente conexe

ale lui GT , si astfel, (E, I) este un matroid, numit matroidul ciclurilor ale grafului G

(sau matroidul ciclu al grafului G [16, p. 3]); se noteaza M(G). De fapt, acest exemplu

justifica denumirea de circuit a multimilor minimale dependente dintr-un matroid.

In general, dacaM este un matroid si exista un grafG astfel nct multimile de independenta

dinM corespund multimilor de arce aciclice ale lui G, adicaM=M(G), atunci matroidul

M se numeste grafic.

In capitolul urmator vom arata ca matroizii grafici sunt n acelasi timp si matroizi ma-

triceali.

Exemplul 2.3.8. Fie G = K3 atunci M(G) = U2,3.

Exemplul 2.3.9. Fie G pseudograf ilustrat n Figura 2.3.4

atunci

C(M(G)) = {1, {2, 3} , {2, 4, 5} , {3, 4, 5} , {5, 6, 7} , {2, 4, 6, 7} , {3, 4, 6, 7}} .

23

14

523

7

68

Figura 2.3.4.

e2

e2

e5

e3 e4

Figura 2.3.5.

Exemplul 2.3.10. Matroidul grafului ilustrat n Figura 2.3.5

este izomorf matroidului matricei

A =

[1 0 0 1 1

0 1 0 0 1

]

si deci M[A] pe lnga faptul ca este matriceal mai este si grafic.

2.3.9 Matroizi bicirculari

Fie G = (V,E) un graf, fie T E o submultime de muchii si fie familia

C = {T E : subgraful GT este o subdiviziune a unui graf ilustrat n Figura 2.3.6} .

Figura 2.3.6.

Atunci (S, C) este un matroid cu C multimea circuitelor, numit matroid bicircular. Se

noteaza B(G). Multimea bazelor sint mulmile maximale de muchii n care fiecare compo-

nenta conexa contine exact cte un circuit.

24

2.3.10 Matroizi partitie

Fie Si, i = 1, n, n multimi finite si disjuncte doua cte doua astfel nct S =n

i=1 Si si

I = {T S : i {1, 2, . . . , n} , |T Si| 1} .

Pentru orice T S, cardinalitatea unei multimi de independenta maximala din T esteni=1 |T S| si astfel (E,F ) este un matroid.

In general, daca M este un matroid si exista o multime S cu partitia {S1, S2, . . . , Sn}

astfel nct multimile de independenta ale lui M corespund multimilor de independenta din

S, atunci spunem ca M este un matroid partitie.

Incheiem acest paragraf cu Tabela 2.1 n care snt recapitulate tipurile de matroizi la care

ne vom referi cel mai des, n cele ce urmeaza.

Denumirea Notatie Multimile Bazele Circuitele

tipului independente

matroidul Uk,n submultimile cu cel submultimile cu submultimile cu

k-uniform mult k elemente exact k elemente exact k + 1 elemente

matroidul vectorial M[A] coloanele liniar coloanele maximal coloanele minimal

al unei matrice A independente liniar independente liniar dependente

matroidul ciclurilor M(G) multimile de muchii arborii de acoperire multimile de muchii

ale unui graf G fara cicluri care contin cicluri

matroidul bicircular B(G) multimile de muchii multimile de muchii multimile de muchii

al unui graf G fara subgrafuri maximale: fiecare care contin subgra-

homeomorfice celor componenta conexa furi homeomorfice

din Fig 2.3.6 are exact un ciclu celor din Fig 2.3.6

Tabela 2.1.

2.4 Operatii asupra matroizilor

2.4.1 Intersectia matroizilor

Definitia 2.4.1. Fie M1 = (S1, I1) si M2 = (S2, I2) doi matroizi, fie S = S1 S2 si fie

I = {I1 I2 : I1 I1 si I2 I2}. Atunci M = (S, I) este intersectia matroizilor M1 si

M2 si se noteaza M =M1 M2.

Exemplul 2.4.2. U2,3 U1,3 = U1,3.

Corolarul 2.4.3. M =M1 M2 este un matroid.

25

Demonstratie. Sa ne convingem ca definitia de mai sus este corecta si ca M = M1 M2

este un matroid; n acest scop verificam (I1)(I3).

(I1) I1 si I2, deci I si I 6= .

(I2) Fie I I si I I. Fie ca I = I1 I2, unde I1 I1 si I2 I2. Evident, I I1 si

I I2. In particular, din (I2), I I1. De aici putem scrie ca I

= I I2 si deci I I.

(I3) Fie I , I I si |I | = |I |+1. Alegem I

1, I

1 I1 si I

2, I

2 I2 astfel nct I = I

1I

2

si I = I

1 I

2 . Evident,

I I1 si I I1 x1 I

\ I astfel nct I {x1} I1

si

I I2 si I I2 x2 I

\ I astfel nct I {x2} I2.

Prin urmare I (I {x1}) I si I (I {x2}) I si deci fie ca punem x = x1 sau

x = x2, unde x I \ I , (I3) este verificata.

Teorema 2.4.4. Fie M1 = (S1, I1) si M2 = (S2, I2) doi matroizi. Atunci

(i) C(M1 M2) = C(M1) C(M2);

(ii) B(M1 M2) = {B1 B2 : B1 B(M1) si B2 B(M2)};

Teorema 2.4.5. Fie M =M1 M2. Daca B B(M), atunci

|B| = minXS1S2

{rM1(X) + rM2(S \X)} .

Propozitia 2.4.6. Fie Uk,n matroidul uniform pe multimea S si k1, k2 doi ntregi astfel nct

0 k1 n si 0 k2 n, atunci

Uk1,n Uk2,n =

Uk1,n daca k1 k2;Uk2,n daca k1 > k2.

2.4.2 Reuniunea matroizilor

Definitia 2.4.7. Fie M1 = (S1, I1) si M2 = (S2, I2) doi matroizi, fie S = S1 S2 si fie

I = {I1 I2 : I1 I1, I2 I2}. Atunci M = (S, I) este reuniunea (sau suma directa) a

matroizilor M1 si M2 si se noteaza M =M1 M2 (sau M =M1 M2).

Exemplul 2.4.8. U2,3 U1,3 = U3,3.

Exemplul 2.4.9. Suma directa a matroizilor grafici asociati celor doua componente conexe

ale grafului ilustrat n Figura 2.7.8 este matroidul ciclu al ntregului graf.

Corolarul 2.4.10. M =M1 M2 este un matroid.

26

Demonstratie. Sa ne convingem ca definitia de mai sus este corecta si ca M = M1 M2

este un matroid; n acest scop verificam (I1)(I3).

(I1) I1 si I2, deci I si I 6= .

(I2) Fie I I si I I. Fie ca I = I1 I2, unde I1 I1 si I2 I2. Atunci putem scrie

ca I = (I1 \ (I \ I)) (I2 \ (I \ I

)). De aici, ntruct I1 \ (I \ I) I1 si I2 \ (I \ I

) I2

(din (I2)), rezulta ca I I.

(I3) Fie I , I I, si |I | = |I | + 1. Atunci putem alege I

1, I

1 I1 si I

2, I

2 I2 astfel

nctI 1 = I 1 +1 sau I 2 = I 2 +1 si I = I 1 I 2, iar I = I 1 I 2 . Aplicnd (I3) primim

ca x1 I

1 \ I

1 astfel nct si I

1 {x1} I1 sau x2 I

2 \ I

2 astfel nct si I

2 {x2} I2.

In ambele cazuri, rezulta ca x I \ I astfel nct I {x} I.

Teorema 2.4.11. Fie M1 = (S1, I1) si M2 = (S2, I2) doi matroizi. Atunci

(i) C(M1 M2) = C(M1) C(M2);

(ii) B(M1 M2) = {B1 B2 : B1 B(M1), B2 B(M2)};

Teorema 2.4.12. Fie M =M1 M2. Daca X S, atunci

rM1M2(X) = minTX

{|X T |+ rM1(T S1) + rM2(T S2)} .

In particular, daca S1 S2 = , atunci

rM1M2(X) = rM1(X S(M1)) + rM2(X S(M2)).

Teorema 2.4.13. Fie M =M1 M2. Daca S1 S2 = , atunci

(M1 M2) =M1 M

2,

iar daca S1 = S2, atunci

(M1 M2) =M1 M

2.

Demonstratie. 1. Fie S1 S2 = . In cele ce urmeaza vom compara bazele matroizilor

(M1 M2) si M1 M

2.

B((M1 M2)) = {B : S \B B((M1 M2))}

= {S \B : B B((M1 M2))}

= {S \ (B1 B2) : B1 B(M1) si B2 B(M2)}

= {(S1 \B1) (S2 \B2) : B1 B(M1) si B2 B(M2)}

= {B1 B2 : B

1 B(M

1) si B

2 B(M

2)}

=M1 M2.

2. Fie S1 = S2 = S.

27

B((M1 M2)) = {B : S \B B((M1 M2))}

= {S \B : B B((M1 M2))}

= {S \ (B1 B2) : B1 B(M1) si B2 B(M2)}

= {(S \B1) (S \B2) : B1 B(M1) si B2 B(M2)}

= {B1 B2 : B

1 B(M

1) si B

2 B(M

2)}

=M1 M2.

Propozitia 2.4.14. Fie Uk,n matroidul uniform pe multimea S si k1, k2 doi ntregi astfel

nct 0 k1 n si 0 k2 n, atunci

Uk1,n Uk2,n =

Uk1+k2,n daca k1 + k2 n;Un,n daca k1 + k2 > n.

Teorema 2.4.15. Fie M = (S, I) un matroid. Atunci M nu este 2-conex daca si numai

daca exista o submultime proprie X S astfel nct I = {I1 I2 : I1 I(M|X) si I2 I(M\X)}.

Corolarul 2.4.16. Fie M un matroid, X1, X2, . . . Xn componentele conexe ale acestuia si

fie Mi =M|Xi, i = 1, n. Atunci

M =M1 M2 . . .Mn

si dacaM = N1N2 . . .Nk atunci k = n si exista o permutare a multimi {1, 2, . . . , n}

astfel nct Ni =M(i).

2.5 Dualitate

Teorema 2.5.1. Fie M un matroid si B(M) familia de complemente ale bazelor lui M,

B(M) = {S(M) \B : B B(M)} .

Atunci B(M) este multimea bazelor unui matroid pe S.

Demonstratie. In primul rnd demonstram ca B satisface urmatoarea conditie:

(B2**) daca B1, B2 B si x B2 \ B1, atunci exista un element y B1 \ B2 astfel nct si

(B1 \ {y}) {x} B.

Intruct B1 este o baza, B1 {x} contine un unic circuit C. Intruct C este dependenta,

iar B2 este independenta, C \ B2 6= si y C \ B2. Evident, y B1 \ B2. Intruct

(B1 \ y) {x} nu contine un circuit C, multimea (B1 \ y) {x} este independenta. In fine,

|(B1 \ y) {x}| = |B1|, deci este o baza.

28

Sa demonstram acum teorema. Intruct B(M) nu este vida, nu este vida nici B(M) si

deci (B1) este verificata. Fie B1 , B2 B

si x B1 \ B2 . Notam prin Bi = S(M) \ B

i ,

i = 1, 2. Atunci Bi B si B1 \ B

2 = B2 \ B1. Din (B2**), exista y B1 \ B2 astfel

nct (B1 \ y) {x} B. Deci y B1 \ B

2 si S(M) \ ((B1 \ y) {x}) B

. nsa

S(M) \ ((B1 \ y) {x}) B = (B1 \ y) {x} si putem deduce ca B

satisface (B2).

Definitia 2.5.2. Matroidul din teorema de mai sus se numeste dualul lui M si se noteaza

M.

In asa fel B(M) = B(M) si evident ca

Corolarul 2.5.3. M =M.

Exemplul 2.5.4. Fie matroidul uniform Uk,n. Bazele acestui matroid snt toate submultimile

de k elemente din S(Uk,n). Deci

Uk,n = Unk,n.

Propozitia 2.5.5. Fie M un matroid atunci

r (M) + r(M) = |S(M)| = |S(M)| .

Propozitia 2.5.6. Fie M = (S, I) un matroid si X S. Atunci

r(X) = |X| r (M) + r (S \X) .

Demonstratie. Fie I X si I S\X doua submultimi maximal independente nM siM,

respectiv. Atunci r(X) = |I| si r (S \X) = |I|. Fie B o submultime maximal independenta

din S \ I astfel nct I B. Deducem ca r (B) = rS \ I si r (S \ I) = r (M). Deci B este

o baza n B.

Notam prin B = S \ B. B este o baza n M si I B, iar B X = I. La fel si

I B, iar B (S \X) = I. Deci

B X = |B| \ |I|

si

|X| = |X B|+ |X B|

= |B| |I|+ |I|

= r (M) r (S \X) + r(X).

n cele ce urmeaza vom folosi notatiile C(M) sau simplu C pentru circuitele matroidului

dual si le vom numi cocircuite.

29

Lema 2.5.7. Fie M un matroid pe S, atunci C este un cocircuit al lui M daca si numai

daca S \ C este un hiperplan n M.

Demonstratie. Fie C un cocircuit al lui M. Atunci

r (S \ C) = r(C) + r (M) |C|

= |C| 1 + r (M) |C|

= r (M) 1

ntruct C este minimala n privinta r(C) = |C| 1, deducem ca S \ C este o

submultime maximala astfel nct

r (S \ C) = r (M) 1.

Deci S \ C este un hiperplan.

Lema 2.5.8. Daca C este un circuit si C este un cocircuit al matroidului M, atunci

|C C| 6= 1.

Demonstratie. Presupunem contrariul, fie C C = {x}. Atunci H = S \ C este un

hiperplan al lui M si x / H. Cum nsa C \ {x} H primim ca r (H) = r (H x). Ceea ce

este o contradictie.

Lema 2.5.9. Fie G un graf conex plan si G dualul sau geometric, atunci

M(G) =M(G).

Demonstratie. Fie G un graf conex plan, notam E = E(G) = E(G). Intrucat (G) = G

este suficient sa demonstram ca oricare ar fi un arbore de acoperire B al lui G muchiile

ramase E \B formeaza un arbore de acoperire al lui G. Dar asta e simplu:

1. E \ B formeaza un subgraf acicliic n G. Intr-adevar, [prin reducere la absurd]

presupunem ca E \ B contine un ciclu C. Atunci trebuie sa existe cel putin doua varfuri

u, v V (G) astfel ncat u C, iar v / C. Intrucat orice ciclu din G este o multime de

taiere n G concludem ca orice drum din G care uneste varfurile u si v trebuie sa intersecteze

C si prin urmare trebuie sa contina o muchie din E \B. Insa B este un arbore de acoperire

pentru G si deci contine n ntregime (fara vreo muchie din E \ B) un drum de la u la v.

Deci am primit o contradictie.

2. In baza formulei lui Euler avem ca

|V (G)| = 2 + |E| |V (G)| .

Intrucat |B| = |V (G)| 1 primim

|E(G) \B| = |E| |B|

= |E| |V (G)|+ 1

= |V (G)| 1

si E(G) \B este arbore de acoperire pentru G.

30

In baza lemei de mai sus se demonstreaza usor urmatoarea teorema.

Teorema 2.5.10. Daca G este un graf planar atunci matroidul M(G) este grafic.

Pe de alta parte, nu ntotdeauna dualul unui matroid grafic este si el grafic, de exemplu

Teorema 2.5.11. Nici unul din M(K5) si M(K3,3) nu este grafic.

Demonstratie. Presupunem, prin absurd, ca M(K5) = M(G). Putem considera ca, fara

a restrnge din generalitate, ca G este conex. Atunci, ntrucat M(K5) are 10 elemente si

rangul 4, G trebuie sa aiba 7 vrfuri si 10 muchii, iar media gradelor vrfurilor d(G) sa fie

mai mica decat 3. Fie v un varf de gradul 2 n G. Deducem ca M(G) = M(K5) are un

circuit de lungimea 1 sau 2, ceea ce este o contradictie. Asadar, M(K5) nu este grafic.

Analog se poate demonstra ca si M(K3,3) nu este grafic.

2.6 Minori

Din paragraful 1.2 al capitolului 1, cunoastem definitia minorului unui graf. Analog se

defineste si minorul unui matroid. Nu se schimba nici notatiile. Doar regulile de efectuare

ale operatiilor de eliminare si contractie se schimba si anume: dat fiind un matroidM pe S

si x S, operatia de eliminare se efectueaza dupa regula

M\ x = (S \ x, {I \ x : I I(M)}) , (2.5)

iar operatia de contractie...

M/x = (M \ x). (2.6)

Mai general, daca T S, atunci M \ T este un matroid pe multimea S \ T cu

I(M\ T ) = {I \ T : I I(M)} (2.7)

sau echivalent

I(M\ T ) = {(S \ T ) I : I I(M)} , (2.8)

iar M/T este un matroid pe multimea S \ T calculat dupa formula

M/T = (M \ T ) . (2.9)

Ceea ce ne spune ca exista o conexiune ntre aceste doua operatii si anume: ca aceste

doua operatii snt duale, n urmatorul sens

M/T = (M \ T ) (2.10)

si

M\ T = (M/T ). (2.11)

31

Exemplul 2.6.1. Fie S = {1, 2, 3, 4} si U2,4 matroidul uniform pe S, atunci

U2,4 \ 2 = ({1, 3, 4} , {, {1} , {3} , {4} , {1, 3} , {1, 4} , {3, 4}})

adica U2,3, iar

U2,4/2 = ({1, 3, 4} , {, {1} , {3} , {4}})

adica U1,2.

In baza acestui exemplu usor se demonstreaza propozitia urmatoare.

Propozitia 2.6.2. Fie S o multime arbitrara nevida si Uk,n un matroid uniform pe S,

k n < 0. Atunci orice minor al acestui matroid este si el uniform.

Demonstratie. Fie Uk,n matroidul uniform pe multimea S si x S, atunci

Uk,n \ x =

Uk,n1 daca k < n;Uk1,n1 daca k = n.

si

Uk,n/x =

Uk1,n1 daca k > 0;Uk,n1 daca k = 0. ,

Corolarul 2.6.3. Orice minor al unui matroid uniform este la fel un matroid uniform.

Teorema 2.6.4. Fie M un matroid pe S, fie T S si fie X S \ T . Atunci

(i) C(M\ T ) = {C S \ T : C C(M)};

(ii) rM\T (X) = rM(X).

In baza operatiei de eliminare a unui element sau a unei multimi de elemente se defineste

operatia de restrictie

M|T =M\ (S \ T ).

Teorema 2.6.5. Fie M un matroid pe S, fie T S si fie X T . Atunci

(i) C(M | T ) = {C T : C C(M)};

(ii) rM |T (X) = rM(X T );

(iii) fM |T (X) = fM(X) T .

32

Teorema 2.6.6. Fie M un matroid pe multimea S, fie T S si fie X S \ T . Atunci

(i) multimile independente ale matroidului M/T snt submultimi I din S \ T astfel nct

pentru orice baza B din M | T , multimea I B este independenta n M;

(ii) multimile maximal independente (bazele) ale matroidului M/T snt submultimi B din

S \ T astfel nct pentru orice baza B din M|T , multimea B B este o baza n M;

(iii) circuitele matroidului M/T snt submultimi de forma C \ T unde C C(M). La fel,

daca I este o multime independenta n M si C este un circuit din M , atunci C \ I este

un circuit n M/T ;

(iv) rM/T (X) = rM(X T ) \ rM(T );

(v) fM/T (X) = fM(X T ) \ T .

Lema urmatoare prezinta cteva proprietati ale operatiilor de eliminare si contractie.

Lema 2.6.7. Fie M un matroid pe S si T1, T2 S, T1 6= T2. Atunci

(i) (M\ T1) \ T2 =M\ (T1 T2) = (M\ T2) \ T1;

(ii) (M/T1)/T2 =M/(T1 T2) = (M/T2)/T1;

(iii) (M/T1) \ T1 = (M\ T1)/T2.

Se observa usor ca definitia operatiilor de eliminare si contractie snt similare att pentru

grafuri cat si pentru matroizi. Astfel este evidenta urmatoarea teorema.

Teorema 2.6.8. Fie G un graf si T E(G). Atunci

M(G) \ T =M(G \ T )

si

M(G)/T =M(G/T ).

Demonstratie. Fara a restrnge din generalitate putem considera ca |T | = 1, adica T contine

un singur element. Fie T = {e}. Se observa usor ca M(G) \ e = M(G \ e). Iar daca

e este o bucla atunci G/e = G \ e si M(G)/e = M(G) \ e despre care am demonstrat

deja ca este M(G \ e). Sa presupunem ca e nu este bucla. Atunci submultimea I din

E(G) \ e este aciclica daca si numai daca I {e} este aciclic n G. In asa fel, primim ca,

I(M(G)/e) = I(M(G/e)).

33

Teorema 2.6.9. Fie G un graf si T E(G). Atunci

M(G) \ T =M(G/T )

si

M(G)/T =M(G \ T ).

Corolarul 2.6.10. Orice minor al unui matroid grafic este grafic si orice minor al unui

matroid cografic este la fel cografic.

2.7 Conexitate

2.7.1 Matroizi 2-conecsi

Fie M = (S, I) un matroid si o relatie binara pe S definita n felul urmator

= {(x, y) S S : x = y sau C C(M) : x, y C} . (2.12)

Propozitia 2.7.1. Relatia este o relatie de echivalenta.

Demonstratie. Reflexivitatea si simetria relatiei snt evidente: reflexivitatea este asigurata

de conditia x = y, iar simetria de conditia x, y C. Sa ne convingem ca este tranzitiva.

Fie (x, y) si (y, z) ; x 6= y si y 6= z. Atunci exista circuitele C1 si C2 astfel nct

x C1, z C2 si C1 C2 6= (deoarece y C1 si y C2). Alegem C1 si C2 astfel nct

|C1 C2| sa fie minimal. [Prin reducere la absurd] presupunem ca nu exista asa un circuit

n M care sa contina si x si z.

Fie y C1 C2. In baza relatiei (C3*) exista un circuit C3 astfel nct x C3

(C1 C2) \ {y}. Mai mult chiar, z / C3 (deoarece am presupus ca @C C(M) : x, z C).

Intruct C3 * C1 adica C3 C2 6= reiese ca exista un element z C2 \ C1 si z C3.

Aplicnd (C3*) pentru C2, C3, z si z obtinem un circuit C4 astfel nct z C4 (C2 C3) \

{z}. Atunci C4 * C2 si (C3\C2)C4 6= , iar ntruct (C3\C2) C1 obtinem ca C1C4 6= .

Insa C1 C4 (C1 C2) \ z si |C1 C4| < |C1 C2|.

Asadar, am gasit nca doua circuite C1 si C4 astfel nct x C1, z C4 si C1 C4 6= ,

iar |C1 C4| < |C1 C2|. Dar acest fapt e n contrazicere cu alegerea multimilor C1 si C2.

Teorema este deci demonstrata.

Clasele de echivalenta determinate de relatia pe S se numesc componente de conex-

itate (sau mai simplu componente conexe) ale matroidului M.

Definitia 2.7.2. MatroidulM se numeste 2-conex, sau doar conex, daca relatia (definita

prin (2.12)) determina exact o clasa de echivalenta.

34

Exemplul 2.7.3. F7 este 2-conex.

Exemplul 2.7.4. Fie G graful ilustrat n Figura 2.7.7, atunci M(G) este 2-conex.

1

2

4

3

5

Figura 2.7.7.

Exemplul 2.7.5. Fie G graful ilustrat n Figura 2.7.8, atunci se observa usor M(G) are

doua componente de conexitate si deci nu este 2-conex.

2

1

3

4

5

7

6

Figura 2.7.8.

Urmatoarea definitie este echivalenta celei anterioare si de multe ori se va adeveri mai

utila (ntruct a enumera componentele de conexitate nu e o operatie ntotdeauna usoara).

Definitia 2.7.6. Un matroid M este conex daca x, y S(M) exista un circuit C astfel

nct x, y C.

Orice reuniune de componente conexe ale matroiduluiM se numeste separator. Propozitia

urmatoare este o consecinta imediata a definitiei conexitatii.

Propozitia 2.7.7. Fie M un matroid si X S(M). Atunci X este un separator daca si

numai daca C C(M) ori C X sau C S(M) \X.

Demonstratie. Fie X un separator, atunci x, y X exista un circuit C astfel nct x, y C

si C X, altfel X nu poate sa fie o componenta conexa, adica un separator.

Propozitia 2.7.8. Fie M un matroid pe S si X S. Atunci X este un separator daca si

numai daca

r (X) + r (S \X) = r (M) .

35

Demonstratie. 1. Evident, X S din (R3) primim

r (X) + r (S \X) r () + r (M) = r (M) .

Fie BX si BS\X submultimile maximal independente din X si S \ X, respectiv. Fie B =

BX BS\X . Daca X este separator atunci B este independenta n M (deoarece nu exista

nici un circuit care sa uneasca doua elemente din X si S \X) si deci

r (X) + r (S \X) = |BX |+BS\X

= |B| r (M) .

Necesitatea este demonstrata.

2. Pe de alta parte, daca X nu este un separator atunci trebuie sa existe un circuit C

care intersecteaza att X ct si S \ X. Fie BX si BS\X submultimi maximal independente

din X si S \ X, respectiv, astfel nct C X BX si C (S \ X) BS\X . Evident,

C B = BX BS\X si deci B este o multime dependenta. Iar ntruct BX si BS\X snt

maximale reiese ca r (B) = r (M). Si prin urmare

r (X) + r (S \X) = |BX |+BS\X

> |B| = r (M) .

Suficienta este deci verificata.

Propozitia 2.7.9. Fie M un matroid pe S si X S. Atunci X este un separator daca si

numai daca M\X =M/X.

Aceasta propozitie poate fi privita ca o consecinta a urmatoarei leme.

Lema 2.7.10. Fie M un matroid pe S si T S. Atunci M \ T = M/T daca si numai

daca

r (T ) + r (S \ T ) = r (M) .

Demonstratie. 1. Fie r (T ) + r (S \ T ) = r (M). In primul rnd observam ca I(M/T )

I(M\ T ). De aceea pentru a ne convinge ca M\ T = M/T vom demonstra incluziunea

inversa. Fie I I(M \ T ). Atunci exisa o baza B BM \ T astfel nct I B. Daca

completam B pna la o baza n M, sa zicem cu B. Atunci din

r (M) = |B|+ |B| = r (S \ T ) + |B|

reiese ca |B| = r (T ) si B este o baza n M|T . Prin urmare B este o baza n M/T , iar

I I(M/T ). Deci M\ T =M/T .

2. Fie M\ T = M/T , iar B o baza n M\ T = M/T . Daca BT este o baza n M|T

atunci B BT B(M) si

r (M) = |B|+ |T |

= r (M\ T ) + r (M|T )

= r (T ) + r (S \ T )

36

Propozitia 2.7.11. Fie M un matroid pe S si X S. Atunci X este un separator daca si

numai daca

r (X) + r(X) |X| = 0.

Pentru a demonstra propozitia de mai sus, avem nevoie de urmatoarea lema.

Lema 2.7.12. Fie M un matroid pe S si X S. Atunci

r (X) + r (S \X) r (M) = r (X) + r(X) |X| .

Demonstratie. Inlocuind r(X) cu relatia din Propozitia 2.5.6 si anume

r(X) = |X| r (M) + r (S \X)

primim o identitate. Iar din acest fapt rezulta justetea lemei.

Corolarul 2.7.13. Un matroid M este conex daca si numai daca M este conex.

In primul rnd reamintim urmatorul criteriu (de care ne vom folosi pe tot parcursul

paragrafului).

Propozitia 2.7.14. Fie G un graf fara bucle. Atunci G este 2-conex daca si numai daca

e, g E(G) exista un ciclu C astfel nct e, g E(C).

Propozitia 2.7.15. Fie G un graf fara bucle cu cel putin 3 vrfuri. Atunci G este 2-conex

daca si numai daca M(G) este conex.

2.7.2 Matroizi k-conecsi

Definitia 2.7.16. Fie M = (S, I) un matroid, fie r functia rang a acestuia si k un ntreg

arbitrar. Atunci partitia (X1, X2) a multimii S este o k-sectiune (Tutte) daca si numai

daca

(i) min|X| , |Y | k;

(ii) r (X) + r (Y ) r (M) k 1.

DacaM are o k-sectiune atunci spunem ca este k-separat (sau k-separabil). DacaM

este k-separabil atunci numarul (M) = min {k : M este k-separabil} se numeste conectiv-

itatea matroidului M. Evident, M este 2-conex daca si numai daca (M) 2. In general,

daca k este un ntreg mai mare dect 1, atunci spunem caM este k-conex daca (M) k.

Propozitia 2.7.17. Fie M un matroid. Atunci (M) = (M).

37

Demonstratie. Fie M = (S, I) un matroid si X S. Atunci aplicnd Lema 2.7.12 si forma

duala a acesteia primim

r (X) + r (S \X) r (M) = r (X) + r(X) |X|

= rX + rS \X rM.

Astfel (X,S \X) este o k-separatie a lui M daca si numai daca este o k-separatie a lui

M.

Propozitia 2.7.18. Fie M = (S, I) un matroid k-conex cu cel putin 2(k 1) elemente.

Atunci fiecare circuit sau cocircuit al lui M are cel putin k elemente.

Demonstratie. Daca pentru un k < k, M are o submultime de cardinalul k si care este

un circuit sau un cocircuit, atunci partitia (X,S \ X) va fi o k-separatie. Ceea ce e n

contrazicere cu faptul ca M e k-conex.

Propozitia 2.7.19. FieM = (S, I) un matroid k-conex cu cel putin 2k1 elemente. Atunci

M contine o submultime X de cardinal k care este n acelasi timp si circuit si cocircuit.

Corolarul 2.7.20. FieM un matroid. Daca (M) = atunciM este matroidul uniform.

Mai mult chiar,

(Uk,n) =

k + 1 daca n 2k + 2;

n k + 1 daca n 2k + 2;

n celelalte cazuri.

Acum sa definim alte tipuri de separatii si conexitati. O partitie (X,Y ) a multimii S

pe care este definit un matroid M avnd functia rang r, se numeste k-separatie verticala

daca

(1) min {r (X) , r (Y )} k;

(2) r (X) + r (Y ) r (M) k 1.

Partitia (X,Y ) se numeste k-separatie ciclica daca

(1) M|X si M|Y contin un circuit;

(2) r (X) + r (Y ) r (M) k 1.

Conectivitatea verticala k(M) a lui M este cel mai mic k pentru care M este k-separabil

vertical sau r (M) n caz contrar. Conectivitatea ciclica (M) a lui M este cel mai mic k

pentru care M este k-separabil ciclic sau |S| r (M) n caz contrar. Despre un matroid

M spunem ca este k-conex vertical (k-conex ciclic) daca 2 k k(M) (2 k (M),

respectiv).

Propozitia 2.7.21. Fie M = (S, I) un matroid, fie (M) < si fie k un numar natural

arbitrar. Atunci M este Tutte k-conex daca si numai daca este n acelasi timp vertical

k-conex si ciclic k-conex.

38

2.8 Reprezentabilitatea matroizilor

2.8.1 Reprezentabilitatea peste corpuri finite

Definitia 2.8.1. Fie M un matroid si K un corp. Atunci M este reprezentabil peste

corpul K (sau K-reprezentabil) daca si numai daca exista o matrice A cu elemente din K

astfel nct M=M[A].

Exemplul 2.8.2. Matroidul grafic din Exemplul 2.3.10 este GF (2)-reprezentabil, unde GF (2)

este corpul Galua.

Exemplul 2.8.3. U2,4 este GF (3)-reprezentabil ntruct este izomorf matroidului matricei

A =

[1 0 1 1

0 1 1 2

].

Daca M este un matroid K-reprezentabil si A este matricea, cu elemente din K, gratie

careiaM este reprezentabil, atunciA se numestematricea reprezentativa (sauK-reprezentarea)

a lui M.

De notat ca orice matroid reprezentabil poate avea mai multe matrici reprezentative peste acelasi corp.

Propozitia 2.8.4. Fie M un matroid si K un corp. Daca M este K-reprezentabil, atunci

orice K-reprezentare (nenula) a lui M poate fi adusa la o matrice de forma [Ir|D] (unde

Ir este matricea unitate de tipul r r, D este o matrice oarecare de tipul r (n r) cu

elemente din K, n este numarul de elemente ale matroidului M, iar r = r (M)) astfel nct

M=M [Ir|D].

Demonstratie. 1. Fie A o K-reprezentare a lui M, atunci A poate fi adusa la forma [Ir|D]

prin pivotarea gaussiana.

2. Pentru a demonstra ca M = M [Ir|D] sau ca (echivalent) M[A] = M [Ir|D] este

suficient sa mentionam ca operatiile de:

(i) schimbare a doua linii (sau coloane) ntre ele;

(ii) nmultire a unei linii (sau coloane) cu un element diferit de zero din K;

(iii) nlocuire a unei linii r cu suma r + r, unde r este o linie arbitrara din A;

(iv) suprimare a liniei care contine doar zerouri (numai daca ea nu este unica linie),

nu modifica matroidul M[A].

39

DacaM este un matroid K-reprezentabil, atunci [Ir|D] se numestematricea reprezen-

tativa standard (sau K-reprezentarea standard) a lui M. Daca n loc de D punem

matricea D# capatata din D prin nlocuirea elementelor diferite de zero cu 1, atunci[Ir|D

#]

este matricea reprezentativa partiala (sau K-reprezentarea partiala) a lui M.

Propozitia 2.8.5. Fie M un matroid si K un corp. Daca M este K-reprezentabil atunci si

M este K-reprezentabil. In particular, daca M este reprezentat peste K de matricea [Ir|D]

atunci M este reprezentat peste K de[DT |Inr

].

In cele ce urmeaza snt prezentate unele rezultate referitoare la reprezentabilitatea ma-

troizilor peste cmpurile finite.

Teorema 2.8.6. Fie K un corp. Atunci

(i) F7 este F -reprezentabil daca si numai daca caracteristica corpului K este 2;

(ii) F7 este F -reprezentabil daca si numai daca caracteristica corpului K este diferita de

2.

Pentru a demonstra teorema de mai sus, avem nevoie de urmatoarele leme.

Lema 2.8.7. Fie K un corp si matricea

DF =

0 1 1 1

1 0 1 1

1 1 0 1

cu elemente K. Daca caracateristica corpului K este 2, atunci M[I3|DF ] = F7, daca nsa

caracteristica corpului K nu este 2, atunci M[I3|DF ] = F7 .

Lema 2.8.8. Fie M {F7, F

7

}si K un corp. Daca M este K-reprezentabil atunci M =

M [I3|DF ], unde DF este matricea din Lema 2.8.7.

Teorema 2.8.9. Fie K un corp finit si k un ntreg mai mare dect 1. Atunci U2,k este

K-reprezentabil daca si numai daca |K| k 1.

Demonstratie. Fie A = [I2|D] o K-reprezentare standard a lui U2,k. Evident, orice coloana

a matricei D nu este de fapt altceva dect o combinatie liniara de forma

a1

[1

0

]+ a2

[0

1

],

unde a1, a2 K. Cum nsa M[A] trebuie sa fie izomorf cu U2,k nu orice combinatie de acest

tip este buna pentru D ci numai cele mutual independente.

40

Fara a restrnge generalitatea putem considera a1 = 1, ceea ce ar nsemna ca prima linie

a matricei D e formata numai din 1. Atunci linia a doua trebuie sa contina elemente mutual

diferite si nenule (caci daca macar doua snt egale atunci primim doua coloane egale, adica

liniar dependente, iar daca punem un element nul atunci primim coloana

[1

0

]). Prin urmare

k 2 |K| 1, adica |K| k 1.

Corolarul 2.8.10. Fie q un numar prim. Atunci matroizii U2,q+2 si Uq,q+2 nu snt GF (q)-

reprezentabili, unde GF (q) este corpul Galua.

De notat ca nu orice matroid este reprezentabil, de exemplu

Propozitia 2.8.11. Matroidul lui Vamos V8 nu este reprezentabil peste nici un corp.

Propozitia 2.8.12. Matroidul non-Pappus nu este reprezentabil peste nici un corp.

Teorema 2.8.13. Fie M un matroid. Atunci M reprezentabil peste GF (2) daca si numai

daca nu are un minor izomorfic cu U2,4.

In legatura cu teorema de mai sus se impun mai multe remarci.

In primul rnd, matroizii GF (2)- si GF (3)-reprezentabili se numesc binari si ternari,

respectiv.

In al II-lea rnd, minorii care mpiedica un tip anumit de matroizi sa fie K-reprezentabili,

pentru un corp K fixat se numesc minori imposibili pentru K-reprezentabilitate.

Asadar, n lumina acestor noi termeni Teorema 2.8.13 ne spune ca unicul minor imposibil

pentru clasa matroizilor binari este U2,4.

Teorema 2.8.14. Fie K un corp de caracteristica mai mare ca 2. Atunci F7 si F 7 snt

minori imposibili pentru clasa matroizilor K-reprezentabili.

Teorema 2.8.15. Unicii minori imposibili pentru clasa matroizilor ternari sint U2,5, U3,5,

F7 si F7 .

2.8.2 Matroizi binari

In acest paragraf snt prezentate doua proprietati interesante ale matroizilor binari. Ream-

intim ca matroizii binari snt matroizi GF (2)-reprezentabili.

Propozitia 2.8.16. Fie M un matroid binar, fie C C(M) si A una din matricele GF (2)-

reprezentative ale lui M, atunci

AC = 0, unde

AC este suma coloanelor din A core-

spunzatoare elementelor circuitului C.

41

Demonstratie. Fie c1, c2, ..., ck coloanele din A corespunzatoare elementelor circuitului C.

Intruct C este o multime dependenta rezulta ca c1, c2, . . . , ck snt liniar dependente, adica

a1, a2, . . . , ak GF (2), nu toate nule astfel nct

a1 c1 + a1 c2 + . . .+ ak ck = 0.

Distingem urmatoarele cazuri.

1. Fie ca a1 = a2 = . . . = ak = 1, atuncik

i=1 ai ci =

AC = 0.

2. Fie ca nu toti a1, a2, . . . , ak snt 1, atunci

ki=1

ai ci =mki=1

ai ci = 0,

unde mk < k. Prin urmare {c1, c2, ..., ck} contine o submultime care la fel este liniar depen-

denta, dar atunci C nu este minimal dependenta. Contradictie.

Lema 2.8.17. Fie M un matroid binar. Daca C1 si C2 snt doua circuite distincte, atunci

C1 M C2 este o reuniune de circuite mutual disjuncte.

Demonstratie. Fie A o matrice reprezentativa a lui M peste GF (2) fie C un circuit n M.

Atunci, din Propozitia 2.8.16,

C = 0, adica suma coloanelor matricei A corespunzatoare

elementelor acestui circuit este zero (vectorul nul). Pe de alta parte, daca despre X S(M)

se stie ca suma coloanelor corespunzatoare este la fel vectorul nul, adica este dependenta,

atunci spunem ca X contine un circuit C . Mai mult chiar, si coloanele X \C , daca exista,

n suma fac vectorul nul. In aceste conditii, multimea X poate fi privita ca o reuniune de

circute disjuncte.

Fie C1, C2 C(M) si C1 6= C2. Atunci C1 M C2 6= . Iar tinnd seama de consideratiile

de mai sus,

AC1 = 0 si

AC2 = 0. Acum, ntructA

C1 =A

C1 \ C2 +A

C1 C2 = 0,

rezulta ca daca linia r a coloanei

AC1 C2 este 1, atunci printre coloanele C1 \C2 trebuie

sa fie un numar impar de coloane care sa contina 1 n rndul r. Acelasi rationament este

valabil si pentru C1 \ C2, deoareceA

C2 =A

C2 \ C1 +A

C1 C2 = 0.

Iar intruct impar + impar = par, rezulta ca

A

C1 M C2 =A

(C1 \ C2) (C2 \ C1) = 0.

42

Propozitia 2.8.18. FieM un matroid binar, iar C si C un circuit si un cocircuit, respectiv.

Atunci |C C| este par.

Demonstratie. Fie CC 6= (caci de altfel teorema este demonstrata) si x CC. Atunci

exista o baza B n M astfel nct C \ {x} B. Fie B = S \ B si A = [Ir|D] este o

reprezentare peste GF (2) a luiM, astfel nct coloanele din Ir corespund elementelor din B.

Atunci M =M[DT |Inr] si coloana x din DT are 1 n pozitiile corespunzatoare vectorilor

din Inr care se contin n C \ {x}. Intruct C este circuit n M, rezulta ca

AC = 0. Si

suma aceasta are 0 n linia x. Ceea ce nseamna ca exista un numar impar de coloane din

C \ {x} avnd 1 n aceasta linie. Prin urmare C \ {x} si C \ {x} au un numar impar de

elemente comune, adica interseca acestora va avea un numar par de elemente.

Teorema 2.8.19. Fie M un matroid. Atunci urmatoarele afirmatii snt echivalente

(i) M este binar;

(ii) daca C este un circuit, iar C un cocircuit, atunci |C C| este par;

(iii) daca C1 si C2 snt doua circuite distince atunci C1 M C2 contine un circuit;

(iv) daca C1 si C2 snt doua circuite distince atunci C1 M C2 este o reuniune de circuite

mutual disjuncte;

(v) diferenta simetrica a oricaror circuite (cel putin 2) ori este vida sau contine un circuit;

(vi) diferenta simetrica a oricaror circuite este o reuniune de circuite mutual disjuncte;

(vii) daca B este o baza, iar C un circuit atunci C =MeC\B C(e, B);

(viii) exista o baza B a lui M astfel nct daca C un circuit atunci, atunci C =MeC\B

C(e, B);

Lema 2.8.20. Daca matroidulM nu este K-reprezentabil atunci niciM nu este K-reprezentabil.

Teorema 2.8.21. Orice matroid grafic este binar.

Demonstratie. Fie G = (V,E) un graf cu m vrfuri si n muchii. Pentru a arata ca M(G)

este binar, este suficient sa gasim o matrice A (cu n coloane) peste corpul GF (2) astfel

nct M[A] sa fie izomorf matroidului M(G). In acest scop formam matricea de incidenta

vrfuri-muchii A = (aij) a lui G, dar putin modificata, n felul urmator

aij =

1 daca muchia ej nu este o bucla si eeste incidenta vrfului vi;0 n celelalte cazuri.

Se observa ca coloanele corespunzatoare buclelor contin doar zerouri (vectorul nul).

43

Pentru a demonstra ca M(G) = M[A], este suficient sa aratam ca o multime X de

coloane din A este liniar dependenta daca si numai daca X contine un ciclu n G. Din acest

motiv vom parcurge urmatorii doi pasi.

1. Presupunem ca X contine muchiile unui ciclu C. Daca C este o bucla, atuci coloana

corespunzatoare este vectorul nul si deci X este liniar dependenta. Daca C este o pereche

de muchii paralele atunci coloanele corespunzatoare snt identice si deci iarasi: X este liniar

dependenta. In sfrsit, daca C este un k-ciclu si k > 2, atunci fiecare muchie din C este

incidenta cu exact doua vrfuri din C. Adica orice rnd contine n aceste coloane exact doua

unitati. Cum nsa n GF (2), 1 + 1 = 0 deducem ca suma vectorilor (cloanelor) din X este

0 si deci: X este liniar dependenta.

2. Presupunem ca X este o multime liniar dependenta de coloane din A. Fie D X

liniar dependenta, dar minimala (n raport cu relatia de incluziune), adica orice submultime

proprie a lui D este independenta. Daca D contine o coloana nula atunci aceasta coloana

corespunde unei bucle (ntruct vrfurile izolate snt excluse). Daca nsa D nu contine o

coloana nula atunci deoarece D este minimal dependenta rezulta ca suma coloanelor din D

este zero, deci fiecare rnd contine exact doi de 1. Deci D contine un ciclu.

44

2.8.3 Matroizi regulati

In capitolul precedent Matroizii regulati snt un caz particular al matroizilor reprezentabili.

Mai precis spus, proprietatea de a fi regulat este opusa proprietatii de a nu fi reprezentabil

peste nici un corp asa cum, de exemplu, proprietatea de simetrie este opusa proprietatii de

antisimetrie. De aceea putem spune ca matroizii care nu snt reprezentabili peste nici un

corp (matroidul lui Vamos, non-Pappus) snt antiregulati.

Definitia 2.8.22. FieM un matroid. Se spune caM este regulat daca si numai daca este

reprezentabil peste orice corp K.

Aceasta definitie este nsa prea abstracta si nu este practica: nu va putea fi folosita n

calitate de instrument atunci cnd vom dori sa aratam ca un matroid este regulat. De aceea,

n cele ce urmeaza ne vom folosi de urmatoarea definitie.

Definitia 2.8.23. Fie M un matroid. Se spune ca M este regulat daca exista un matroid

matriceal M[A] peste R izomorf matroidului M cu A total unimodulara.

Definitia 2.8.24. Fie A o matrice cu elemente din R. Se spune ca A este total uni-

modulara daca si numai daca determinantul oricarei submatrice patratica este 0, 1 sau

1.

Lema 2.8.25. Fie A o matrice total unimodulara, fie aij A un element arbitrar nenul si

fie B matricea capatata din A n urma pivotarii dupa aij. Atunci B este total unimodulara.

Demonstratie. Fie A si B doua submatrice patratice ale matricelor A si B, respectiv. Tre-

buie sa aratam ca detB {0, 1,1}. [In acest scop] notam prin Il multimea indicilor liniilor

submatricei A (adica multimea indicilor liniilor din A care intra n componenta submatricei

A) si prin Ic multimea indicilor coloanelor submatricei B. Distingem urmatoarele cazuri:

1. Fie i Il, atunci |detA| = |detB|; si deci detB {0, 1,1}.

2. Fie j Ic, iar i / Il, atunci B contine o coloana (coloana j) a carei elemente snt

toate nule; deci det(B) = 0.

3. Fie i Il si j Ic. La fel ca si n cazul precedent, coloana j consta doar din zerouri,

cu exceptia elementului pivot (bij = 1). Avnd n vedere acest fapt si notnd cu B matricea

obtinuta prin suprimarea liniei i si coloanei j din matricea B, primim ca detB = detB.

Dar atunci notnd prin A matricea obtinuta din A n acelasi fel ca si B din B si aplicnd

rezultatul cazului 1 avem ca |det(A)| = |det(B)|. Prin urmare detB {0, 1,1}

Lema 2.8.26. Fie M un matroid de rang r diferit de zero. Atunci M este regulat daca

si numai daca exista un matroid matriceal M[A] peste R cu A total unimdulara de forma

[Ir|D] izomorf matroidului M.

45

Demonstratie. Fie M un matroid regulat. Atunci M = M[A] unde A este o matrice cu

elemente din R total unimodulara. In virtutea Lemei 2.8.25 matricea A, prin operatia de

pivotare, poate fi adusa la forma [Ir|D] care la fel este o matrice total unimodulara.

Teorema 2.8.27. Fie M un matroid regulat. Atunci M este regulat.

Demonstratie. Fie M un matroid regulat. Atunci (din Lema 2.8.26) exista o matrice A cu

elemente din R total unimodulara astfel nct M[A] = M. Prin definitie M = [DT |Inr]

care la fel este total unimodulara.

Stergnd o coloana dintr-o matrice total unimodulara nu afecteaza unimodularitatea aces-

teia. Combinnd aceasta observatie cu rezultatul anterior ajungem la urma toarea concluzie.

Corolarul 2.8.28. DacaM este un matroid total unimodular, atunci orice minor al acestuia

este total unimodular.

Lema 2.8.29. Fie D1 o matrice cu elemente din {0, 1,1} si K un corp de caracteristica

diferita de 2. Presupunem ca [Ir|D1] este K-reprezentarea standard a unui matroid binarM.

Presupunem ca [Ir|D2] este capatata din [Ir|D1] n urma pivotarii dupa un element nenul

din [Ir|D1]. Atunci orice element al matricei D2 este din {0, 1,1}.

Demonstratie. Este clar ca elementele din linia r si coloana s snt din {0, 1,1}. Fie ca

i 6= r si j 6= s. Reamintim ca fiecare element dij din [Ir|D 2] se obtine dupa formula dij =

dijdisdrsdrj. Intruct toate elementele matricei D1 snt din {0, 1,1} si drs 6= 0 dupa o simpla

enumerarea si verificare nlocuire a caurilor dij poate lua valori din {0, 1,1, 2,2}.

Teorema 2.8.30 (Tutte). FieM un matroid. Atunci urmatoarele afirmatii snt echivalente

(i) M este regulat;

(ii) M este izomorf unui matroid matriceal M[A] peste R al carui matrice A este total

unimodulara;

(iii) M este reprezentabil peste GF (2) si peste un c