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 tiriama 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:
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ų AG 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 v0, v1, ... ir d1, d2, ... 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.
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
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.
