Matroidai

Algoritmų teorijoje svarbią vietą užima godūs algoritmai. Jie aiškūs ir lengvai realizuojami, veikia ganėtinai greitai ir žinoma daug įvairių uždavinių, kuriuos galima išspręsti jų pagalba. Tad pristatysime jų pagrindą – matroidų teoriją. Ji neretai leidžia nustatyti apie godaus algoritmo pritaikomumą. Tam pakanka, kad tiriame aibė būtų matroidas...

Apibrėžimai

Ciklu grafe vadinsime uždarą kelią grafe, kai bet kuri grafo briauna panaudojama tik vieną kartą.
Paprastu ciklu vadinsim tokį ciklą, kai pašalinus vieną ciklo briauną, jis nustoja būti ciklu.

Visi nagrinėjami grafai yra neorientuoti. Grafo G grafinį matroidą žymėsime M(G). Matricos A vektorinį matroidą žymėsime M[A].

Kas yra matroidas?

Paimkime tokią matricą:

1 0 0 1 0 0 0
0 1 0 1 1 1 0
0 0 1 0 1 1 0

Tegu aibę E sudaro {1, 2, 3, 4, 5, 6, 7} – matricos stulpelių numeriai, o aibę I sudaro tokie E poaibiai, kad jų apibrėžiami vektoriai yra tiesiškai nepriklausomi2) virš realių skaičių lauko R. Kokiomis savybėmis pasižymi I?

1. Aibė I nėra tuščia. Net jei pradinė aibė E yra tuščia (E=Æ), I sudaro vienintelis elementas – tuščia aibę (I={{Æ}}).

2. Bet kuris I poaibis yra šios aibės elementas. Tai gana aišku – nes jei tam tikras vektorių rinkinys yra tiesiškai nepriklausomas virš lauko, tai tokie bus ir visi jo poaibiai. Tai vadinamoji paveldimumo savybė.

3. Jei X, Y priklauso I ir |X|=|Y|+1, tada egzistuoja x Î X-Y, toks, kad Y È {x} priklauso I. Vėliau ji taps aiškesnė.

Tada matroidu vadinama aibių pora E, I, susidedanti iš baigtinės aibės E, vadinamos matroido bazine aibe, ir jos poaibių aibės I, vadinamos matroido nepriklausomų aibių aibe, kai I tenkina prieš tai išvardintas savybes.

Įrodysime, kad pavyzdyje pateikta tiesiškai nepriklausomų stulpelių aibė yra matroidas. Tam pakanka įrodyti trečiąją savybę.

Įrodymas. Tegu X, Y < I ir |X|=|Y|+1. Tegu W bus vektorių, apimančių X v Y, erdvė. Aišku, kad jos matas ne mažesnis už |X|. Tarkim, kad Y È {x} bus tiesiškai priklausoma visiems x Î X-Y (t.y., minima savybė netenkinama). Tada Y sudaro pagrindą erdvėje W. Iš to seka, kad |X| £ dim W £ |Y|. Tačiau, kadangi pagal sąlygą X ir Y sudarytos iš tiesiškai nepriklausomų vektorių ir |X| > |Y|, gauname prieštaravimą. Tokia vektorių aibė yra matroidu. Jį kartais vadina vektoriniu matroidu.

Panagrinėkime tokį grafą G:
Graph for matroid

Grafas neorientuotas ir jį sudaro 4 viršūnės ir 7 briaunos, kurių viena yra kilpa. Tegu E yra to grafo briaunų aibė, t.y. {1, 2, 3, 4, 5, 6, 7}, o aibė I - aibė tokių E poaibių, kad bet kuris I elementas neturi grafo kilpų. Ši aibių E, I pora yra matroidas, kuris vadinamas grafiniu matroidu, žymimas M(G).

Teorema. Tegu G – grafas, o AG - jo incidencijų matrica1). Jei AG nagrinėsime kaip matricą virš lauko {0,1}, kuriame visos operacijos atliekamos moduliu 2, tai tada iš nepriklausomų aibių A sudarytas matroidas turės briaunų aibę, savyje neturinčią ciklų; ir M(G)=M[AG].

Įrodymas. Būtina įrodyti, kad X Ì AG yra tiesiškai priklausomas tada ir tik tada, kai X turi ciklą. Tarkim, kad X turi ciklą C. Jei C yra kilpa, tada į X įeis nulinis vektorius, esanti priklausomu. Jei C nėra kilpa, tai kiekviena viršūnė cikle atitiks dvi C briaunas ir vektorių suma moduliu 2 bus nulinis modulis. Todėl X yra tiesiškai priklausomas.

Dabar tarkim, kad X yra tiesiškai priklausomas. Paimkim minimalų tiesiškai priklausomą jo poaibį D (D Ì X), t.y. tokį, kad jame pašalinus bet kurį elementą gausime tiesiškai nepriklausomą poaibį. Jei D sudarys nulinis vektorius, tada X turi kilpą ir, tokiu būdu, ciklą. Tegu D neturi nulinio vektoriaus. Kadangi lauke {0, 1} tėra vienintelis nenulinis elementas ( 1 ), tai D esančių vektorių suma bus nuliniu vektoriumi todėl, kad D yra minimalus tiesiškai priklausomas poaibis. Ir to seka, D apima ciklo briaunas ir jei kokiai nors viršūnei incidentali briauna iš D, tad egzistuoja dar bent viena jai incidentali briauna.

Ir tikrai, paimkime briauną d1, kurią atitinką viršūnės v1 ir v2. Tegu v2 būna kitos briaunos d2 galu. Tęsdami šį procesą gausime dvi sekas v, v, ... ir d, d, ... Kadangi D turi baigtinį viršūnių kiekį, tai kažkuri jų turi pasikartoti. Kai tai įvyks, poaibyje bus surastas ciklas – taigi, ciklas bus ir X (nes D Ì X).

Bazės ir paprastieji ciklai

Matroido bazė - maksimali nepriklausoma matroido aibė.
Paprastas matroido ciklas - minimali priklausoma matroido aibė

Imkim dvi aibes: 1) iš visų įmanomų matroido M bazių, kurią žymėsim BM; 2) iš visų įmanomų paprastų matroido M ciklų, kurią žymėsim CM. Kadangi matroidai pasižymi paveldimumo savybe, bet kuri šių aibių gali pilnai apibrėžti matroidą.

Teorema. Aibė X yra matroido M bazių aibe tada ir tik tada, kai tenkinama:
1) B nėra tuščia;
2) Jei B1, B2Î B, x Î B1 - B2, tada egzistuoja y Î B1 - B2, toks, kad (B-x) È {y} Î B.

Įrodymas.

Tegu patenkintos abi sąlygos. Būtina įrodyti, kad B apima visas bazes. Tarkim, kad taip nėra. Tegu B1 Î B. Tačiau egzistuoja elementas I toks, kad B1 È {I} Î B, I = B1 - B. Tačiau tada toks elementas Y Î B – (B È {I} ) neegzistuoja.

Tegu B - bazių aibė. Įrodysime, kad ji tenkina abi sąlygas. Pirma savybė – akivaizdi. Panagrinėkime antrąją. x Î B1 - B2. Tačiau neegzistuoja toks y Î B2 - B1, kad B1 - x È {y} Î B. Tačiau tai prieštarauja trečiajai matroidų savybei, nes | B1 - {x}| + 1 = | B2 | - ir toks y privalo egzistuoti.

Išvada. Visų bazių galios vienodos (pagal antrą savybę). Matroido rangu vadinama jo bazės galia.

Teorema. Aibė C yra paprastų matroido ciklų aibe tada ir tik tada, kai patenkinta:
1) Nė vienas C elementas nėra tuščia aibė;
2) Nė vienas C elementas nėra kito C element poaibiu;
3) Jei C1 ir C2 Î C bei e Î C1 Ç C2, tai C1 È C2-e turi kokį nors C elementą.

Įrodymas. Analogiškas anksčiau pateiktiems įrodymams. Skaitytojai gali pamiklinti savo smegenis, o rezultatus užrašyti komentaruose.

Matroidai ir kombinatorinė optimizacija

Matroidai plačiai taikomi kombinatorinės optimizacijos uždaviniuose, o taip pat uždaviniuose, kurių sprendimas pagrįstas godžiais algoritmais.

Panagrinėkime tokį uždavinį: darbų vykdytojas turi vienam žmogui skirtų m vienadienių darbų J1, J2, J3, ... Jn. Taip pat jis turi n darbininkų, kurių kiekvienas moka atlikti kažkokius iš tų darbų (jų poaibį). Vykdytojas nori žinoti, kiek daugiausia darbų jo darbininkai gali atlikti per vieną dieną. Kaip vėliau paaiškės, tai bus tam tikro matroido rangu.
Graph for task with matroid

Tegu A - tam tikros aibės E poaibių aibė. Pvz., tegu A=({1, 2, 4}, {2, 3, 5, 6}, {5, 6}, {7}) iš E={1, 2, 3, 4, 5, 6, 7}. Poaibis E-{x1, x2, ... xk} vadinamas daliniu transversaliu A, jei yra abipusis atitikimas F tarp {1, 2, ..., k} ir {1, 2, ..., m}, kai xj Î AF(j) bei kuriam j. Jei m=k, tai toks dalinis tranversalis vadinamas tranversaliu. Aibė {2, 3, 5, 6} yra A {2, 3, 5, 6}, kaip matosi piešinyje.

Teorema. Tegu A - kokia nors E poaibių aibė, o I aibės A dalinių transversalių aibė. Tada pora E, I - matroidas.

Įrodymas. Bet kuris dalinio transversalio poaibis - dalinis transversalis. Tuščia aibė – irgi dalinis transervalis. Todėl pirmos dvi matroidų savybės tenkinamos. Trečios savybės įrodymui sukurkim dvidalį grafą3) (jis ir maksimalus porų skaičius parodytas piešinyje). Tegu viršūnės kairėje atitiks E elementus, o dešinėje - A elementus. Briauna iš kairės į dešinę yra tada ir tik tada, kai atitinkamas kairės pusės elementas priklauso atitinkamam dešinės pusės elementui. Dalinis transversalis atitinka porą grafe. Tegu X ir Y yra daliniai transversaliai ir |X|=|Y|+1. Nuspalvinkime X atitinkančias briaunas mėlynai, o atitinkančias Y - raudonai. Beje, briaunos, atitinkančios dvi poras, bus nuspalvintos purpurine spalva. Taip gauname |X- Y| mėlynos spalvos briaunų, |Y-X| raudonos spalvos briaunų – ir tenkinama |X-Y|=|Y-X|+1. Paimkim pografį H, indikuotą raudonomis ir mėlynomis pradinio grafo briaunomis. Kiekviena viršūnė atitinka arba dviem briaunom – mėlynai ir raudonai, arba vienai – mėlynai arba raudonai. Aišku, kad bet kuri jungi komponentė sudaro arba kelią, arba ciklą, susidedantį iš pakaitomis einančių raudonų ir mėlynų briaunų. Kadangi grafas dvidalis, bet kurį ciklą sudaro lyginis briaunų skaičius. Kadangi mėlynų briaunų viena daugiau nei raudonų, tai privalo egzistuoti kelias, prasidedantis ir besibaigiantis mėlyna briauna. Tą kelią pažymėkime H‘. Sukeiskime H‘ raudonas ir mėlynas spalvas. Gauname, kad briaunos, nuspalvintos raudona ir purpurine spalva sudaro poras grafe. Toliau nesunku įrodyti, kad šį naują porų rinkinį atitinkantis poaibis E yra pavidalo Y È {x}, kur x - kažkuris X-Y elementas.

Grįžkim prie anksčiau iškelto uždavinio. Aišku, kad dalinių transversalių matroido rangas atitiks maksimalios porų derinių dvidaliame grafe aibės galiai, kuri, savo ruožtu, lygus maksimaliam darbų, kuriuos darbuotojai gali atlikti per vieną dieną, skaičiui.

Godusis algoritmas

Pasvertas matroidas - toks, kai aibės E elementams yra priskirta svorio funkcija w.

Tada godusis algoritmas:
BG=Æ. Kol egzistuoja e Ï BG toks, kad BG È {e} Î I ir w(e) yra maksimalus, BG := BG È {e}.

Lema. Godusis algoritmas kuria nepriklausomą maksimalaus svorio aibę.

Įrodymas. Kadangi svoriai teigiami, tai maksimalaus svorio aibė bus matroido baze. Tegu BG={e1, e1, e1, ..., er}, išrašant elementus algoritmo išrinkimo tvarka. Tada w(e1) >= e2 >= ... >= er. Panagrinėkime bazę B={f1, f1, f1, ... f1}, kurios elementai išrašyti mažėjimo tvarka. Tegu ji būna maksimalaus svorio baze. Toliau įrodysime, kad visada galioja nelygybė w(ek) >= w(fk).

Įrodinėsime prieštaravimo būdu. Tegu k+1 bus mažiausiu indeksu, kuriam tas santykis nebus tenkinamas, t.y. bus w(ek+1) < w(fk+1. Imkim dvi aibes: Y={e1, e1, e1, ..., er, X={f1, f1, f1, ... f1}. Pagal trečią matroidų savybę Y È {fj} Î I kiekvienam j Î {1,2, ..., k, k+1}. Tačiau w(fj) >= w(fk+1 >= w(ek+1). Tačiau algoritmas privalėjo išrinkti w(fj) vietoje ek+1. Gauname prieštaravimą – todėl w(ej) >= w(fj). Kadangi naudota prielaida, kad B yra maksimalaus svorio, tai seka, kad algoritmas tikrai kuria nepriklausomą maksimalaus svorio aibę.

Kraskalo algoritmas

Šio algoritmo veikimo pradžioje yra |V| nepriklausomų komponenčių, kurių kiekviena sudaryta tik iš vienos viršūnės. Tada kiekvieno žingsnio metu išrenkama dvi viršūnes jungianti mažiausio svorio briauna ir įtraukiama į jau suformuoto minimalaus karkasinio medžio4) aibę, o tos dvi komponentės sujungiamos į vieną. Kai belieka viena komponentė – minimalus karkasinis medis sukurtas.

Anksčiau nagrinėjome grafo matroidą ir įrodėme, kad jis iš tikro yra matroidu. Akivaizdu, kad to matroido bazes atitiks karkasiniai medžiai iš G. Tad kaip galime panaudoti ką tik pateiktą godųjį algoritmą minimalaus Karkasinis medžio sudarymui?

Tegu G - grafas, kurio briaunoms priskirta svorio funkcija w >= 0. Įveskime naują svorio funkciją w*=M-w+1, kur M – mažiausias briaunos grafe G svoris. Aišku, kad karkasinio medžio svorio minimizacija susiveda į nepriklausomos maksimalaus svorio aibės su svorio funkcija w* suradimą. Tai galima pasiekti panaudojant godų algoritmą, ką iš tikro ir daro Kraskalo algoritmas. Tik čia jo mes neapžvelgsime - apie jį skaitykite atskirame puslapyje.

Ilgėjančių grandinių algoritmas

Grįžtant prie dalinių transversalijų matroido, tenka apgailestauti, kad taip paprastai nepavyksta išspręsti maksimalaus porų grafe skaičiaus uždavinio. Be to, kad dalinių transversalijų aibė yra matroidu, reikia algoritmo, leidžiančio nustatyti poras – ir tai ilgėjančių grandinių algoritmas. Iš to, kad aibė yra matroidas, pasiekiama, kad, pasinaudojus turimomis poromis, galima ieškoti vienetu didesnės galios poros.

Teorema. Tegu I - aibės E poaibių aibė. Tada E, I yra matroidu tada ir tik tada, kai tenkinamos pirmos dvi matroidų sąlygos, ir pagal bet kurią teigiamą svorio funkciją w aibėje E, godus algoritmas kuria nepriklausomą maksimalaus svorio aibę.

Įrodymo čia nepateiksime. Jį galima rasti James Oxley straipsnyje „Kas yra matroidas?“ Tik atkreipsime dėmesį, tad tai parodo, kad matroidai yra vienintelėmis hierarchinėmis struktūromis, kurioms pritaikomas godus algoritmas.

J. Oxley. What is a matroid // Cubo, no.5, 2003

 

Papildomi paaiškinimai

1) Grafo incidencijų matrica – lentelė, kurios kiekviena eilutė atitinka grafo mazgą, o stulpelis – grafo briaunas. Jei i-oji briauna išeina iš mazgo, tai i-tos eilutės j-me stulpelyje įrašom +1. Jei i-oji briauna nukreipta į mazgą, tai i-tos eilutės j-me stulpelyje įrašom -1. Visi kiti incidencijų matricos elementai lygūs 0.

2) Linear Vectors n-mačių vektorių aibė S={a1; a2; ... ; ak} vadinama tiesiškai priklausoma, jei bent vienas šios aibės vektorius yra kitų vektorių tiesinis darinys.

3) Dvidalis grafas – tai grafas, kurį sudaro 2 pografiai ir kiekviena grafo briauna jungia pirmojo pografio viršūnę su antrojo pografio viršūne.
Dvidalis grafas

4) Miškas – tai beciklis grafas.
Jungusis miškas – tai beciklis grafas, kuriame egzistuoja kelias tarp bet kurių jo viršūnių.
Medis – tai jungusis miškas.
Jungiantysis medis – tai medis, kurio viršūnių aibė sutampa su visa grafo viršūnių aibe, o briaunų aibė yra grafo briaunų aibės poaibis.
Karkasinis medis – tai minimalus jungiantysis medis.

5) Kraskalo algoritmą jungiame neorientuotame grafe su svoriais pirmąkart 1956 m. aprašė Džozefas Kraskalas (Kruskal)

Pradžioje turime tuščią aibę. Tada, kol įmanoma, atliekama tokia operacija: iš visų briaunų, kurias įjungus prie jau parinktų, nesusidaro ciklas, išrenkama mažiausio svorio briauna. Kai tokių briaunų nebelieka, algoritmas baigia darbą. Tada pografis, kurį sudaro visos jo viršūnės ir surastos briaunos, sudaro grafo karkasinį medį.

Algoritmo įvertinimas. Kadangi pradžioje reikia surūšiuoti visas briauna pagal jų svorius, tai reikalauja O (E x log(E)) laiko. Tada jungumo komponentes patogu saugoti nepersikertančiose aibėse. Tokiu atveju visoms operacijoms reikės O(Exa(E,V)), kur a – funkcija, atvirkštinė Akermano funkcijai. Kadangi bet kokiems praktiniams uždaviniams a(E,V)<5, tai ją galima paimti kaip konstantą, tad bendru Kraskalo algoritmo veikimo laiku laikyti O(E x log(E)).

Kraskalo algoritmas tikrai randa grafo minimalaus svorio karkasinį medį, nes jis yra Rado- Edmondso algoritmo grafiniam matroidui atveju (kai nepriklausomos aibės – aciklinės briaunų aibės).

Daugiau:

Pirminiai skaičiai
Kraskalo algoritmas
Monte-Karlo metodas
Kokiu greičiu skriejame?
Nekritinė stygų teorija
Skaičiai – apžvalga/ pradmenys
Revoliucija mazgų teorijoje
Izingo modelis įmagnetinimui
Pagrindinės statistinės sąvokos
Kombinatorika, polinomai, tikimybės
Greičiais C besiplečiančios–besitraukiančios erdvės B
Mokslo ribotumas: Dievas, Giodelis ir gravitacija
Tjorstono geometrizacijos teiginys
Da Vinči matematinė klaidelė
Specialioji reliatyvumo teorija
Diagramos, pakeitusios pasaulį
Didžiausias bendras daliklis
Paviliota senovinio žaidimo
Scenoje - paprastos grupės
Išmatavimų triauškintojas
Visata kaip kompiuteris
Harmoninės eilutės
Nešo pusiausvyra
Smeilo paradoksas
Dalyba iš nulio
Perkoliacija
Ferma taškas
Vartiklis