Matroid partycji

W matematyce matroid partycji lub matroid partycji to matroid , który jest bezpośrednią sumą jednolitych matroidów . Jest zdefiniowany na podstawie zestawu podstawowego, w którym elementy są podzielone na różne kategorie. Dla każdej kategorii istnieje ograniczenie pojemności - maksymalna dozwolona liczba elementów z tej kategorii. Niezależne zbiory macierzy podziału to dokładnie te zbiory, w których dla każdej kategorii liczba elementów z tej kategorii jest co najwyżej pojemnością kategorii.

Definicja formalna

Niech będzie zbiorem $rozłącznych$ zbiorów kategorii”). Niech ${\ displaystyle d_ {i}}$ będą liczbami całkowitymi z ${\ Displaystyle 0 \ równoważnik d_ {i} \ równoważnik | C_ {i} |}$ („pojemności”). Zdefiniuj podzbiór, $który ma$ dla każdego ${\ Displaystyle i}$ , ${\ Displaystyle | ja \ czapka C_ {i} | \ równoważnik d_ {i}}$ . Zbiory spełniające ten warunek tworzą niezależne zbiory matroidu , zwanego matroidem partycji .

Zbiory $nazywane$ kategoriami lub matroidu partycji .

Podstawą matroid partycji $}$ zbiór, którego przecięcie z każdym blokiem ma dokładnie rozmiar $d_ {i$ } . Obwód matroidu jest podzbiorem pojedynczego bloku $displaystyle$$C_ {i}$ do \ } Ranga matroidu to ${\ displaystyle \ suma d_ {i}$ } .

Każda jednolita $partycji$$jest$ matroidem blokiem $_$ _ ${\ displaystyle d_ {1} = r}$ . Każda matroid partycji jest bezpośrednią sumą zbioru jednolitych matroidów, po jednej dla każdego z jej bloków.

$.$ pojęcie matroidu partycji jest definiowane bardziej restrykcyjnie Podziały, które są zgodne z tą bardziej restrykcyjną definicją, to poprzeczne matroidy rodziny zbiorów rozłącznych określonych przez ich bloki.

Nieruchomości

Podobnie jak w przypadku jednolitych matroidów, z których są utworzone, podwójna matroida matroidu partycji jest również matroidem partycji, a każda podrzędna matroida partycji jest również matroidem partycji. Bezpośrednie sumy matroidów partycji są również matroidami partycji.

Dopasowanie

Maksymalne dopasowanie w grafie to zestaw krawędzi, który jest tak duży, jak to możliwe, pod warunkiem, że żadne dwie krawędzie nie mają wspólnego punktu końcowego. Na grafie dwudzielnym z dwupodziałem zestawy krawędzi spełniające warunek, że żadne dwie krawędzie nie mają wspólnego punktu końcowego w ${\ Displaystyle (U$ niezależnymi zestawami matroid partycji ( $, V )$ z jednym blokiem na wierzchołek w $iz$ z liczb ${\ displaystyle d_ {i}}$ równy jeden. Zbiory krawędzi spełniające warunek, że żadne dwie krawędzie nie mają wspólnego punktu końcowego w $niezależnymi$ zbiorami drugiej matroid partycji. Dlatego dwudzielny problem maksymalnego dopasowania można przedstawić jako przecięcie matroidów tych dwóch matroidów.

Mówiąc bardziej ogólnie, dopasowania grafu można przedstawić jako przecięcie dwóch matroidów wtedy i tylko wtedy, gdy każdy nieparzysty cykl na grafie jest trójkątem zawierającym dwa lub więcej wierzchołków stopnia drugiego.

Kompleksy kliki

Zespół kliki to rodzina zbiorów wierzchołków wykresu $}$ które indukują pełne podgrafy ${\ displaystyle G$ . Kompleks kliki tworzy matroid wtedy i tylko wtedy, gdy jest kompletnym grafem wieloczęściowym $iw$ tym przypadku wynikowa matroid jest matroidem partycji Kompleksy klik to dokładnie te systemy, które można utworzyć jako przecięcia rodzin matroidów podziału, dla których każde ${\ displaystyle d_ {i} = 1}$ .

Wyliczenie

Liczba odrębnych matroidów partycji, które można zdefiniować na zbiorze elementów oznaczonych $etykietą$ , dla ${\ Displaystyle n = 0,1,2, \ kropek}$ , wynosi n {\ displaystyle

1, 2, 5, 16, 62, 276, 1377, 7596, 45789, 298626, 2090910, ... (sekwencja A005387 w OEIS ).

Wykładnicza funkcja generująca tej sekwencji to ${\ Displaystyle f (x) = \ exp (e ^ {x} (x-1) +2x+1)}$ .