Matroid
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
- ↑ a b JamesJ. Oxley JamesJ., What is a matroid? [online]
- ↑ a b Cormen i in. 2012 ↓, s. 443.
- ↑ Cormen i in. 2012 ↓, s. 444.
Bibliografia
- Thomas H.T.H. Cormen Thomas H.T.H. i inni, Wprowadzenie do algorytmów, wyd. VII, Wydawnictwo Naukowe PWN, 2012, ISBN 978-83-01-16911-4 .
Linki zewnętrzne
- Ilustracja przedstawiająca przykład matroidu grafowego
Kontrola autorytatywna (independence system):
- LCCN: sh85082228
- J9U: 987007557991105171
Encyklopedie internetowe:
- Treccani: matroide