Bipartitní matroid - Bipartite matroid

V matematice, a bipartitní matroid je matroid všechny jejichž obvody mají dokonce velikost.

Příklad

A jednotný matroid ${ displaystyle U {} _ {n} ^ {r}}$ je bipartitní právě tehdy ${ displaystyle r}$ je liché číslo, protože obvody v takovém matroidu mají velikost ${ displaystyle r + 1}$.

Vztah k bipartitním grafům

Bipartitní matroidy byly definovány pomocí Velština (1969) jako zobecnění bipartitní grafy, grafy, ve kterých má každý cyklus sudou velikost. A grafický matroid je bipartitní právě tehdy, pokud pochází z bipartitního grafu.^[1]

Dualita s euleriánskými matroidy

An Euleriánský graf je ten, ve kterém mají všechny vrcholy sudý stupeň; Euleriánské grafy mohou být odpojeny. Pro rovinné grafy, vlastnosti bytí bipartitní a euleriánské jsou dvojí: rovinný graf je bipartitní právě tehdy, když jeho duální graf je Eulerian. Jak ukázal Welsh, tato dualita se rozšiřuje na binární matroidy: binární matroid je bipartitní, právě když je jeho duální matroid je Eulerianský matroid, matroid, který lze rozdělit do disjunktních obvodů.

U matroidů, které nejsou binární, se dualita mezi euleriánskými a bipartitními matroidy může rozpadnout. Například uniformní matroid ${ displaystyle U {} _ {6} ^ {4}}$ je nebipartitní, ale je dvojí ${ displaystyle U {} _ {6} ^ {2}}$ je Eulerian, protože jej lze rozdělit do dvou 3 cyklů. Self-dual uniformní matroid ${ displaystyle U {} _ {6} ^ {3}}$ je bipartitní, ale ne Eulerian.

Výpočetní složitost

Je možné otestovat v polynomiální čas zda je daný binární matroid bipartitní.^[2] Jakýkoli algoritmus, který testuje, zda je daný matroid Eulerian, má přístup k matroidu prostřednictvím věštba nezávislosti, musí provést exponenciální počet věšteckých dotazů, a proto nemůže trvat polynomiální čas.^[3]

Reference