Matroid – struktura stosowana w kombinatoryce. Pojęcie to zostało wprowadzone w 1935 roku przez angielskiego matematyka Hasslera Whitneya.
Formalna definicja matroidu jest następująca. Matroidem nazywamy parę która musi spełniać następujące warunki: 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. 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ą).
Przypisy
Bibliografia
Linki zewnętrzne Ilustracja przedstawiająca przykład matroidu grafowego
Kategoria:Algebra liniowa Kategoria:Kombinatoryka Kategoria:Geometria