Matroid

Из Википедије, слободне енциклопедије

Овом чланку или једном његовом делу је потребно сређивање. Ово подразумева категоризацију, унутрашње повезивање, разламање текста и слична уређивања, како би се добио квалитетнији чланак.       Погледајте како се мења страна за помоћ, или страну за разговор. Уклоните ову поруку када завршите.

Садржај 1 Osnovna definicija 2 Teorema 1. 2.1 Dokaz: 3 Teorema 2. 3.1 Dokaz: 4 Види још

[уреди] Osnovna definicija

Matroid (MATROID) – je uređeni par M=(S,I) formiran na sledeći način:

1. Skup S je konačan.
2. Neka je I – neprazna familija podskupova skupa S ( koji se nazivaju nezavisnim podskupovima ) takvih da ako je B∈I i A⊆B, tada je A∈I. Ako familija I zadovoljava ovu osobinu tada je nazivamo nasleđenom (HERADITARY). Primetimo da prazan skup Ø obavezno pripada familiji I.
3. Ako je A∈I, B∈I i |A| < |B|, tada postoji element x∈A-B, tako da je A∪{x}∈I. Govorimo da struktura M zadovoljava osobinu zamene (EXCHANGE PROPETY).

Temin “MATROID” je uveo Vitni Hasler (HASSLER WHITNEY). On je proučavao matrične matroide, čiji su elementi S redovi zadate matrice. Skup redova je nazavistan, ako su oni linearno nezavisni u običnom smislu. Lako se pokazuje da ova struktura definiše matroid.

Kao suštinu drugog primera matroida razmotrimo matroid grafa M_G=(S_G,I_G), koji je definisan pomoću pojma neorijentisanog grafa G=(V,E), gde je:

• S_G – skup E ivica grafa G,
• Ako je A – podskup skupa E, tada je A I_G tada i samo tada kada je A necikličan tj, skup ivica A je nezavistan tada i samo tada kada podgraf G_A=(V,A) obrazuje šumu.

[уреди] Teorema 1.

Ako je G=(V,E) – neorijentisani graf tada je MG=(S_G,I_G) – matroid.

[уреди] Dokaz:

Očigledno je da je S_G=E – konačan skup. Osim toga I_G – je nasledna familija ukoliko je podskup šume takođe šuma. Drugim rečima, odstranjivanje ivica iz acikličnog skupa ivica grafa ne može dati cikličan skup.

Na taj način ostaje nam da pokažemo da struktura M_G odgovara osobini zamene. Pretpostavimo da su G_A=(V,A) i G_B=(V,B) šume grafa G i da je |A| < |B| , tj. A i B su aciklični skupovi ivica, i da u skupu B ima više ivica nego u skupu A. Iz jedne od teorema koje su ranije razmatrane sledi da šuma u kojoj imamo k ivica ima tačno {V} -k drveta . Da to dokažemo pođimo od |V| drveta od kojih svako ima samo jedan vrh i ne sadrži ni jednu ivicu. Tada svako rebro (ivica) koje se dodaje šumi, za jedan smanjuje broj drveta. Na taj način šuma G_A ima |V| - |A| drveta , a šuma G_B ima |V| - |B| drveta.

Ukoliko šuma G_B ima manje drveta od šume G_A tada u šumi G_A postoji drvo T čiji vrh (pripada) predstavlja kraj dva različita drveta šume G_A. Više od toga, ako je drvo T na taj način povezano, ono mora da sadrži ivicu (u,v) tako da vrhovi u i v pripadaju različitim drvima šume G_A. Ukoliko ivica (u,v) spaja vrhove dvaju različitih drveta šume G_A tada je možemo dodati u šumu G_A ne obrazujući krug na taj način. Na taj način strutura M_G zadovoljava osobinu zamene, čime se završava dokaz da je M_G – matroid.

Za zadati matroid M=(S,I) definišimo elemenat x∈A kao proširenje (EXTENSION)), skupa A∈I, ako je njega moguće dodati u A bez narušavanja nezavisnosti tj. x – je proširenje skupa A ako je A∪{x}∈I. Kao primer razmotrimo matroid grafa M_G. Ako je A – nezavisni skup ivica, tada je ivica e proširenje skupa A tada I samo tada ako ne pripada tom skupu i ako njeno dodavanje skupu ne dovodi do stavranja ciklusa.

Ako je A – nezavistan podskup u matroidu M, i ako u njemu nema proširenja (nisu moguća) tada kažemo da je A maksimalan skup. Na taj način, skup A je maksimalan ako se ne sadrži ni u jednom većem podskupu matroida M. Dole data osobina je često vrlo korisna.

[уреди] Teorema 2.

Svi maksimalni nezavisni podskupovi matroida imaju istu veličinu.

[уреди] Dokaz:

Teoremu dokazujemo metodom suprotnosti. Pretpostavimo da je A – maksimalan nezavistan podskup matroida M i da postoji drugi maksimalni nezavisni podskup B matroida M čija je veličina veća od veličine podskupa A. Tada iz osobine zamene sledi da skup A proširujemo do većeg nezavisnog skupa A∪{x} na račun nekog elementa x∈B-A što protivureči pretpostavci o maksimalnosti skupa A.

Kao ilustraciju primene ove teoreme razmotrimo primenu matroida grafa M_G vezanog sa neorijentisanim grafom G. Svaki maksimalni nezavisni podskup matroida M_G mora da bude (da predstavlja) slobodno drvo koje ima tačno |V| - 1 ivica koje spajaju vrhove grafa G. Takvo drvo se zove osnovno drvo (SPANNING TREE) grafa G.

Kažemo da je matroid M=(S,I) težinski (WEIGHTED), ako je sa njim povezana težinska funkcija w koja svakom elementu x∈S određuje strogo pozitivnu težinu w(x). Težinska funkcija w se uopštava na podskupove skupa S putem sumiranja:

w(A)= ∑ w(x), x∈A, za proizvoljni podskup A⊆S,

npr. ako sa w(e) označimo dužinu ivice e matroida grafa M_G , tada je w(A) – ukupan dužina svih ivica koje pripadaju skupu A.

[уреди] Види још

• Теорија графова
• Похлепни алгоритам