Un concept matematic pe zi: Matroizi

Cu toții am trecut prin liceu, s-ar putea să ne mai amintim de spații vectoriale, mulțimi liniar independente de vectori, baze, etc. Dacă suntem informaticieni suntem probabil familiari – ca majoritatea românilor, la nivel intuitiv – cu algoritmul Greedy, exprimat prin filosofia de viață „alege ce ți-e cel mai bine pentru moment; despre viitor ne vom ingrijora mai târziu” 🙂

Dacă am luat un curs de algoritmică s-ar putea să ne amintim că algoritmul Greedy găsește soluția optimă pentru problema arborelui parțial de cost minim – altfel spus maniera optimă de a crea o rețea intre n noduri este de a alege in mod repetat muchia incă nealeasă de cost minim atâta timp cât aceasta nu creează un ciclu cu muchiile alese anterior (algoritmul schițat se numește algoritmul lui Kruskal)

Conceptul despre care vreau să vă povestesc in minutul de matematică pe ziua de azi unifică toate aceste lucruri. Deși deja clasic pentru cei care se ocupă cu combinatorica sau informatica teoretică (Cormen ii dedică un capitol din cursul de algoritmi) el este unul puțin cunoscut, chiar de către matematicienii puri. Motiv pentru popularizarea de față 🙂

*

Așadar ce este un matroid ? Simplu, o pereche formată din

  • un univers U (o mulțime de elemente)
  • o familie \mathcal{F} de părți ale lui U pe care le vom numi mulțimi independente.

Evident, \mathcal F trebuie să satisfacă niște axiome de bun-simț (mai precis două):

  • dacă A\in \mathcal{F} și B\subseteq A atunci B\in \mathcal{F} („orice submulțime a unei mulțimi independente e la rândul ei independentă„)
  • dacă A,B\in \mathcal{F} sunt maximale (astfel de mulțimi se numesc, deloc surprinzător, baze) atunci |A|=|B|. („oricare două baze au aceeași dimensiune„)

Ultima axiomă are o formulare echivalentă, numită axioma schimbului:

  • dacă A, B sunt mulțimi independente și |A|<|B| atunci există x\in B\setminus A astfel incât A\cup \{x\} să fie in continuare independentă.

*

O.K., e timpul pentru niște exemple.

Evident, orice mulțime finită de vectori v_{1},v_{2}, \ldots, v_{n} intr-un spațiu vectorial dă naștere in mod natural la un matroid: familiile independente sunt definite utilizând noțiunea uzuală de independență liniară. Iată in continuare câteva exemple combintoriale, mai puțin banale:

  • dacă G=(V,E) e un graf conex definesc un matroid M pe mulțimea muchiilor in felul următor: A\subset E e o mulțime independentă dacă nu induce niciun ciclu (matroizii obținuți in acest fel se numesc matroizi grafici).

In exemplul concret de mai jos (ciclul cu 4 vârfuri C_{4}) toate mulțimile de muchii (cu excepția mulțimii tuturor muchiilor) sunt mulțimi independente.

Evident, bazele unui matroid grafic sunt exact arborii parțiali („spanning treees”) in G.

  • dacă G=(B,F,E) e un graf bipartit (B= „băieți”, F= „fete”), atunci vom declara o mulțime de muchii „independentă” dacă niciun băiat nu este cuplat cu mai mult de o fată (s-ar putea să fie singur). Un matroid obținut in acest fel se numește matroid transversal)

in exemplul de mai sus (hotlinked fără rușine din tutorialul LEDA) muchiile roșii formează o mulțime independentă in matroidul transversal „de partea doamnelor”.

In desenul de mai sus universul matroidului are opt elemente. Fețele corespund la mulțimi dependente: de exemplu orice mulțime de trei elemente este independentă (neformând o față).

Matroidul Vámos este remarcabil prin următoarea proprietate: nu există o mulțime de opt vectori intr-un spațiu vectorial (peste orice corp am dori) astfel incât relația de independență liniară intre vectori să ne dea tocmai acest matroid (in limbaj tehnic: el nu este reprezentabil)

*

La ce sunt buni matroizii ? Lista este imensă așa incât mă voi limita la două-trei exemple:

In primul rând matroizii caracterizează (intr-un sens foarte precis) cazurile in care algoritmul greedy găsește o soluție optimă.

Ce inseamnă asta ? Dacă avem un matroid M in care fiecare element w\in U are un cost c_{W}\geq 0, problema bazei de cost minim in M cere să calculăm o bază B a lui M de cost total c(B)=\sum_{W\in B} c_{W} minim. Putem generaliza algoritmul lui Kruskal de la arbori parțiali (cu alte cuvinte matroizi grafici) la matroizi in general. Demonstrația optimalității se extinde la toți matroizii. Are insă, după cum am spus, și un soi de reciprocă: dacă oricare ar fi costurile c_{W} algoritmul greedy găsește soluția optimă atunci M este un matroid.

In al doilea rând poate vă mai amintiți de problema găsirii unei imperecheri (cuplaj) de cost minim intr-un graf bipartit (băieți-fete). Am vorbit recent despre ce se intâmplă când costurile sunt aleatoare uniform distribuite in [0,1]. Dar cum calculăm un cuplaj de cost minim ?

Algoritmul cel mai cunoscut se numește algoritmul ungar și a fost publicat de Harold Kuhn in 1955. Nu e chiar atât complicat  insă depășește cadrul unei popularizări de un minut 🙂 , așa incât nu il voi discuta aici. Amănunt istoric interesant pentru matematicieni, James Munkres (autorul celebrei cărți de topologie algebrică) a fost cel care a analizat complexitatea acetui algoritm.

Pe de altă parte un cuplaj intr-un graf bipartit nu e altceva decât o bază (comună) a doi matroizi (transversali) peste un univers comun: matroidul transversal „de partea băieților” (care exprimă faptul că niciun băiat nu e imperechiat cu mai mult de o fată) și matroidul transversal „de partea fetelor”.

Problema găsirii unui cuplaj de cost minim (și unii algoritmi care o rezolvă) se generalizează la problema găsirii unei baze comune in intersecția a doi matroizi M_{1},M_{2} peste același univers. Interesant, intersecția a trei sau mai mulți matroizi conduce la o problemă NP-completă, așadar la una care (probabil) nu are algoritmi eficienți.

In exemplele de mai sus conceptul de matroid permitea unificarea/generalizarea unor rezultate. Iată unul cu altă natură:

Să presupunem că vrem să impărțim un secret intre mai mulți participanți astfel incât numai anumite grupuri de participanți il pot reconstitui. De exemplu (varianta cea mai frecventă, numită in engleză threshold sharing) vrem ca orice grup de cel puțin k participanți să il poată reconstitui, dar grupurile formate din k-1 sau mai puțini participanți să n-o poată face. Un exemplu de astfel de schemă este cea a lui Adi Shamir, bazată pe faptul că k valori definesc complet un polinom de grad cel mult k-1, dar mai puțin de k valori lasă valoarea polinomului intr-un punct „secret” complet nedeterminată.

Ce se intâmplă când nu ne mulțumește faptul că orice grup de k participanți poate reconstrui secretul și vrem să controlăm mai bine structura grupurilor care (nu) au acces ?

Evident, grupurile care nu pot reconstrui secretul verifică prima axiomă a matroizilor: cu alte cuvinte dacă A\subseteq B și grupul B nu poate reconstrui secretul atunci nici A nu o poate face 🙂

Ito, Saito și Nishizeki au arătat că pentru orice familie de părți \mathcal{F}\subseteq \mathcal{P}(U) cu această proprietate există o schemă in care grupurile din \mathcal{F} sunt exact cele care nu au acces. Problema cu această schemă este că e extrem de ineficientă: pentru a „ascunde” k biți trebuie să distribuim un număr de biți care e (vorbind aproximativ) cel puțin 2^n\times k (unde n este numărul participanților). Cu alte cuvinte dependența de numărul participanților este exponențială !

Ce putem spune insă despre schemele ideale, cele in care spațiul in care trăiesc informațiile parțiale distribuite agenților nu are dimensiuni mai mare decât cel in care reprezentăm secretul ? Brickell și Davenport au arătat că mulțimea structurilor de acces „interzise” formează un matroid. Interesant, nu toți matroizii corespund unor structuri de acces in scheme perfecte: matroidul Vámos este un contraexemplu.

Mă opresc aici. Dacă doriți să aflați mai mult prima referință este capitolul din Cormen. Despre alte referințe (mai avansate) am mai vorbit.

Anunțuri
Acest articol a fost publicat în popularizarea_ştiinţei. Pune un semn de carte cu legătura permanentă.

Lasă un răspuns

Completează mai jos detaliile tale sau dă clic pe un icon pentru a te autentifica:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare / Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare / Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare / Schimbă )

Fotografie Google+

Comentezi folosind contul tău Google+. Dezautentificare / Schimbă )

Conectare la %s