Matroid

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

Formalna definicja matroidu jest następująca. 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.

Bibliografia

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