Matroid dwudzielny
W matematyce dwudzielna matroid jest matroidem , którego wszystkie obwody mają parzysty rozmiar.
Przykład
Jednolita matroida i tylko wtedy, gdy ponieważ obwody w takiej matroidzie mają rozmiar .
Związek z grafami dwudzielnymi
Matroidy dwudzielne zostały zdefiniowane przez Welsha (1969) jako uogólnienie grafów dwudzielnych , grafów, w których każdy cykl ma parzystą wielkość. Matroid graficzny jest dwudzielny wtedy i tylko wtedy, gdy pochodzi z grafu dwudzielnego.
Dualność z matroidami Eulera
Graf Eulera to taki, w którym wszystkie wierzchołki mają parzysty stopień; Grafy Eulera można rozłączyć. W przypadku grafów planarnych właściwości bycia dwudzielnym i eulerowskim są podwójne: graf planarny jest dwudzielny wtedy i tylko wtedy, gdy jego podwójny graf jest eulerowski. Jak pokazał Welsh, ta dwoistość rozciąga się na binarne matroidy : binarna matroida jest dwudzielna wtedy i tylko wtedy, gdy jej podwójna matroida jest matroidem Eulera , matroidem, który można podzielić na rozłączne obwody.
W przypadku matroidów, które nie są binarne, dwoistość między matroidami eulerowskimi i dwudzielnymi może się załamać. Na przykład jednolity matroid nie jest dwudzielny, ale jego podwójny { Eulera, ponieważ można go podzielić na dwa 3-cykle. Samopodwójny jednolity matroid nie eulerowski
Złożoność obliczeniowa
czasie wielomianowym można sprawdzić, czy dana matroida binarna jest dwudzielna. Jednak każdy algorytm, który sprawdza, czy dana matroida jest eulerowska, mając dostęp do matroidu za pośrednictwem niezależnej wyroczni , musi wykonać wykładniczą liczbę zapytań wyroczni, a zatem nie może zająć czasu wielomianowego.