Matroid
Przejdź do nawigacji
Przejdź do wyszukiwania
Matroid – struktura stosowana w kombinatoryce. Pojęcie to zostało wprowadzone w 1935 roku przez angielskiego matematyka Hasslera Whitneya[1].
Formalna definicja matroidu jest następująca. Matroidem nazywamy parę która musi spełniać następujące warunki[2]:
- jest zbiorem skończonym,
- jest taką niepustą rodziną podzbiorów że jeśli oraz to (zbiór pusty zawsze należy do ),
- jeśli i należą do oraz to istnieje taki element że (jest to własność wymiany).
Podzbiór należący do nazywamy podzbiorem niezależnym[2]. jest bazą matroidu, jeśli jest maksymalnym podzbiorem niezależnym (nie zawiera się w żadnym innym podzbiorze niezależnym). W każdym matroidzie można znaleźć bazę (zazwyczaj więcej niż jedną)[1][3].
Przypisy[edytuj | edytuj kod]
- ↑ a b James Oxley , What is a matroid?
- ↑ a b Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein ↓, s. 443.
- ↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein ↓, s. 444.
Bibliografia[edytuj | edytuj kod]
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do algorytmów. Wyd. VII. Wydawnictwo Naukowe PWN, 2012. ISBN 978-83-01-16911-4.