Matroid

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

În matematică și în special în combinatorică , termenul matroid este aplicat structurilor care ne permit să abordăm o noțiune de „independență” care generalizează independența liniară a spațiilor vectoriale . De fapt, termenul de structură de independență a fost folosit și pentru unele dintre aceste structuri. Aceste structuri privesc, direct sau indirect, colecțiile de subseturi ale unui set de mediu dat care posedă proprietăți particulare.

Matroidele pot fi definite într-o varietate surprinzător de largă de moduri, fiecare corespunzând unui tip de entitate (seturi independente, seturi dependente, baze, seturi închise sau plane, operator de închidere, circuite (seturi dependente minime), funcție de rang, hiperplane, rețele geometrice ). Dorind să fie formal mai precise, sunt identificate o duzină de specii de structuri care sunt criptomorfe ; în plus, fiecare dintre aceste tipuri de structuri poate fi definit folosind numeroase sisteme de axiome. Acest lucru sugerează că multe concepte de o importanță considerabilă converg în teoria matroidelor.

De asemenea, trebuie remarcat imediat că există numeroase și variate exemple de matroizi. Prin urmare, teoria matroidelor ne permite să încadrăm într-un mod unitar o varietate foarte mare de fapte matematice. De fapt, dezvoltarea sa a contribuit foarte mult la conferirea organicității combinatoricii și la transformarea ei într-un domeniu solid al matematicii. În cele din urmă, trebuie remarcat faptul că are legături cu numeroase domenii ale matematicii, atât „pure”, cât și „aplicate” (algebră, geometrie, optimizare, cercetare operațională, teorie și practică a algoritmilor) și, de asemenea, cu discipline mai aplicative, cum ar fi ingineria structurală și chimie moleculară.

În acest articol principal introducem matroidele în două moduri, bazate respectiv pe noțiunile de set independent și operator de închidere. Acestea sunt două definiții relativ simple și capabile să ofere dovezi bune unor tipuri de entități care caracterizează matroidele.

Matroid al independenților

Un matroid de independenți este definit ca o pereche M = ( E , I ), un sistem de independență , în care E este un set numit mediu sau set de suport al matroidului și I este o colecție de subseturi de E numite seturi independente de M , care îndeplinesc următoarele proprietăți:

  1. Setul gol este independent.
  2. Fiecare subset al unui independent este independent; cu alte cuvinte, I este o colecție închisă cu privire la incluziune; această proprietate se numește uneori moștenire de independență .
  3. Dacă A și B sunt două mulțimi independente și A are mai multe elemente decât B , atunci există un element în A, dar nu în B astfel încât adăugat la B duce la un alt set independent; această proprietate se numește proprietatea de schimb .

Dacă mediul este finit, cererile anterioare sunt suficiente pentru definiție, dar dacă este infinit, sunt necesare alte condiții destul de complexe; aici nu abordăm aceste probleme, ci ne limităm la menționarea proprietății care caracterizează un matroid finit :

  • Un subset infinit al lui E este independent dacă fiecare dintre subsetul său finit este independent; această proprietate se numește caracter finit .

Un matroid se spune că este dimensional finit sau finit dacă există un număr natural astfel încât să nu existe un set independent cu cardinalitate mai mare decât acesta.

Primele două proprietăți necesare pentru matroizi independenți sunt foarte simple, dar motivația pentru a treia proprietate nu este atât de evidentă. Aceasta implică faptul că, având în vedere două seturi independente de aceeași cardinalitate, fiecare element al unuia dintre cele două poate fi înlocuit cu un element al celuilalt pentru a obține un alt set independent: această consecință justifică termenul „schimb”. Pentru a clarifica mai bine semnificația celei de-a treia axiome, este potrivit să examinăm câteva exemple semnificative.

Acum continuăm să definim unele obiecte cu proprietăți specifice într-un matroid independent M = ( E , I ).
Un subset maxim independent este numit baza lui M. Un subset de E care nu este independent se numește dependent . Un subset minim dependent este numit circuit .
De asemenea, este definit ca operatorul de închidere al unui matroid finit ca funcție de tip cl: P ( E ) & mapsto: P ( E ) M care, aplicat unui subset generic A de E , îl extinde prin adăugarea tuturor elementelor x în E dar nu în A astfel încât există un circuit C al lui M care conține x și este conținut în uniunea lui A și { x }. Este ușor de văzut că această funcție este într-adevăr o funcție de închidere , adică este o funcție endoolonică booleană în expansiune , monotonă și idempotentă .

Închidere matroidă

Acum definim matroidele prin intermediul unui operator de închidere, adică luând în considerare un set de mediu și o funcție de închidere care are proprietăți particulare.

Definim ca matroid de închidere o pereche ( E , cl) unde E este un set finit și cl o funcție de tipul P ( E ) ^ mapsto; P ( E ) care îndeplinește următoarele condiții, pentru elementele arbitrare a , b din E și pentru subseturile arbitrare Y , Z din E :

  1. cl este un operator de închidere pe E.
  2. se bucură de proprietatea de schimb a lui Mac Lane-Steinitz : dacă a aparține lui cl ( ) \ cl (Y), atunci b aparține lui cl ( ).
  3. Dacă E este infinit, se adaugă cererea pentru caracter finit : dacă a este în cl ( Y ), atunci există un subset finit X al lui Y astfel încât a să fie în cl ( X ).

Se arată că un matroid de închidere este logic echivalent cu un matroid independent finit al cărui operator de închidere definit pe seturile independente coincide cu operatorul de închidere introdus cu definiția.

În acest moment știm că atunci când avem de-a face cu un matroid, se poate alege dacă îl definim prin specificarea operatorului său de închidere sau prin intermediul seturilor sale independente; această a doua posibilitate este deseori de dorit, mai ales în aplicații de natură geometrică.

Observăm că, dimpotrivă, operatorul de închidere al unui spațiu topologic tinde să nu aibă proprietatea de schimb (2), în timp ce are o proprietate caracteristică diferită.

Exemple

  • Se spune că un matroid este simplu dacă fiecare dintre subseturile sale din două elemente este independentă.
  • Fie E o mulțime și k un număr natural . Subseturile lui E cu cel mult k elemente constituie seturile independente ale unui matroid pe E. Am demonstrat că proprietățile seturilor independente sunt valabile.
    • Pentru orice alegere a întregului natural k setul gol nu are mai mult de k elemente;
    • Fiecare subset al unui set cu cel mult k elemente conține nu mai mult de k elemente;
    • Dacă un subset A are cardinalitate mai mare decât cea a lui B , atunci A trebuie să conțină un element x care nu este conținut în B. Deoarece B are cardinalitate cel mult k - 1, adăugarea x la B menține independența.
  • Dacă E este un subset finit arbitrar al unui spațiu vectorial V , atunci putem defini un M matroid pe E luând colecțiile de vectori liniar independenți din E ca seturi independente. Vedem că proprietățile matroidelor independente sunt adevărate.
    • Setul gol este vacuu un set de vectori liniar independenți.
    • Un subset al unui set de vectori liniar independenți nu poate avea o dependență liniară.
    • Schimb de proprietate. dacă A și B sunt seturi de vectori liniar independenți, subtend subspaiile lui V având dimensiuni | respectiv A | și | B |. Dacă fiecare vector din A depinde liniar de vectorii din B , atunci fiecare vector din A aparține subspaiului | B | -dimensional generat de vectorii din B. Prin urmare, vectorii lui A generează cel mult un spațiu de dimensiune | B |, ceea ce implică | A | ≤ | B |. Observați că fiecare set de vectori ai unui spațiu vectorial constituie un matroid finit și că este finit-dimensional dacă spațiul vectorial are dimensiuni finite.
  • Să luăm în considerare o matrice A cu intrări într-un câmp , setul coloanelor sale C și colecția D a seturilor de coloane care constituie seturi de vectori liniar dependenți. Structura M : = ( C , D ) este un matroid numit matroid al coloanelor lui A ; la rândul său , A se spune să reprezinte M. Matroidele de coloană sunt reprezentări ale matroidelor vectoriale, sunt total echivalente cu ele și pot fi utile pentru calculele efective.
  • Într-o geometrie proiectivă alegem un set arbitrar E de puncte și îl dotăm cu funcția de închidere constituită de închiderea proiectivă limitată la E. În acest fel se obține un matroid. Ca un caz particular, putem lua pentru E un subset al unei geometrii afine și chiar mai ales un subset al unui spațiu euclidian.
  • Într-un spațiu vectorial sau într-o geometrie proiecțională considerăm o aranjare arbitrară a hiperplanelor H , adică un set finit de sub spații de codimensiune 1. Spunem independentă o colecție J de hiperplanuri de H astfel încât intersecția membrilor săi să aibă codimensiune | J |, adică egal cu numărul de hiperplane din J. Apoi notăm cu I setul de colecții independente. Structura ( H , I ) constituie un matroid. Funcția de închidere a acestui matroid extinde o colecție A de hiperplane cu toate hiperplanele care conțin intersecția hiperplanelor din A. Aceste matroide sunt liniar sau proiectiv duale față de cele observate în exemplele anterioare referitoare la vectori și, respectiv, la punctele proiective.
  • Acum derivăm un matroid dintr-un multigraf finit arbitrar G = ( V , E ) (sau mai precis dintr-un grafic finit). Spunem independente fiecare set de margini care nu conține niciun ciclu; în teoria graficelor un astfel de set de margini constituie o așa-numită pădure . Dacă notăm cu I colecția acestor seturi de margini, ( E , I ) formează un matroid independent care se numește ciclu matroid sau grafic matroid . Proprietățile matroidelor sunt garantate de următoarele fapte:
    • Setul gol nu permite obținerea unei bucle.
    • Prin eliminarea muchiilor dintr-un set independent, nu se pot obține cicluri.
    • Să luăm în considerare bazele matroidului, adică subpădurile lui G care conțin toate vârfurile graficului și amintim că un nod izolat trebuie considerat un copac. O pădure cu k este uniunea | V | - k copaci. Deci, o pădure cu mai multe margini are mai puțini copaci decât o pădure cu câteva margini. Dar unii copaci din pădurea mai mare trebuie să conțină două vârfuri de doi copaci diferiți (și deconectați) în pădurea mai mică. Deoarece cele două vârfuri fac parte din copacul din cea mai mare pădure, în această pădure există o singură cale care unește cele două vârfuri. Această cale trebuie să conțină o margine care nu face parte din nici unul dintre cei doi copaci din pădurea mai mică; aceasta este marginea care poate fi adăugată pădurii mai mici.

Observați că în acest fel un matroid este obținut și dintr-un multigraf infinit; un astfel de matroid este finit deoarece toate ciclurile sunt finite; în plus, este finit-dimensional dacă numărul vârfurilor este finit, chiar dacă numărul muchiilor este infinit).

Două tricolore maxime cu un număr diferit de noduri. Cel din stânga nu poate fi extins deoarece singurul vârf rămas este adiacent nodurilor de toate cele trei culori.

În schimb, ia în considerare o situație care nu duce la un matroid. Fie E setul de noduri ale unui grafic și numim seturi de noduri independente acelea care pot fi colorate cu cel mult trei culori fără coincidențe între nodurile adiacente. Setul gol îndeplinește condiția și fiecare subset de noduri tricolore este tricolor; pe de altă parte, proprietatea de schimb nu este validă, deoarece este posibil să aveți două subgrafe tricolore maxime cu un număr diferit de noduri, așa cum se arată în figura din dreapta.

Definiții și proprietăți suplimentare

Ne referim la un matroid al independenților ( E , I ). Se spune că un subset de E este dependent dacă nu este independent. Un set minim dependent, adică astfel încât fiecare dintre subsetul său propriu este independent, se numește circuit (acest termen provine din exemplul anterior al matroidului grafic).

Spunem că un subset A din E generează ( se întinde ) M dacă închiderea sa este întregul E.

O mulțime independentă maximă, adică care nu este conținută în mod corespunzător în nicio altă mulțime independentă, se numește bază (acest termen provine din exemplul anterior despre spațiul vectorial). Un fapt important este că toate bazele unui matroid au același număr de elemente; acest număr se numește rangul lui M. În general, însă, circuitele lui M pot avea cardinalitate diferită.

În exemplul de mai sus al algebrei liniare matroide, o bază este, de asemenea, o bază în sensul algebrei liniare a subspațiului generat de E, iar un circuit este un set minim de vectori dependenți ai lui E. În matroidul ciclurilor, o bază corespunde unei subpăduri maxime a graficului G, iar circuitele sunt cicluri simple ale graficului. În exemplul în care seturile de cel mult k elemente sunt independente, baza este orice subset de E cu k elemente și circuitează orice subset de k + 1 elemente.

Dacă A este un subset al lui E , atunci putem defini un matroid al independenților de pe A presupunând ca seturi independente ale acestuia subseturile independente din M care sunt conținute în A. Acest lucru ne permite să vorbim despre subomatroizi și să atribuim un rang fiecărui subset de E.

Dacă M = ( E , I ) este un matroid finit și B denotă colecția bazelor sale, adică a seturilor sale maxime independente, se numește matroid dual al lui M și notat cu M *, matroidul care are ca mediu setați E-ul însuși și, ca o colecție de baze, colecția de subseturi care sunt complementare unor baze din B. Un subset de E este independent în M * dacă și numai dacă este inclus în complementul unei baze de M , sau echivalent dacă și numai dacă complementul său generează M. Se verifică cu ușurință că M * este într-adevăr un matroid.

De asemenea, sunt propuse dualitățile matroidelor infinite, dar definițiile lor întâmpină dificultăți, iar problema dualității dintre aceste matroide nu a fost încă rezolvată în mod satisfăcător.

Alte exemple

La scurt timp după articolul fondator al lui Witney, sa descoperit că independența algebrică este o independență matroidă. Să luăm în considerare un câmp K și câmpul său de extensie L. Se spune că un subset finit x 1 , ..., x k al lui L este independent algebric dacă nu există polinom diferit de zero f ( t 1 , ..., t k ), cu coeficienți în K , astfel încât f ( x 1 , ..., x k ) = 0. Cuplul constituit de setul de mediu L și de independența algebrică este un matroid finitar care se numește matroid algebric plin de mediu L pe K. Rangul acestui matroid este egal cu gradul de transcendență al lui L peste K. Apoi, spune algebrică matroidă, fiecare sottomatroidă a unui matroid algebric plin.

Mai târziu s-a constatat că teoria transversalelor oferă un alt gen de matroid numit matroid transvers .

Bibliografie

Vezi și în Istoria Matroidelor

Elemente conexe

linkuri externe

Controlul autorității LCCN ( EN ) sh85082228
Matematica Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică