Matroid

Obecnie Matroid stał się tematem zainteresowania wielu osób z różnych dziedzin. Wraz z postępem technologii i dostępem do informacji, Matroid stał się istotny w dzisiejszym społeczeństwie. Czy to ze względu na wpływ na gospodarkę, wpływ na kulturę popularną, czy też znaczenie w życiu codziennym, Matroid to temat, który nie pozostaje niezauważony. W tym artykule zbadamy różne aspekty związane z Matroid i przeanalizujemy jego wpływ na dzisiejszy świat.

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

  1. a b James Oxley, What is a matroid?
  2. a b Cormen i in. 2012 ↓, s. 443.
  3. Cormen i in. 2012 ↓, s. 444.

Bibliografia

Linki zewnętrzne