Univerza v Ljubljani
Fakulteta za raˇ cunalniˇ stvo in informatiko Fakulteta za matematiko in fiziko
Marko Drvariˇc
Osnovno o matroidih
DIPLOMSKO DELO
INTERDISCIPLINARNI UNIVERZITETNI ˇSTUDIJSKI PROGRAM PRVE STOPNJE
RA ˇCUNALNIˇSTVO IN MATEMATIKA
Mentor : prof. dr. Riste ˇ Skrekovski
Ljubljana, 2021
koriˇsˇcenje rezultatov diplomske naloge je potrebno pisno privoljenje avtorja, Fakultete za raˇcunalniˇstvo in informatiko ter mentorja.
Besedilo je oblikovano z urejevalnikom besedil LATEX.
Fakulteta za raˇcunalniˇstvo in informatiko izdaja naslednjo nalogo:
Tematika naloge: Osnovno o matroidih
Kazalo
Povzetek Abstract
1 Kratka zgodovina matroidov 1
2 Opis in definicije matroidov 3
2.1 Neodvisne mnoˇzice . . . 3
2.2 Baze . . . 4
2.3 Funkcija ranga . . . 5
2.4 Izomorfizem matroidov . . . 7
2.5 Podmatroidi, zoˇzitve, skrˇcitve in minorji . . . 7
3 Dualnost 11 4 Pomembni razredi matroidov 15 4.1 Matroidi iz grafov . . . 15
4.2 Matroidi iz linearne algebre . . . 22
5 Poˇzreˇsna metoda 29
6 Problem pakiranja in pokritja 33
Literatura 37
Povzetek
Naslov: Osnovno o matroidih Avtor: Marko Drvariˇc
Matroidi so struktura v kombinatoriki, ki jo je prvi predstavil Hassler Whit- ney leta 1935, pri kateri se pojme kot so neodvisna mnoˇzica, cikel, baza, rang, minor, dual in druge naravno posploˇsi in uporablja. Matroide lahko definiramo na veˇc naˇcinov, pri tem pa izhajamo predvsem iz terminologije uporabljene v teoriji grafov in linearne algebre. Glede na to, kako matroide definiramo, jih lahko uporabimo pri razliˇcnih kombinatoriˇcno-optimizacijskih problemih, kot sta problem pakiranja in pokritja ter poˇzreˇsna metoda.
Kljuˇcne besede: graf, vektor, linearna algebra, neodvisnost.
Abstract
Title: Matroid basics Author: Marko Drvariˇc
Matroids are a combinatorical structure, first introduced by Hassler Whitney in 1935, that generalizes and uses notions such as independent set, cycle, base, rank function, minor, duality and others. Matroids can be defined in different ways, mostly using terminology used in graph theory and linear algebra. Based on the definition used, we can use matroids in a variety of problems from the fields of combinatorics and optimization, such as the packing and covering problems, as well as the greedy method.
Keywords: graph, vector, linear algebra, independency.
Poglavje 1
Kratka zgodovina matroidov
Teorija matroidov se zaˇcne s ˇclankom [16] Hasslera Whitneya leta 1935.
Whitney je matroid definiral kot druˇzino neodvisnih podmnoˇzic osnovne mnoˇzice S, ki zadovoljuje osnovna pogoja, predstavljena kasneje. Glede na izbiro mnoˇzice S je Whitney takoj opisal dva razreda matroidov, in sicer lin- earne in grafovske. Poleg osnovne definicije je v svojem delu podal ˇse nekaj ekvivalentnih razliˇcic teh aksiomov, izpostavil omenjena razreda in dokazal nekaj osnovnih rezultatov. Med najbolj pomembnimi rezultati je, da je pos- ploˇsil dualnost ravninskih grafov.
V naslednjih dvajsetih letih ni bilo veliko objavljenih del na podroˇcju matroidov. Izjema, ki v svojem ˇcasu ni bila preveˇc cenjena, je bil ˇclanek [12]
s strani Richarda Rada leta 1942. Rado je podal matroidsko posploˇsitev Hallovega izreka o prirejanju v grafih. V istem ˇclanku je Rado opisal prav tako izrek o neodvisni transverzali, kar je verjetno prvi pomemben rezultat v teoriji matroidov.
V pedesetih letih prejˇsnjega stoletja je Bill Tutte objavil nekaj rezultatov iz teorije matroidov in hkrati reˇsil nekaj problemov, ki jih je zastavil Whit- ney. Ti rezultati so bili predvsem povezani s karakterizacijo razliˇcnih razre- dov matroidov. ˇCeprav so bili ti rezultati poglobljeni in njihova povezava z optimizacijo takrat ni bila oˇcitna, so postali osnova pomembnih dejstev za potrebe optimizacije.
1
Dokonˇcno so matroidi postali pomemben del optimizacije v ˇsestdesetih letih prejˇsnjega stoletja. Osrednja oseba v tem ˇcasu je bil Jack Edmonds. Ne le, da je odkril uporabne izreke in algoritme, ampak je tudi predstavil izraze in terminologijo, ki se uporablja ˇse danes. Pomemben izrek, ki ga je opisal, je predvsem Izrek o razbitju matroidov (Matroid Partition Theorem), ki je zelo uporaben predvsem pri problemu pakiranja in pokritja. Jack Edmonds je bil tudi organizator prve konference o matroidih leta 1964. Edmonds je kasneje izjavil, da takrat ni mogel najti veˇc kot ˇsest ljudi, ki bi ˇze sliˇsali za izraz ”matroid”, a je kljub temu Tutte to konferenco oznaˇcil za dogodek, ki je teorijo matroidov oznanil svetu. Nekaj ˇcasa so se pojavljali predlogi, da bi izraz matroid spremenili v izraz ”kombinatoriˇcna geometrija”, vendar so ob nasprotovanju Tutta in Edmondsa matroidi ostali matroidi [2].
V teoriji matroidov je veˇc izrekov, ki so v bistvu ekvivalentni izreku o razbitju matroidov, vendar so tudi sami pomembni. Tak ekvivalenten izrek je na primer samostojno naˇsel tudi Tutte, vendar pa je brez dvoma najbolj pomemben ˇse en izrek Edmondsa, Izrek o preseku matroidov (Matroid In- tersection Theorem). Ta izrek posploˇsi slaven K¨onigov min-max izrek za maksimalno velikost prirejanja v dvodelnem grafu.
S tem je bila postavljena osnova za nadaljno uporabo matroidov v raznih optimizacijsko-kombinatoriˇcnih problemih, kot so ˇze omenjeni problem paki- ranja in pokritja, problem preseka dveh ali treh matroidov in zagotovo najbolj znan problem, povezan z matroidi, Poˇzreˇsna metoda.
Kljub skromnim zaˇcetkom, so matroidi nekaj deset let po prvem opisu, kot posledica izjemnih rezultatov na tem podroˇcju in nekaj zagnane promocije s strani doloˇcenih znanstvenikov, postali kljuˇcen del diskretne optimizacije.
A kljub velikim napredkom, na podroˇcju teorije matroidov ostaja ˇse veliko odprtih vpraˇsanj, ki ˇse danes izzivajo matematike.
Poglavje 2
Opis in definicije matroidov
Matroidi so zelo raznolik koncept, saj jih lahko najdemo v raznih vejah matematike. Najbolj preprosta primera sta mnoˇzica vektorjev s pripadajoˇco druˇzino linearno neodvisnih podmnoˇzic in konˇcni graf s pripadajoˇco druˇzino vseh acikliˇcnih podgrafov. Temu primerno obstaja tudi mnogo razliˇcnih, ekvivalentnih naˇcinov kako lahko matroide definiramo.
2.1 Neodvisne mnoˇ zice
Matroid M je urejeni par (E,I), ki ga sestavljata konˇcna mnoˇzica E in druˇzina I podmnoˇzic E, za katere veljajo naslednje lastnosti:
1. prazna mnoˇzica je element I;
2. ˇce jeI ∈ I in I’⊆ I, potem I0 ∈I;
3. ˇce sta I1 in I2 elementa v I in velja |I1|<|I2|, potem obstaja element e izI2\I1, da je I1∪ {e} ∈ I.
Mnoˇzicam iz I pravimo neodvisne mnoˇzice matroida M. Med lastnostmi neodvisnih mnoˇzic je verjetno najbolj uporabna lastnost, opisana v nasled- njem izreku [10].
Izrek 2.1. Ce staˇ X in Y izI in velja|X|<|Y|, potem obstaja Z ⊆Y \X, da velja |X∪Z|=|Y| in X∪Z ∈ I.
3
Dokaz. Naj bo Z0 taka mnoˇzica med vsemi mnoˇzicami Z ⊆ Y \X, da je X ∪Z neodvisna, |X ∪Z0| pa maksimalna. ˇCe |X ∪Z0| < |Y|, potem
∃Y0 ⊆Y,|Y0|=|X ∪Z0|+ 1 in ker po tretji lastnosti za neodvisne mnoˇzice velja, da je Y0 neodvisna ∃y ∈ Y0 \(X ∪Z0) ˇce velja, da je X ∪Z0 ∪ {y}
neodvisna. Mnoˇzica Z0∪ {y} je protislovje za izbiroZ0 [15].
Izreku (2.1) pravimo dopolnitveni izrek. Pomembna je ˇse oˇcitna posledica dopolnitvenega izreka, ki je hkrati tudi lastnost baz matroidov.
Izrek 2.2 ([7]). Vse baze matroida M imajo enako moˇc in ta moˇc je enaka rangu matroida M.
Iz dopolnitvenega izreka izhaja ˇse ena pomembna posledica, predstavl- jena v naslednjem razdelku, saj se neposredno nanaˇsa na drugo definicijo matroidov.
2.2 Baze
Baza matroida je definirana kot mnoˇzica B ⊆ M, ˇce je B neodvisna in ni prava podmnoˇzica nobene neodvisne mnoˇzice matroida M. Druˇzino vseh baz matroida M oznaˇcimo z B. Matroid M sestavljata ne-prazna konˇcna mnoˇzica E in ne-prazna druˇzina B baz E, za katere velja:
1. nobena baza ni prava podmnoˇzica druge baze;
2. ˇce staB1 inB2 bazi in je enek element izB1\B2, potem obstaja tudi element f iz B2\B1, da velja, da je (B1\e)∪ {f} tudi baza.
Ravno druga lastnost je posledica dopolnitvenega izreka, imenujemo pa jo izmenjalni aksiom za baze matroida [7].
Dokaz izmenjalnega aksioma. Aksiom dokaˇzemo preprosto tako, da dopol- nitveni izrek uporabimo na mnoˇzicah B1 in B2 in dobimo ravno to last- nost.
Diplomska naloga 5
2.3 Funkcija ranga
Naslednja karakterizacija matroidov poteka preko funkcije ranga matroida.
Za matroidM = (S,I) za vsako podmnoˇzicoA⊆Sdefiniramorang mnoˇzice A kot ˇstevilo
ρ(A) = max{|X|;X ⊆A, X ∈ I}. (2.1) Predpis (2.1) doloˇca funkcijo ρ : P(S) → N, ki se imenuje funkcija ranga matroida M. Vrednost ρ(S) je rang matroida M.
Izrek 2.3 ([7]). Naj bo ρ funkcija ranga matroida M. Tedaj za vsak X ⊆ S in za poljubna elementa y, z ∈S velja:
1. ρ(∅) = 0;
2. ρ(X)≤ρ(X∪ {y})≤ρ(X) + 1;
3. ˇce jeρ(X∪ {y}) =ρ(X∪ {z}) =ρ(X), tedaj je ρ(X∪ {y, z}) =ρ(X).
Za funkcijo ρ:P(S)→N, ki ima vse te lastnosti velja, da je funkcija ranga nekega matroida nad S. Neodvisne mnoˇzice takega matroida so natanko tiste mnoˇzice X ⊆S, za katere je ρ(X) = |X|.
Dokaz. Prvi dve lastnosti sledita neposredno iz predpisa (2.1) funkcije ranga ρ ter prvih dveh lastnosti neodvisnih mnoˇzic v definiciji matroida.
Dokazati moramo torej le ˇse tretjo lastnost.
Oznaˇcimo Y = X ∪ {y, z} in recimo, da velja ρ(Y) > ρ(X). Z X0 oznaˇcimo neodvisno mnoˇzico, ki naj bo vsebovana v X. ˇCe tako oznaˇcimo, velja ρ(X) = |X0|. Dopolnitveni izrek nam pravi, da lahko X0 dopolnimo do maksimalne neodvisne mnoˇzice X00, ki bo vsebovana v Y. Ker pa velja
|X00| = ρ(X) > ρ(Y) = |X0|, mora X00 vsebovati bodisi y bodisi z. Torej mora veljati, da je vsaj ena od mnoˇzic X0 ∪ {y} in X0 ∪ {z} neodvisna.
Slednje pa bi seveda pomenilo, da drˇzi bodisi ρ(X ∪ {y}) > ρ(X) bodisi ρ(X∪ {z})> ρ(X). Dobili smo protislovje.
Pokaˇzimo, da drˇzi izrek tudi v drugo smer. Denimo, da za funkcijo ρ veljajo vse tri lastnosti. Naj boI ={X ⊆S|ρ(X) = |X|}.Iz prve lastnosti funkcije sledi prva lastnost neodvisnih mnoˇzic matroida. Preverimo, ali velja druga lastnost. Recimo, da je I ∈ I in da obstaja J ⊂ I, J /∈ I. Sledi, da ρ(J)< |J|. Nasprotna moˇznost je izkljuˇcena zaradi prvih dveh lastnosti funkcije ranga. ˇCe sedaj mnoˇziciJ po vrsti dodajamo elemente izI\J, preko druge lastnosti funkcije ranga ugotovimo, da velja ρ(I) < |I|. Dobili smo protislovje, saj veljaI ∈ I. Torej tudi druga lastnost velja. Preveriti moramo ˇse, ali velja tudi tretja lastnost. Vzemimo poljubna I, J ∈ I,|J| = |I|+ 1.
Torej velja ρ(J) =ρ(I) + 1. ˇCe parI, J ne zadoˇsˇca tretji lastnosti, velja po drugi lastnosti funkcije ranga za vsak y∈J\I:
ρ(I) = ρ(I ∪ {y})<|I|+ 1. (2.2) Denimo, da je J\I ={y1, . . . , yr}.Takrat mora biti R ≥2, saj bi v nasprot- nem primeru veljalo J =I∪ {y1} ∈ I. Po (2.2) je ρ(I∪ {y1}) =ρ(I) =|I|, iz tretje lastnosti funkcije ranga pa sledi ρ(I ∪ {y1} ∪ {y2}) = ρ(I). Ceˇ nadaljujemo z dodajanjem unij k mnoˇzici I, ugotovimo, da velja ρ(J) ≤ ρ(I ∪ {y1} ∪ · · · ∪ {yr}) = ρ(I) = |I| < |J|. To pa je protislovje za izbiro mnoˇzice J. S tem smo dokazali tudi tretjo lastnost.
Kot zadnje moramo ˇse preveriti, ali je funkcija ranga tako dobljenega matroida zares enaka ρ. Za dano podmnoˇzico X ⊆ S vzemimo mnoˇzico I ∈ I, I ⊆X, ki ima maksimalno moˇc. Tedaj veljaρ(I) =|I| ≤ρ(I∪ {x})≤
|I|+ 1.Z indukcijo po|X|od tu slediρ(X) =ρ(I) = |I|. S tem smo dokazali
celoten izrek [7].
Alternativno bi lahko za definicijo matroida preko funkcije ranga uporabili tudi naslednje lastnosti, ki morajo veljati za poljubni mnoˇzici X, Y ⊆S:
1. 0 ≤ρ(X)≤ |X|;
2. ˇce jeX ⊆Y, je ρ(X)≤ρ(Y);
3. ρ(X∪Y) +ρ(X∩Y)≤ρ(X) +ρ(Y).
Diplomska naloga 7 Drugi lastnosti iz te definicije pravimomonotonost, tretji pasubmodularnost funkcijeρ, definiciji monotonosti in submodularnosti pa se pojavita pri defini- cijah raznih problemov, predvsem problema pakiranja in pokritja [7].
2.4 Izomorfizem matroidov
Tako kot so definirani izomorfizmi za mnoge matematiˇcne strukture, je defini- ran tudi izomorfizem matroidov. Izomorfnost matroidov rabimo tudi za nadaljne definicije v teoriji matroidov, kot je na primer definicija grafovskih matroidov.
Izomorfizem matroidov M = (S,I) in M0 = (S0, I0) je bijektivna pres- likava φ : S → S0, ki v obe smeri ohranja neodvisnost: ˇce I ∈ I, tedaj φ(I) ∈ I0, in ˇce je I0 element I0, potem φ−1(I0) ∈ I. Temu ekvivalenten je pogoj, da φ ohranja baze oziroma funkcijo ranga:
ρ0(φ(X)) = ρ(X), X ⊆S,
kjer smo z ρ0 oznaˇcili funkcijo ranga v matroidu M0. Ce staˇ M in M0 izomorfna, to zapiˇsemo kot M ∼=M0 [7].
2.5 Podmatroidi, zoˇ zitve, skrˇ citve in minorji
V teoriji matroidov obstajajo tri osnovne operacije, ki posploˇsujejo operacije za grafe. Poleg operacije pridobivanja dualov, ki je opisana v nadaljevanju, sta osnovni operaciji ˇse zoˇzitev in skrˇcitev [9].
Naj bo M = (S,I) matroid nad S in A ⊆ S. Tedaj z IA oznaˇcimo druˇzino
IA={X ∈ I |X∩A=∅} ⊆ P(S\A).
DruˇzinaIAima vse tri lastnosti, potrebne za definicijo matroida preko neod- visnih mnoˇzic, zato velja, da je M \A := (S \A,IA) matroid nad mnoˇzico S\A. MatroiduM\Apravimozoˇzitev matroidaM naS\A, pravimo pa mu
tudi podmatroid matroida M. Zoˇzitev matroida ustreza operaciji odstranje- vanja povezav grafa.
Podobno kot zoˇzitve matroida ustrezajo odstranjevanju povezav grafa, lahko posploˇsimo tudi operacijo krˇcenja povezav grafa. V teoriji grafov je skrˇcitev povezave e = uv operacija, pri kateri najprej iz G odstranimo povezavo e, potem pa identificiramo obe krajiˇsˇci. Dobljeni graf oznaˇcimo z G/e. ˇCe velja, da e 6= f, potem velja (G/e)/f = (G/f)/e. Kot posledico lahko za poljubno mnoˇzico povezav A ⊆ E(G) definiramo graf G/A, ki ga dobimo tako, da vse povezave iz A skrˇcimo. Graf G/A potem imenujemo skrˇcitev grafaG. Skrˇcitev grafa lahko naravno prenesemo tudi na matroide, o tem pa nam govori naslednji izrek [7].
Izrek 2.4. Za mnoˇzico povezav T ⊆ E(G/A) velja, da je vpet gozd v G/A natanko tedaj, ko v grafu G−(E(G)\A) obstaja tak vpet gozd TA, da je T ∪TA vpet gozd v G.
Dokaz. [7] Za dokaz izreka uporabimo indukcijo po |A|. Pri |A| = 0 nimamo ˇcesa dokazovati, sicer pa upoˇstevamo, da za vsak a∈A velja
G/A= (G/a)/(A\a) = (G/(A\a))/a, (2.3)
in uporabimo indukcijsko predpostavko.
Za funkcijo rangaρM v matroiduM, kjerA⊆S inT =S\A, definiramo funkcijo ρM/A(X) :P(T)→N kot
ρM/A(X) =ρM(X∪A)−ρM(A). (2.4) Sledi, da je za matroid M = (S,I) in A ⊆ S funkcija ρM/A funkcija ranga nekega matroida nad mnoˇzico T = S \ A. Dokaz vseh lastnosti funkcije ranga za ρM/A hitro sledi iz (2.3) in enakih lastnosti funkcije ρM. Matroid, ki mu pripada funkcija rangaρM/A, oznaˇcimo zM/A. Imenujemo ga skrˇcitev matroida M glede na mnoˇzico A.
Za definicije posebnih razredov in struktur znotraj teorije matroidov so pomembni tudi minorji matroidov. Minor matriodaM definiramo kot vsak
Diplomska naloga 9 matroid M0, ki ga lahko dobimo iz M z zaporedjem zoˇzitev in skrˇcitev. Do uporabne povezave matroidov z lastnimi minorji pridemo tudi preko nasled- njega zanimivega izreka.
Izrek 2.5 ([7]). Naj bo M matroid nad S in naj bosta T, U ⊆ S, tako da T ∩U =∅. Tedaj velja
a) (M \U)\T = (M \T)\U =M \(T ∪U);
b) (M/U)/T = (M/T)/U =M/(T ∪U);
c) M\U/T =M/T \U.
Dokaz. Toˇcka (a) je oˇcitna, toˇcka (b) pa sledi iz (a) na podlagi dualnosti operacij. Dokazati moramo torej le ˇse toˇcko (c). Vzemimo najprej mnoˇzico X ⊆S\(T ∪U) in izraˇcunajmo njen rang:
ρM\U/T(X) =ρM\U(X∪T)−ρM\U(T)
=ρM(X∪T)−ρM(T)
=ρM/T(X)
=ρM/T\U(X).
Matroida M/T \U in M \U/T imata torej enaki funkciji ranga. Sledi, da
sta enaka.
Kot posledica izreka 2.5 sledi:
Izrek 2.6. Ce jeˇ M0 minor matroida M nad S, tedaj obstajata disjunktni mnoˇzici T, U ⊆S, za kateri velja M0 =M/T \U =M \U/T.
Za nekatere pomembne razrede matroidov velja, da so zaprti za minorje, kar pomeni, da je vsak minor matroida, ki pripada razredu, tudi v razredu.
Take razrede lahko opiˇsemo s prepovedanimi minorji, torej z minorji, ki ne morejo nastopati kot minorji v nobenem matroidu tega razreda, so pa min- imalni matroidi s to lastnostjo. Nek matroid je torej prepovedan minor za razred matroidovM, ˇce ni vM, vsak njegov pravi minor pa pripada razredu M [15].
Poglavje 3 Dualnost
Ena izmed bolj atraktivnih lastnosti matroidov je obstoj teorije dualnosti.
Ta teorija, ki jo je prviˇc predstavil Whitney leta 1935, razˇsiri pojem pra- vokotnosti v vektorskih prostorih in koncept ravninskega duala ravninskega grafa. V reˇsevanju matroidskih problemov s tem pridobimo zelo uporabno orodje [10].
Na podlagi izreka, ki ga je v svoji knjigi opisal Whitney leta 1935 [16], lahko s pomoˇcjo danega matroida na enostaven naˇcin sestavimo nov matroid.
Izrek 3.1 ([10]). Naj bo M = (S,I) matroid in B druˇzina baz v M. Ses- tavimo druˇzino B∗ ⊆ P(S):
B∗ ={S\B |B ∈ B}={B∗ |S\B∗ ∈ B}. (3.1) Tedaj jeB∗ neprazna druˇzina mnoˇzic, ki ima lastnost izmenjalnega aksioma.
Zato je B∗ druˇzina baz nekega matroida M∗ nad S.
Dokaz. Izmenjalni aksiom za B∗ lahko zapiˇsemo v ekvivalentni obliki kot:
B, B0 ∈ B in x∈B\B0 =⇒ ∃y∈B0\B : (B0 \y)∪x∈ B. (3.2) Sedaj poglejmo mnoˇzico B0∪ {x}. Ta mnoˇzica ima rang |B0|. Ker je x∈B, sledi, da je (B∩B0)∪ {x} v I. To mnoˇzico lahko po dopolnitvenem izreku
11
dopolnimo do neodvisne mnoˇzice A ⊆ B0 ∪ {x} moˇci |B0| z elementi iz B0. To pomeni da jeA baza, zato velja A= (B0\y)∪ {x} za nekiy ∈B0\B. S
tem smo izrek dokazali.
Matroidu M∗ iz tega izreka pravimodualni matroid matroida M. ˇCe je matroid definiran kot M = (S, I), potem z I∗ oznaˇcimo neodvisne mnoˇzice, z ρ∗ pa funkcijo ranga dualnega matroida M∗. Potem veljata naslednji last- nosti:
(M∗)∗ =M;
I ∈ I∗ natanko tedaj, ko S \I vsebuje bazo matroida M, kar drˇzi natanko tedaj, ko je ρ(S\I) =ρ(M);
Za matroidMin njegov dualM∗velja preprosta zveza glede rangov: ρ∗(M∗) =
|S| −ρ(M). Razˇsiritev te zveze nam da sploˇsno zvezo za poljubne mnoˇzice v S.
Izrek 3.2 ([10]). Naj bosta ρ in ρ∗ funkciji ranga v matroidih M in M∗. Potem za vsak A⊆S velja:
ρ∗(S\A) = |S| −ρ(S)−(|A| −ρ(A)) (3.3) oziroma
ρ∗(A) =|A|+ρ(S\A)−ρ(S). (3.4) Dokaz. Ce enaˇˇ cbo (3.4) vzamemo za definicijo funkcije ρ∗, se lahko prepriˇcamo, da za ρ∗ veljajo vse tri lastnosti za alternativno definicijo ma- troida preko funkcije ranga, ki smo jo ˇze opisali. Oˇcitno je, da velja
0≤ρ(X)≤ |X|
ter
ˇ
ce je X ⊆Y, je ρ(X)≤ρ(Y),
Diplomska naloga 13 lastnost submodularnosti funkcije ρ pa sledi iz lastnosti submodularnosti za ρ:
ρ(S\A) +ρ(S\B)≥ρ(S\(A∪B)) +ρ(S\(A∩B)). (3.5) Iz tega sledi, da jeρ∗ funkcija ranga nekega matroida M0 nad mnoˇzico S. V matroiduM0 so neodvisne mnoˇzice doloˇcene s pogojem ρ∗(A) =|A|. Iz (3.5) sledi, da to drˇzi natanko tedaj, ko jeρ(S\A)−ρ(S) = 0.To pa drˇzi natanko tedaj, koS\A vsebuje bazo. Iz tega sledi, da je M0 =M∗.
Pri objektih, ki so prirejeni dualnemu matroidu, a se nanaˇsajo na osnovni matroid, dodamo predpono ”ko”. Tako dobimo naslednje pojme:
korang je rang v dualnem matroidu,
kobaza je baza v dualnem matroidu,
kocikel je cikel v dualnem matroidu,
kozanka je zanka v dualnem matroidu itd [10].
Poglavje 4
Pomembni razredi matroidov
4.1 Matroidi iz grafov
Eden od dveh osnovnih razredov matroidov, ki se pojavijo v Whitneyjevem delu iz leta 1935 [16] so matroidi, ki so izpeljani iz grafov. Matroidi, izpeljani iz grafov, nam dajo nekaj zelo uporabnih in zanimivih rezultatov ter struktur, ki se nanaˇsajo tudi na optimizacijsko-kombinatoriˇcne probleme [6].
4.1.1 Grafovski matroidi
Naj boGgraf inS =E(G) mnoˇzica povezav grafaG. DruˇzinaI ⊆ P(S) naj vsebuje natanko tiste mnoˇzice povezav, ki ne vsebujejo nobenega cikla. Taka druˇzina I oˇcitno zadoˇsˇca prvemu in drugemu pogoju pri definiciji matroidov z neodvisnimi mnoˇzicami, preverimo pa lahko tudi, da velja tretji pogoj.
Dobljeni matroid, ki ga oznaˇcimo z M(G) = (S,I) imenujemo matroid ciklov grafa G. Vsak matroid, ki je izomorfen matroidu ciklov nekega grafa, je grafovski matroid. ˇCe je graf G povezan, baze v matroidu ciklov grafa G ustrezajo vpetim drevesom. ˇCe graf ni povezan, baze ustrezajo vpetim gozdovom [7].
Kot primer si oglejmo graf G na Sliki 4.1.
15
Slika 4.1: Graf G
Za baze matroida bomo vzeli vpeta drevesa grafaG. ˇCe pogledamo Sliko 4.1, lahko vidimo, da so baze grafa v Tabeli 4.1.
Baze {a, b, c, d}
{a, e, d, c}
{b, c, d, e}
{b, a, e, d}
{c, b, a, e}
{c, b, f, e}
{c, d, f, a}
{c, g, a, e}
{c, g, f, d}
Tabela 4.1: Vpeta drevesa v grafu G
Z opazovanjem te mnoˇzice baz lahko vidimo, da je prva lastnost za baze matroida izpolnjena, saj nobena baza ni prava podmnoˇzica druge baze.
Drugo lastnost lahko pokaˇzemo tako, da jo uporabimo na dveh bazah. ˇCe
Diplomska naloga 17 izberemo B1 = {a, b, c, d} in B2 = {c, g, a, e}, potem lahko vidimo vpeti drevesiB1 inB2 na slikah 4.2 in 4.3 [3].
Slika 4.2: Vpeto drevo, B1
Slika 4.3: Vpeto drevo, B2
Opazimo, da imata obe vpeti drevesi pet vozliˇsˇc in ˇstiri povezave. Drugo lastnost baz lahko demonstriramo tako, da odstranimo {a} iz B1 in potem obstaja tak element v B2, da nastane nova baza, B3 = (B1 \ {a})∪ {e}).
Slika 4.4 nam predstavlja dobljeno bazo,B3 [3].
Slika 4.4: Vpeto drevo, B3 Podoben razmislek velja za katerokoli izbiro baz.
Gamoidi. Leta 1968 je Hazel Perfect v svojem delu [11] kot prvi koncep- tualno predstavil nov zanimiv razred matroidov, gamoide. Gamoidi so se izkazali za precej teˇzko obvladljiv razred matroidov, saj je veliko osnovnih vpraˇsanj odprtih ˇse danes, tudi veˇc deset let kasneje. Gamoide je poimenoval Pym leta 1969, bolj podrobno pa jih je raziskal Mason leta 1972.
Gamoidi so oˇciten primer uporabe grafov kot vir matroidov, saj se grafi skrivajo v sami definiciji.
Naj boG= (V, E) usmerjen graf. Izberemo podmnoˇzicoB mnoˇzice V in naj L(G, B) predstavlja mnoˇzico vseh podmnoˇzic V, ki jih lahko poveˇzemo v B. Torej X ∈L(G, B), ˇce obstaja Y ⊆B, da obstaja povezava iz X v Y. Izrek 4.1 ([15]). L(G, B) je mnoˇzica neodvisnih mnoˇzic matroida na V.
Dokaz tega izreka sledi v poglavju o transverzalnih matroidih.
Vsak matroid, ki ga lahko dobimo iz usmerjenega grafa G in neke podmnoˇzice B mnoˇzice V(G) na tak naˇcin, imenujemo strogi gamoid.
Gamoid je matroid, ki ga dobimo, ˇce omejimo strogi gamoid L(G, B) na neko podmnoˇzico V(G). Oznako L(G, B) uporabljamo, da oznaˇcimo tako strogi gamoid kot tudi njegovo mnoˇzico neodvisnih mnoˇzic.
Diplomska naloga 19 Gamoidi imajo tudi zelo lepe lastnosti v povezavi z duali in minorji. Vel- jata naslednja izreka [15].
Izrek 4.2. Vsak minor gamoida je gamoid.
Izrek 4.3. Dual gamoida je gamoid.
Dokaza sta predstavljena v poglavju o transverzalnih matroidih, saj v dokazih nastopajo tako transverzalni matroidi kot pojmi, povezani z njimi.
Kot bomo videli tudi v dokazih, so najbliˇzji razred gamoidom transverzalni matroidi, s katerimi se gamoidi lepo povezujejo.
4.1.2 Transverzalni matroidi
Pri definiranju trasverzalnih matroidov se moˇcno nanaˇsamo na terminologijo iz teorije grafov.
Za graf G pravimo mnoˇzici povezav, v kateri noben par povezav nima skupnega krajiˇsˇca prirejanja v grafu G. Pravimo, da prirejanje F pokriva mnoˇzico toˇck U ⊆ V(G), ˇce je vsaka toˇcka izU krajiˇsˇce kakˇsne povezave iz F. ˇCe neko prirejanje pokriva vse toˇcke grafa, mu pravimo popolno prire- janje. Preko prirejanj definiramo tudi transverzale. Za dvodelen graf G z dvodelnim razbitjem V(G) = S ∪T pravimo, da je mnoˇzica toˇck A ∈ T delna transverzala v T, ˇce v grafu G obstaja prirejanje, ki pokrije vse toˇcke izA. Enako definiramo tudi delne transverzale v S [7].
Definiramo tudi neodvisne delne transverzale glede na matroid M. Te je definiral Rado v izreku:
Izrek 4.4 ([12]). naj bo M matroid nad mnoˇzico S in G dvodelen graf z dvodelnim razbitjem S∪T. Mnoˇzica A ∈ T je neodvisna delna transverzala glede na matroid M natanko tedaj, ko za vsako podmnoˇzico X∈A velja:
ρ(NG(X))≥ |X|. (4.1)
Prav tako je Rado podal naslednji izrek, ki definira transverzalne ma- troide.
Izrek 4.5 ([12]). Naj bo A = (Ai;i ∈ I) konˇcna druˇzina konˇcnih mnoˇzic, S = ∪i∈IAi in I druˇzina vseh delnih transverzal druˇzine A. Tedaj je M = (S,I) matroid.
Ta izrek se v jeziku dvodelnih grafov glasi takole.
Izrek 4.6. Naj bo Gdvodelen graf z dvodelnim razbitjem V(G) = S∪T. ˇCe je I ⊆ P(S)druˇzina vseh tistih podmnoˇzic mnoˇziceS, ki jih lahko pokrijemo s kakˇsnim prirejanjem v G, tedaj je M = (S,I) matroid.
Dokaz. Vzemimo dvodelni graf G, ki ustreza druˇzini A. Za toˇcke grafa veljaV(G) =S∪I, pri ˇcemer stas∈Sini∈I sosednji, ˇces ∈Ai. Naj bo ˜M matroid sosednosti grafaGglede na prosti matroid nadS∪I. Za matroid ˜M, naj bo M0 = (S,I0) zoˇzitev tega matroida na S, torej M0 = ˜M \I. Trdimo, da jeI0 =I. Za mnoˇzico A⊆S velja, da je neodvisna v M0 natanko tedaj, ko je neodvisna v ˜M. Glede na funkcijo ranga v matroidu sosednosti grafa pa je to natanko tedaj, ko je
|A|=ρ0G(A) = min
Y⊆A(ρG(Y) +|A\Y|) = min
Y⊆A(|NG(Y)|+|A\Y|). (4.2) Ker pa velja |NG(∅)|+|A| = |A|, velja ta enakost natanko tedaj, ko velja
|NG(Y)| ≥ |Y| za vsak Y ⊆ A. Po Hallovem izreku je ta pogoj izpolnjen natanko tedaj, ko je A delna transverzala. Torej res velja I0 =I.
Matroidu delnih transverzal iz Radojevega izreka (4.5) pravimo transverzalni matroid druˇzine A. ˇCe namesto druˇzine A zaˇcnemo z dvodel- nim grafom G nad V(G) = S ∪ I, pravimo, da je M transverzalni ma- troid dvodelnega grafa G. V sploˇsnem dvodelnemu grafu pripadata dva transverzalna matroida, saj lahko vlogi mnoˇzic S in I zamenjamo. Razred transverzalnih matroidov se od drugih razredov, ki smo jih definirali, raz- likuje v tem, da ni zaprt za minorje.
Z definicijami transverzalov in transverzalnih matroidov lahko sedaj dokaˇzemo tudi izreka (4.2) in (4.3).
Dokaz izreka 4.2. Ce jeˇ M matroid na S, obstaja usmerjen graf G, podmnoˇzica B mnoˇzice V(G) in podmnoˇzica S mnoˇzice V(G), da velja
Diplomska naloga 21 M =L(G, B)|S.Zato za T ⊆S,
M|T =L(G, B)|T kar nam pove, da je zoˇzitev gamoida gamoid.
Skrˇcitveni minor M . T lahko predstavimo v obliki M . T = (N|S). T,
kjer jeN strogi gamoid na neki mnoˇziciS0, ki vsebujeS. Sedaj, ker operaciji odstranjanja elementov in krˇcitve komutirata, lahko piˇsemo
M . T = (N.T0)|T, kjer je T0 =S0\(S\T). Ampak ker velja
N . T0 = (B . T0)∗∗ = (N∗|T0)∗ (4.3) in je N∗ takˇsen transverzal, da je N∗|T0 transverzal, je zato njegov dual N . T0 strogi gamoid. Zato je njegova skrˇcitev naT, M . T gamoid in je dokaz konˇcan.
Dokaz izreka 4.3. Naj bo M gamoid, M = N|S, kjer je N strog gamoid.
Potem veljaM∗ =N∗. S, kjer je N∗ transverzal in zato gamoid. Zato je kot posledica izreka (4.2) njegov skrˇcen minor N∗. S gamoid.
Ta izreka pa nista edina povezava med gamoidi in transverzalnimi ma- troidi. Gamoidi in transverzalni matroidi se namreˇc direktno nanaˇsajo eni na druge preko naslednjega izreka.
Izrek 4.7([15]). Matroid M je strog gamoid natanko tedaj, ko je njegov dual M∗ transverzalen.
Dokaz tega izreka se skriva kot posledica dokaza izreka (4.1), zato si ga oglejmo.
Dokaz izreka 4.1. Ce veljaˇ X ⊆ V(G), lahko X poveˇzemo v B, ˇce in samo ˇce lahkoX poveˇzemo v B0 ⊆B, kar pa je ekvivalentno pogoju, da je V \X transverzal druˇzine AV\B0.
Zato veljaX ∈L(G, B), ˇce in samo ˇceV\Xvsebuje transverzal odAV\B. Drugaˇce povedano, X ∈L(G, B) ˇce in samo ˇce jeV \X vpet v transverzalni matroidM[AV\,B]. Ampak komplement vpete mnoˇzice matroidaM je neod- visna mnoˇzica dualnega matroida M∗. Torej smo dokazali izrek in hkrati dokazali bolj zanimiv rezultat v obliki izreka (4.7).
Na podroˇcju transverzalnih matroidov je ˇse vedno precej odprtih vpraˇsanj, predvsem povezanih s karakterizacijo doloˇcenih transverzalnih matroidov. Najbolj zanimivo vpraˇsanje je verjetno karakterizacija tistih transverzalnih matroidov, ˇcigar dualni matroidi so prav tako transverzalni [5].
4.2 Matroidi iz linearne algebre
4.2.1 Vektorski matroidi
Pomembna skupina matroidov so vektorski matroidi. Te dobimo iz linearne neodvisnosti vektorjev nad nekim vektorskim prostorom.
Izrek 4.8 ([7]). Matroidu M = (S,I) nad mnoˇzico S pravimo vektorski ma- troid nad poljem F natanko tedaj, ko obstaja matrika A∈Fn,r, n =|S|, r= ρ(M), s paroma razliˇcnimi vrsticami tako, da linearno neodvisne mnoˇzice vrstic matrike A ustrezajo ravno neodvisnim mnoˇzicam matroida M.
Dokaz. Privzemimo, da je M vektorski matroid ranga r nad poljem F. Ustrezna vektorska predstavitev doloˇcar-dimenzionalni podprostorV nekega vektorskega prostora nadF. Potem jeV izomorfenFr. ˇCe za vrstice matrike A vzamemo r-terke iz Fr, ki ustrezajo posameznim elementom mnoˇzice S,
dobimo iskano matriko.
Ce ˇˇ zelimo poudariti, da je ustrezni vektorski prostor nad poljemF, tedaj pravimo, da je M vektorski matroid nad F [7].
Diplomska naloga 23 Oglejmo si primer.
1 2 3 4 5 6 7 8
A=
0 1 1 1 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1
Matrika A je velikosti 5×8 in njeni stolpˇcni vektorji so v R5. Mnoˇzica stolpˇcnih vektorjev matrikeAje{1,2,3,4,5,6,7,8}. Stolpˇcne vektorje bomo obravnavali kot elemente matroida. Za bazo matroida bomo vzeli maksimalne linearne neodvisne mnoˇzice, ki tvorijo stolpˇcni prostor [3]. Oglejmo si dve bazi naˇsega matroida:
B1 =
1 1 0 0 0
,
1 0 1 0 0
,
0 1 0 1 0
,
0 0 0 1 1
,
B2 =
1 1 0 0 0
,
0 1 1 0 0
,
0 0 1 1 0
,
0 0 0 1 1
.
Ce sedaj odstranimo drugi vektor vˇ B1, ga lahko zamenjamo z drugim vektorjem izB2 in tako dobimo novo bazo, B3,
B3 =
1 1 0 0 0
,
0 1 1 0 0
,
0 1 0 1 0
,
0 0 0 1 1
.
V tem primeru vidimo, da je izpolnjena druga lastnost za baze matroida.
Enak rezultat bi dobili, ˇce bi nadaljevali s tem procesom za vse moˇzne baze matrike A. Iz linearne algebre vemo, da nobena baza matrike ni prava podmnoˇzica druge baze, torej je izpolnjena tudi prva lastnost [3].
4.2.2 Predstavljivi matroidi
Ena glavnih prednosti grafovskih matroidov je, da lahko veliko njihovih last- nosti razberemo ˇze iz grafa. Predstavljivost matematiˇcnih objektov nam velikokrat da laˇzji in bolj dostopen vpogled v lastnosti objekta. Zato so pomemben razred matroidov tudi predstavljivi matroidi.
Predstavljivi matroidi so matroidi, ki jih lahko predstavimo kot matroide linearne neodvisnosti vrstic neke matrikeA. MatrikiA takrat pravimo pred- stavitev matroidaM. Predstavitvam, pri katerih so vse vrstice razliˇcne, prav- imo vektorske predstavitve. Vpraˇsanje o karakterizaciji vektorskih matroidov je zastavil ˇze Whitney leta 1935, problem pa je ˇse danes nereˇsen. Kljub temu pa je danes znanih veˇc pomembnih rezultatov o predstavitvah matroidov nad posameznimi polji. Za primer Fanojevega matroida F7 se da pokazati, da ga lahko predstavimo kot vektorski matroid nad polji s karakteristiko 2, hkrati pa velja, da ga lahko predstavimo samo nad polji s karakteristiko 2, ne moremo pa ga predstaviti nad poljubnim poljem [7].
Opomba. Fanojev matroid F7 je definiran na naslednji naˇcin. Z P1, ..., P7 oznaˇcimo premice projektivne geometrijeP G(2,2) na sliki 4.1. Za baze ma- troida F7 vzamemo vse trojke, razliˇcne od P1, ..., P7. Tako izbrana druˇzina mnoˇzic izpolnjuje zahteve za definicijo matroidov z bazami. Dobljen matroid ni niti grafovski niti kografovski [7].
Matroide, ki so predstavljivi nad poljem GF(2) imenujemo dvojiˇski oziroma binarni matroidi, tiste, ki so predstavljivi nad poljem GF(3) pa imenujemo trojiˇski ali ternarni matroidi. Obstajajo pa med matroidi tudi takˇsni, ki jih lahko predstavimo nad poljubnimi polji. Tem pravimo regu- larni matroidi, velika druˇzina katerih so ˇze omenjeni grafovski matroidi.
Diplomska naloga 25
Slika 4.5: Projektivna geometrija P G(2,2) [6].
Enakomerni matroidi. Preden se poglobimo v dvojiˇske, trojiˇske in reg- ularne matroide, moramo za potrebe dokazov nekaterih izrekov definirati ˇse enakomerne matroide.
Recimo, da sta k in n naravni ˇstevili in 0 ≤ k ≤ n. Naj bo S mnoˇzica moˇcin,I pa druˇzina vseh njenih podmnoˇzic s kveˇcjemukelementi. Tedaj je Un,k = (S,I) matroid. Baze so ravno vsek-mnoˇzice, rang mnoˇzice A⊆S pa je enak ρ(A) =|A|, ˇce|A| ≤k, sicer pa jeρ(A) = k. Matroidu Un,k pravimo enakomerni matroid rangak [7].
Dvojiˇski matroidi. Za matroid pravimo, da je dvojiˇski oz. binaren, ˇce je predstavljiv nad poljem GF(2). Pri minorjih smo ˇze omenili, da obsta- jajo razredi, ki so zaprti za minorje. Med te spadajo tudi dvojiˇski minorji.
Najenostavnejˇsi minor, ki ni dvojiˇski, jeU4,2. O tem govori naslednji izrek [7].
Izrek 4.9 ([7]). Matroid U4,2 ni predstavljiv nad poljem GF(2), je pa pred- stavljiv nad poljubnim drugim poljem.
Dokaz. Za predstavitevA matroida U4,2 nad poljem F privzamemo, da je A standardna matriˇcna predstavitev:
A =
1 0 0 1 a b c d
.
Za a, b, c in d se moramo prepriˇcati da so razliˇcni od 0, saj bi drugaˇce imeli linearno odvisne vrstice. ˇCe je F = GF(2), potem sta zadnji vrstici nujno enaki, torej linearno odvisni, kar pa vU4,2 ni res. ˇCe pa jeF =GF(2), tedaj lahko vzamemo a = b = c = 1 za d poljuben element iz F \ {0,1}. Tako
dobimo linearno predstavitev U4,2 nad F.
Tutte je z uporabo tega pokazal prav tako, da dvojiˇske matroide lahko opiˇsemo tako, da prepovemo U4,2 kot minor. To je opisano v naslednjem izreku.
Izrek 4.10 ([14]). Matroid je dvojiˇski natanko tedaj, ko ne vsebuje matroida U4,2 kot minor.
To sta le dve karakterizacij dvojiˇskih matroidov, obstaja jih ˇse veliko veˇc, preostale se nanaˇsajo predvsem na cikle.
Trojiˇski matroidi Na podoben naˇcin kot dvojiˇski matroidi so definirani tudi trojiˇski matroidi. Matroid jetrojiˇski aliternarni, ˇce je predstavljiv nad poljem GF(3). Tudi trojiˇski matroidi so karakterizirani s prepovedanimi minorji, kar je napovedal Ralph Reid ˇze leta 1971, dokaz pa je leta 1979 objavil Bixby [1].
V primerjavi z dvojiˇskimi matroidi je prepovedanih minorjev pri trojiˇskih matroidih veˇc. O teh minorjih govori naslednji izrek.
Izrek 4.11 ([7]). Za matroid M pravimo, da je trojiˇski natanko tedaj, ko nima minorja, izomorfnega F7, F7∗, U5,2 ali U5,3.
Diplomska naloga 27 Regularni matroidi Za matroid pravimo, da je regularen, ˇce je pred- stavljiv nad poljubnim poljem. Karakterizacijo regularnih matroidov s pre- povedanimi minorji je podal Tutte.
Izrek 4.12 ([14]). Matroid je regularen natanko tedaj, ko nima minorja, izomorfnega U4,2, F7 ali F7∗.
Kot posledica zadnjih izrekov sledi naslednji izrek.
Izrek 4.13 ([7]). Matroid je regularen natanko tedaj, ko je hkrati dvojiˇski in trojiˇski.
Dokaz. Iz definicije ˇze sledi, da je regularen matroid dvojiˇski in trojiˇski, saj je predstavljiv nad vsemi polji, zahteva za dvojiˇski in trojiˇski matroid pa je le predstavljivost nad poljemGF(2) oziromaGF(3). Nasprotna trditev pa sledi iz izrekov (4.10), (4.11) in (4.12) ter dejstva, da je matroidU4,2(= U4,2∗ )
minor matroida U5,3 =U5,2∗ .
Tutte je predstavil ˇse eno karakterizacijo regularnih matroidov. Matroid M je regularen, ˇce je predstavljiv nadGF(2) in nekim poljem, ki ima karak- teristiko razliˇcno od 2 [9].
Poglavje 5
Poˇ zreˇ sna metoda
Podali bomo ˇse eno zanimivo karakterizacijo matroidov. Atraktivna lastnost te karakterizacije je, da lepo nakaˇze zakaj se matroidi naravno pojavijo v problemih kombinatoriˇcne optimizacije. Najbolj znana algoritmiˇcna lastnost matroidov je njihova zveza z algoritmom, poimenovanim ”Poˇzreˇsna metoda”.
V grobem poˇzreˇsna metoda najde maksimalen napredek za neko objektivno funkcijo na vsakem koraku in nikoli ne gleda nazaj. Videli bomo, da s tem pristopom optimiziramo funkcijo natanko takrat, ko ima struktura, ki stoji za algoritmom, matroidne lastnosti. Osnovna ideja za grafe je znan rezultat, ki ga je predstavil W. Kruskal, razˇsiritev na matroide pa je opisal Rado [14, 10].
Naj boS konˇcna mnoˇzica in naj boF mnoˇzica podmnoˇzicS z lastnostjo, da ˇce A ∈ F, B ⊆ A sledi B ∈ F. Naj bo w : S → R+ funkcija cene in na naraven naˇcin razˇsirimo
w(A) = X
e∈A
w(e) (A ⊆S). (5.1)
Recimo, da nas zanima kako najti podmnoˇzico A0 mnoˇzice S z naslednjimi lastnostmi:
1. A0 ∈ F;
2. w(A0) je maksimum med vsemi w(X), kjerX ∈ F. Ta problem imenujemo (F, w) [15].
29
Poˇzreˇsni algoritem za problem (F, w) je avtomatski postopek za izbiro elementa iz F. Postopek sledi takole:
Algoritem 1: Poˇzreˇsna metoda
while Obstajajo ˇse neizbrani elementi v F do
if Obstaja tak element xk razliˇcen od x1, ..., xk−1, da velja x1, x2, ..., xk−1, xk ∈ F in da je w(xk) maksimalen med vsemi takimi x. then
Izberemo xk; else
Ustavimo postopek;
Ko se poˇzreˇsna metoda ustavi, imamo podmnoˇzico X od S, kjerX ∈ F. Pravimo, da poˇzreˇsna metoda deluje, ˇce w(X)≥w(A) za vsak A∈ F.
Pomemben rezultat je naslednji:
Izrek 5.1 ([15]). ˇce je F mnoˇzica neodvisnih mnoˇzic matroida na S, deluje poˇzreˇsna metoda za optimizacijski problem (F, w).
Dokaz. Naj boBbaza matroidaM, izbrana s poˇzreˇsno metodo in recimo, da je T baza matroida M, kjer w(T) > w(B) z nadaljno lastnostjo, da je
|T ∩B| maksimalen. Naj bo xk prvi element, izbran s poˇzreˇsno metodo, ki pripadaB \T. Potem obstaja minimalna odvisna mnoˇzica C, da velja
xk ∈C ⊆T ∪ {xk}.
Naj bo y ∈ C\B, tako da je (T \y)∪ {xk} baza matroida M. Ker ima T maksimalno ceno, velja w(y) ≥ w(xk), hkrati pa w(y) ne more biti strogo veˇcje od w(xk), saj bi v nasprotnem primeru poˇzreˇsna metoda izbrala y in ne xk. Torej velja w(y) = w(xk) in sledi, da ima tudi T1 = (T \y)∪ {xk} maksimalno ceno. Ampak T1 ima veˇc skupnih elementov z B kot s T, kar
nasprotuje izbiri T in zato dokaˇze izrek.
Se bolj presenetljiv rezultat je, da velja obratno.ˇ
Izrek 5.2 ([15]). Naj bo F mnoˇzica podmnoˇzic S z lastnostjo, da iz A ∈ F, B ⊆ A sledi B ∈ F. Potem poˇzreˇsna metoda deluje za (F, w) za vse
Diplomska naloga 31 nenegativne funkcije cene w samo, ˇce je F mnoˇzica neodvisnih mnoˇzic ma- troida na S.
Dokaz. Pokazati moramo samo, da ˇce A = {a1, . . . , ak} ∈ F in B = {b1, . . . , bk+1} ∈ F, potem obstajabi ∈/A in A∪ {bi} ∈ F. Da vidimo, da to drˇzi, definiramo funkcijo cene w naS kot
w(ai) =u 1≤i≤k, w(bi) =v bi ∈B\A,
w(e) = 0 e∈S\(A∪B),
kjer w > v > 0. Potem poˇzreˇsna metoda izbere elemente a1, ..., ak po vrsti.
Ce ne obstajaˇ bi, da je {bi, a1, ..., ak} elementF, bo algoritem potem naprej izbral elemente iz S \(A∪B) in se bo zaustavil, ko izbere element iz F s ceno w(A).
Ce pa veljaˇ |B∩A|=t, vidimo, da
w(A) =ku, w(B) =tu+ (k+ 1−t)v.
Izberemou, v, da veljaw(A)< w(B) inu > v. To je oˇcitno mogoˇce in potem poˇzreˇsna metoda ni izbrala elementaF z maksimalno ceno. To je protislovje,
ki dokaˇze izrek.
Opazimo, da nam ta izrek da sledeˇco uporabno karakterizacijo matroidov:
Izrek 5.3 ([15]). Neprazna mnoˇzica F podmnoˇzic S je mnoˇzica neodvisnih mnoˇzic matroida na S natanko tedaj, ko
a) iz X ∈ F in Y ∈S, sledi Y ∈ F;
b) za vse nenegativne funkcije cene w : S → R, poˇzreˇsna metoda izbere element A iz F, kjer
X
e∈A
w(e)≥X
e∈B
w(e)
za vse elemente B iz F.
Poglavje 6
Problem pakiranja in pokritja
ˇSe en zanimiv optimizacijski problem, pri katerem se pokaˇze uporabnost ma- troidov, je problem pakiranja in njegov dual, problem pokritja. Da lahko definiramo problem in rezultate, ki nam jih ponujajo matroidi, moramo definirati ˇse nekaj pojmov.
Ce staˇ M1 in M2 matroida nad isto mnoˇzico S, je potem funkcija ρ12 = ρ1+ρ2 monotona, submodularna in ρ12(∅) = 0. Ta funkcija doloˇca matroid nad S, za katerega je funkcija ranga doloˇcena z:
ρ(A) = min
X⊆A(ρ1(X) +ρ2(X) +|A\X|).
Ta matroid oznaˇcimo z M1 ∨M2 in ga imenujemo unija matroidov M1 in M2. Lahko pa unijo matroidov opiˇsemo tudi na drug naˇcin. Pri osnovni mnoˇzici S vzamemo disjunktni kopiji te mnoˇzice, recimo S1 = S × {1} in S2 =S×{2}. ˇCe zM10 inM20 oznaˇcimo matroidaM1 inM2, kjer smo mnoˇzico S zamenjali sS1 inS2, velja: M1∨M2 =f(M10⊗M20), kjer jef :S1∪S2 →S naravna projekcija naS, kar pomeni, da f(s,1) = s inf(s,2) =s [7].
Iz drugega opisa unije sledi, da so neodvisne mnoˇzice v uniji M1 ∨M2 f-slike neodvisnih mnoˇzic v M10 ⊗ M20, torej oblike A = A1 ∪ A2, kjer A1 ∈ I(M1), A2 ∈ I(M2). Iz tega izhaja tudi ime ”unija”. Velja, da ˇce so M1, M2, . . . , Mk matroidi nad isto osnovno mnoˇzico S, definiramo unijo M1∨M2∨ · · · ∨Mk kot matroid, ki ima funkcijo ranga definirano s predpisom ρ(A) = min
X⊆A(ρ1(X) +· · ·+ρk(X) +|A\X|) [7].
33
Tudi sama konstrukcija unije je zelo uporabna. Uporabimo jo lahko za to, da preverimo, ali ima matroid dve disjunktni bazi. Preprosto pogledamo unijo M ∨M in ˇce je rang unije enak dvakratnemu rangu matroida M, to drˇzi [7].
S tem se pribliˇzamo bolj sploˇsnemu problemu, problemu pokritja in prob- lemu pakiranja. Pri problemu pokritja skuˇsamo celotno mnoˇzico S pokriti z najmanjˇsim moˇznim ˇstevilom baz, pri problemu pakiranja pa skuˇsamo v matroidu M najti ˇcim veˇc paroma disjunktnih baz [7].
Za ta problema se izkaˇzeta pomembna rezultata. Pri problemu pakiranja velja:
Izrek 6.1 ([7]). matroid M nad S ima k disjunktnih baz natanko tedaj, ko za vsako mnoˇzico A∈S velja k(ρ(S)−ρ(A))≤ |S\A|.
Dokaz. Predpis A→kρ(A) doloˇca submodularno in monotono funkcijo, ki ima vrednost 0 pri A=∅. Funkcijaρ(k), ki je definirana kot
ρ(k)(X) = min
Y⊆X(kρ(Y) +|X\Y|), X ⊆S,
je funkcija ranga nekega matroida M(k) nad S. Ta matroid, torej M(k) je v bistvu unija k kopij matroida M. Za neodvisne mnoˇzice v M(k) vemo, da so ravno unije po k neodvisnih mnoˇzic iz M. Zato ima matroid M k disjunktnih baz natanko tedaj, ko velja ρ(k)(S) ≥ kρ(S). ˇCe upoˇstevamo definicijo funkcije ρ(k), vidimo, da je ta pogoj ekvivalenten pogoju iz izreka.
S tem smo dokazali izrek.
Pri problemu pokritja pa velja:
Izrek 6.2([7]). Osnovno mnoˇzicoS matroida M lahko pokrijemo sk bazami natanko tedaj, ko za vsako mnoˇzico A∈S velja: kρ(A)≥ |A|.
Dokaz. Za dokaz tega izreka upoˇstevamo, da je S unija kveˇcjemu k baz natanko tedaj, ko je unija kveˇcjemu k neodvisnih mnoˇzic matroida M. Ta zahteva pa je ravno ekvivalentna zahtevi, da jeS neodvisna mnoˇzica vM(k), torej ρ(k)(S) = |S|. ˇCe upoˇstevamo definicijo funkcije range iz prejˇsnjega
dokaza, dobimo od tod ravno ta izrek.
Diplomska naloga 35 Iz rezultatov, ki jih dobimo pri definiranju funkcije ranga za matroid unije, sledijo trije znani izreki iz kombinatorike, in sicer Hornov, Truttov in Nash-Williamsov izrek.
Preden si ogledamo prvega izmed treh izrekov, si oglejmo ˇse naslednjo definicijo.
Naj boV vektorski prostor nad obsegomO inM ⊆V neprazna mnoˇzica.
Mnoˇzico vseh linearnih kombinacij elementov iz M imenujemo linearna ogrinjaˇca mnoˇzice M. Oznaˇcimo jo z Lin(M).
Hornov izrek pravi, da je konˇcna mnoˇzica S vektorjev (elementov vek- torskega prostora Fn) unija k linearno neodvisnih podmnoˇzic mnoˇzice S natanko tedaj, ko za vsako mnoˇzico A∈S velja
|A| ≤k·dim(Lin(A)) =k·rang(A) [4].
Tuttov izrek pravi, da povezan grafGvsebujekdisjunktnih vpetih dreves natanko tedaj, ko za vsako razbitje mnoˇzice toˇckV(G) naprazredov obstaja vsaj k(p−1) povezav, ki povezujejo toˇcke v razliˇcnih razredih razbitja [13].
Nash-Williamsov izrek pa pravi, da lahko v grafu G, E(G) pokrijemo s k acikliˇcnimi podgrafi grafa Gnatanko tedaj, ko za vsako neprazno mnoˇzico toˇck A∈V(G) velja |E(A)| ≤k(|A| −1) [8].
Literatura
[1] Robert E. Bixby. On Reid’s characterization of the ternary matroids.
Journal of Combinatorial Theory, Series B, 26(2):174–204, 1979.
[2] William H. Cunningham. The coming of the matroids. Documenta Mathematica, Extra volume: Optimization Stories(1):143–153, 2012.
[3] Hayley Hillman. Matroid theory. Dosegljivo: https://www.
whitman.edu/Documents/Academics/Mathematics/hillman.pdf, 2003. [Dostopano 21. 5. 2021].
[4] Alfred Horn. A characterization of union of linearly independent sets.
Journal of the London Mathematical Society, s1-30(4):494–496, 1955.
[5] AW Ingleton and MJ Piff. Gammoids and transversal matroids. Journal of Combinatorial Theory, Series B, 15(1):51–68, 1973.
[6] Matroid. Dosegljivo: http://https://en.wikipedia.org/wiki/
Matroid, 2003. [Dostopano 17. 8. 2019].
[7] Bojan Mohar. Teorija Matroidov. Druˇstvo matematikov, fizikov in as- tronomov Slovenije, 1996.
[8] C. St.J. A. Nash-Williams. Edge-Disjoint Spanning Trees of Finite Graphs. Journal of the London Mathematical Society, s1-36(1):445–450, 1961.
[9] James Oxley. What is a matroid. Cubo Matem´atica Educacional, 5(3):179–218, 2003.
37
[10] James Oxley. Matroid Theory. Oxford University Press, 2011.
[11] Hazel Perfect. Applications of menger’s graph theorem. 1968.
[12] Richard Rado. A theorem on independence relations. The Quarterly Journal of Mathematics, (1):83–89, 1942.
[13] W. T. Tutte. On the Problem of Decomposing a Graph into n Connected Factors. Journal of the London Mathematical Society, s1-36(1):221–230, 1961.
[14] William T. Tutte. Lectures on matroids. 1965.
[15] D.J.A Welsh. Matroid Theory. Academic Perss Inc. (London) Ltd., 1976.
[16] Hassler Whitney. On the abstract properties of linear dependence.
American Journal of Mathematics, 57(3):509–533, 1935.
