Matroid
 |
Ten artykuł od 2014-06 wymaga uzupełnienia źródeł podanych informacji. Możliwe, że ten artykuł w całości albo w części zawiera informacje nieprawdziwe. Informacje bez źródeł w każdej chwili mogą zostać zakwestionowane i usunięte. Pomóż Wikipedii i dodaj przypisy do materiałów opublikowanych w wiarygodnych źródłach. Po wyeliminowaniu niedoskonałości prosimy usunąć szablon {{Dopracować}} z kodu tego artykułu. |
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.
