Matroid

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Matroid to obiekt stanowiący uogólnienie przestrzeni liniowej wraz z istniejącym w niej pojęciem niezależności liniowej[potrzebne źródło]. Matroidy bada się głównie w takich działach matematyki, jak algebra, geometria czy matematyka dyskretna[potrzebne źródło]. Pojęcie to zostało wprowadzone w 1935 roku przez angielskiego matematyka Hasslera Whitneya[1].

Formalna definicja matroidu jest następująca[1]. Matroidem nazywamy parę (X, cl), gdzie X jest zbiorem skończonym, zaś cl funkcją odwzorowującą zbiór wszystkich podzbiorów zbioru X w siebie. Przy tym funkcja cl, którą nazywa się operatorem domknięcia, musi spełniać następujące warunki:

  • A zawiera się w cl(A)
  • cl(cl(A))=cl(A)
  • jeśli A zawiera się w B, to cl(A) zawiera się w cl(B)
  • jeśli b należy do cl(Aa), lecz nie należy do cl(A), to a należy do cl(Ab) (jest to tak zwany aksjomat wymiany Steinitza)

dla dowolnych podzbiorów A, B zbioru X oraz dowolnych elementów a, b zbioru X (przez Aa rozumiemy sumę zbiorów A i {a}).

Podzbiór A matroidu X nazywamy niezależnym, jeśli dla każdego elementu a ze zbioru A element a nie należy do zbioru cl(A\{a}) (czyli, mówiąc zwykłym językiem, element a jest niezależny od zbioru A\{a}). Natomiast A jest bazą matroidu X, jeśli A jest maksymalnym niezależnym podzbiorem X. Dzięki aksjomatowi wymiany można udowodnić, że w każdym matroidzie można znaleźć bazę (zazwyczaj więcej niż jedną).

Nietrudno sprawdzić, że jeśli X jest skończoną przestrzenią liniową, zaś cl operatorem liniowego domknięcia w X, to para (X, cl) spełnia wszystkie wyżej wymienione aksjomaty matroidu. Innym przykładem matroidu jest dowolne skończone ciało wraz z operatorem algebraicznego domknięcia. Rozważa się też matroidy nieskończone, stosując w stosunku do nich nazwę pregeometria.

Przypisy

Bibliografia[edytuj | edytuj kod]

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do algorytmów. WNT, 2007.