Matroidy

Zbiór wzorów, definicji i najczęściej poruszanych problemów ze Zbiór-ki.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11266
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3143 razy
Pomógł: 747 razy

Matroidy

Post autor: mol_ksiazkowy »

Matroidy


Teoria matroidów ma związki z macierzami, teorię grafów i kombinatoryką. Matroid może być zdefiniowany w języku algebry liniowej; gdzie bazy są to maksymalne zbiory niezależne; jako rodzina zbiorów niezależnych takich, że:
i) jeśli \(\displaystyle{ A}\) jest zbiorem niezależnym i \(\displaystyle{ B \subset A}\) to \(\displaystyle{ B}\) też jest zbiorem niezależnym
ii) jeśli \(\displaystyle{ A}\) i \(\displaystyle{ B}\) są zbiorami niezależnymi oraz \(\displaystyle{ B}\) ma więcej elementów niż \(\displaystyle{ A}\) to istnieje \(\displaystyle{ x \in B \backslash A}\) taki, że \(\displaystyle{ A \cup \{ x \}}\) jest zbiorem niezależnym.

Cykle - cykle są to minimalne zbiory, które nie są niezależne; istnieje możliwość zdefiniowania matroidu przez cykle:
i) żaden podzbiór cyklu nie jest cyklem
ii) Jeśli cykle mają wspólny element to istnieje cykl w nich zawarty i bez tego elementu.

Własność rozszerzania
Jesli \(\displaystyle{ X, Y}\) są niezależne i \(\displaystyle{ |X| < |Y|}\) to istnieje \(\displaystyle{ Z \subset Y \backslash X}\) taki, że \(\displaystyle{ |X \cup Z| = |Y|}\) oraz \(\displaystyle{ X \cup Z}\) jest zbiorem niezależnym

Wyróżnia się typy matroidów:
a) jednorodny jeśli wszystkie jego bazy są zbiorami \(\displaystyle{ k}\) elementowymi; a tj. zbiory niezależne mają nie więcej niż \(\displaystyle{ k}\) elementów
b) cykliczny tj. \(\displaystyle{ M(G) }\) dla jakiegoś grafu \(\displaystyle{ G }\) (bazami w \(\displaystyle{ M(G) }\) są acykliczne zbiory krawędzi \(\displaystyle{ G }\)).
c) grafowy tj. izomorficzny z \(\displaystyle{ M(G) }\) dla jakiegoś grafu \(\displaystyle{ G}\)
d) sprzężony grafowy tj. izomorficzny z \(\displaystyle{ M^{*}(G) }\) dla jakiegoś grafu \(\displaystyle{ G}\) (w \(\displaystyle{ M^{*}(G)}\) cyklami są przekroje grafu \(\displaystyle{ G }\) - tzw. matroid rozcięć)
e) transwersalny to taki, którego zbiory niezależne są transwersalami częściowymi jakiejś rodziny zbiorów \(\displaystyle{ S_1,..., S_m}\).
f) planarny to taki, który jest grafowy i sprzężony grafowy
g) matroid na zbiorze \(\displaystyle{ E }\) reprezentowalny nad ciałem \(\displaystyle{ K }\) to taki, dla którego istnieje przestrzeń wektorowa \(\displaystyle{ V}\) nad \(\displaystyle{ K}\) oraz odwzorowanie \(\displaystyle{ f: E \mapsto V}\) takie, że \(\displaystyle{ A \subset E}\) jest niezależny w \(\displaystyle{ M}\) jest równoważne temu, że \(\displaystyle{ f(A)}\) jest liniowo niezależny w \(\displaystyle{ V}\).
Matroid reprezentowalny nad ciałem \(\displaystyle{ Z_2}\) nazywa się binarnym. Matroidy regularne, to matroidy reprezentowane nad dowolnym ciałem. Istnieją matroidy niereprezentowalne nad żadnym ciałem.
h) wektorowy - jeśli \(\displaystyle{ E }\) jest przestrzenią wektorową, to jej podzbiory liniowo niezależne są też zbiorami niezależnymi matroidu na \(\displaystyle{ E }\).
i) algebraiczny - Jeśli \(\displaystyle{ F \subset K }\) (rozszerzenie ciała), to zbiór elementów \(\displaystyle{ \{ x_1,…,x_n \} }\) z \(\displaystyle{ K }\) jest algebraicznie zależny gdy \(\displaystyle{ f(x_1,…,x_n)=0 }\) dla jakiegoś wielomianu \(\displaystyle{ f }\) o współczynnikach z \(\displaystyle{ F }\). Gdy zbiór \(\displaystyle{ S \subset K }\) jest skończony, to wszystkie jego podzbiory, których elementy nie są algebraicznie zależne są matroidem na \(\displaystyle{ S}\).

Matroid dualny \(\displaystyle{ M^{*}}\), Ograniczenia, Ściągnięcia, Minory
Jeśli \(\displaystyle{ M }\) jest matroidem na zbiorze \(\displaystyle{ E}\), to \(\displaystyle{ M^{*}}\) jest matroidem, którego bazy są dopełnieniami baz matroidu \(\displaystyle{ M}\). Gdy \(\displaystyle{ A}\) jest podzbiorem \(\displaystyle{ M}\) to ograniczenie \(\displaystyle{ M}\) do \(\displaystyle{ A}\) to matroid o tych cyklach \(\displaystyle{ M}\), które są w \(\displaystyle{ A}\) (ozn. \(\displaystyle{ M \times A}\)). Ściągnięcie \(\displaystyle{ M}\) do \(\displaystyle{ A}\) (ozn. \(\displaystyle{ M \cdot A}\)) to matroid o cyklach: minimalnych elementach rodziny \(\displaystyle{ \{ C \cap A \}}\) gdzie \(\displaystyle{ C}\) jest cyklem \(\displaystyle{ M}\). Efektem wykonywania kolejnych operacji ograniczenia i ściągania jest minor matroidu \(\displaystyle{ M }\).

Uwagi
* W teorii matroidów istnieje sporo pojęć z teorii grafów (cykl, planarność, dualność, itd.)
* Własność rozszerzania jest uogólnieniem punktu ii) definicji matroidu
* izomorfizm matroidów to odwzorowanie bijektywne, które przeprowadza zbiory niezalażne na niezależne; np. matroidy na zbiorze \(\displaystyle{ E = \{ 1, 2 \}}\) tj. \(\displaystyle{ \{ \emptyset , \{ 1 \} \}}\) i \(\displaystyle{ \{ \emptyset , \{ 2 \} \}}\) są izomorficzne, ale \(\displaystyle{ \{ \emptyset , \{ 1 \} , \{ 2 \} \}}\) i \(\displaystyle{ \{ \emptyset , \{ 1 \} , \{ 2 \} , \{ 1, 2 \} \}}\) nie są.
* izomorfizm matroidów na ogół nie ma tych niezmienników co grafy (np. spójności)
* transwersala częściowa rodziny zbiorów \(\displaystyle{ S_1,...,S_m }\) to transwersala jakiejś podrodziny tych zbiorów; np.
\(\displaystyle{ \begin{cases}S_1 = \{ 1,2 \} \\ S_2= \{ 2, 3 \} \\ S_3=\{ 1, 3 \} \\ S_4= \{ 1, 2, 3 \} \end{cases}}\)
nie ma transwersali ale ma ją podrodzina \(\displaystyle{ S_1, S_2, S_3 }\) itp.
* przekrój grafu spójnego to taki zbiór krawędzi, po usunięciu których, graf nie jest spójny
* Jeśli \(\displaystyle{ M(G_1) }\) i \(\displaystyle{ M(G_2) }\) są izomorficzne, to \(\displaystyle{ G_1 }\) i \(\displaystyle{ G_2 }\) nie muszą być izomorficzne
* matroid rozcięć jest dualny do matroidu cyklicznego, tj. \(\displaystyle{ M^{*}(G)= M(G)^{*}}\)

********************************************************************* *
Przykład
Matroid, którego bazami są wszystkie dwuelementowe podzbiory \(\displaystyle{ \{ 1,...,6 \}}\) za wyjątkiem \(\displaystyle{ \{ 1, 2 \}}\), \(\displaystyle{ \{ 3, 4 \}}\), \(\displaystyle{ \{ 5, 6 \}}\) nie jest transwersalny.
Matroid o bazach \(\displaystyle{ \{ 1, 2, 4 \}, \{ 1, 3, 4 \}, \{ 1, 4, 5 \}}\) jest transwersalny, gdyż można określić
\(\displaystyle{ \begin{cases}S_1 = \{ 1 \} \\ S_2= \{ 2, 3, 5 \} \\ S_3=\{ 1, 4 \} \end{cases}}\)


Przykład
Matroid \(\displaystyle{ M(K_3) }\) jest jednorodny, ale \(\displaystyle{ M(K_4) }\) nie jest jednorodny.


Przykład
Matroid grafowy jest binarny. Matroid jednorodny na zbiorze czteroelementowym i o bazach \(\displaystyle{ 2}\) elementowych nie jest binarny, a jednak reprezentowalny nad \(\displaystyle{ Z_3}\). Matroidy jednorode są transwersalne.


Przykład
Matroidy \(\displaystyle{ M(K_5)}\) i \(\displaystyle{ M(K_{3,3})}\) nie są planarne.


Przykład
W matroidzie jednorodnym, w którym bazy są \(\displaystyle{ k }\) elementowe, cykle są zbiorami \(\displaystyle{ k+1}\) elementowymi.


Przykład
Regularność, grafowość, binarność są cechami dziedzicznymi dla minorów


Przykład
Jeśli dana jest macierz, to można skonstruować matroid, w którym zbiorami niezależnymi są numery tych kolumn, które są zbiorami liniowo niezależnymi; np. gdy
\(\displaystyle{ \left[\begin{array}{ccc}0&1&0\\1&0&1\\1&1&1\end{array}\right]}\)
to zbiór \(\displaystyle{ \{1,2 \} }\) jest elementem matroidu, gdyż wektory \(\displaystyle{ (0,1,1) }\) i \(\displaystyle{ (1,0,1) }\) są liniowo niezależne.


Przykład
Matroid Fano jest określony na zbiorze \(\displaystyle{ E = \{ 1,..., 7 \}}\) i jego bazami są wszystkie trzyelementowe podzbiory \(\displaystyle{ E}\) za wyjątkiem siedmiu, które odpowiadają trójkom punktów współliniowych; jak na rys. Matroid Fano \(\displaystyle{ F_7}\) jest binarny i nieregularny; nie jest grafowy ani sprzężony grafowy. Jest też eulerowski (tj. jest sumą rozłącznych cykli)
Ukryta treść:    
źródła: Oxley; Welsh; Wilson, Maclane, Mirsky, Hillman
ODPOWIEDZ