Matroid dwukołowy - Bicircular matroid

W matematycznej przedmiotu matroid Teoretycznie bicircular matroid z wykresu G jest matroid B ( G ), którego punkty krawędzie G i którego niezależne zestawy są zestawy krawędziowe pseudoforests z G , to znaczy, że zestawy meblowe, w którym każdy połączony komponent zawiera co najwyżej jeden cykl .

Matroid dwukołowy został wprowadzony przez Simões-Pereira (1972) i dalej badany przez Matthewsa (1977) i innych. Jest to szczególny przypadek matroid ramki z tendencyjnego wykresie .

Obwody

Obwody lub minimalne zbiory zależne tego matroidu to dwukołowe grafy (lub rowery , ale termin ten ma inne znaczenie w teorii grafów); są to połączone wykresy, których ranga obwodu wynosi dokładnie dwa.

Istnieją trzy różne typy wykresów dwukołowych:

• Wykres teta składa się z trzech ścieżek łączących te same dwa wierzchołki ale nie przecinające się ze sobą.
• Wykres ósemkowy (lub ciasna kajdanka) składa się z dwóch cykli mających tylko jeden wspólny wierzchołek.
• Luźna kajdanka (lub sztanga) składa się z dwóch rozłącznych cykli i minimalnej ścieżki łączącej.

Wszystkie te definicje mają zastosowanie do multigrafów , tj. dopuszczają wiele krawędzi (krawędzi mających te same punkty końcowe) i pętli (krawędzi, których dwa punkty końcowe są tym samym wierzchołkiem).

Mieszkania

Te i zamkniętej (spłaszczenie) z bicircular matroid grafu G można określić jak lasy F z G , tak że w indukowanej podgrafu o V ( G ) - V ( F ) , każdy połączony składnik ma cykl. Ponieważ spłaszczenia matroidu tworzą sieć geometryczną, gdy są częściowo uporządkowane przez włączenie zbioru, te lasy G również tworzą sieć geometryczną. W częściowym uporządkowaniu dla tej sieci, że F ₁ ≤ F ₂ jeśli

• każde drzewo składowe F ₁ jest albo zawarte w każdym drzewie F ₂ albo wierzchołkowo rozłączne z każdym drzewem F ₂ , a
• każdy wierzchołek F ₂ jest wierzchołkiem F ₁ .

Do najbardziej interesujących Załóżmy, G  ^O być G z pętlą dodawana do każdego wierzchołka. Wtedy mieszkania B ( G  ^o ) to wszystkie lasy G , rozciągające się lub nieobejmujące. Tak więc, wszystkie lasy grafu G tworzą geometryczny siatki, tym siatki lasów z G ( Zaslavsky 1982 ).

Jako poprzeczne matroidy

Matroidy dwukołowe można scharakteryzować jako matroidy poprzeczne, które powstają z rodziny zestawów, w których każdy element zestawu należy do co najwyżej dwóch zestawów. Oznacza to, że niezależne zbiory matroidu są podzbiorami elementów, które można wykorzystać do utworzenia systemu odrębnych przedstawicieli dla niektórych lub wszystkich zbiorów. W tym opisie elementy odpowiadają krawędziom grafu i istnieje jeden zestaw na wierzchołek, zestaw krawędzi mający ten wierzchołek jako punkt końcowy.

Małoletni

W przeciwieństwie do matroidów poprzecznych w ogóle, matroidy dwukołowe tworzą klasę zamkniętą drugorzędną ; oznacza to, że każda submatroid lub skurcz dwukołowej matroidy jest również matroidem dwukołowym, jak widać z ich opisu w kategoriach krzywych stronniczych ( Zaslavsky 1991 ). Oto opis usuwania i skracania krawędzi w odniesieniu do grafu bazowego: Aby usunąć krawędź z matroidu, usuń ją z grafu. Zasada skurczu zależy od rodzaju krawędzi. Aby skontraktować łącze (nie pętlę) w matroidzie, skontraktuj je na wykresie w zwykły sposób. Aby skrócić pętlę e w wierzchołku v , usuń e i v , ale nie inne krawędzie występujące z v; raczej każda krawędź wypadająca z v i innym wierzchołkiem w staje się pętlą w w . Wszelkie inne pętle grafu w punkcie v stają się pętlami matroid — aby poprawnie opisać to w kategoriach grafu, potrzebne są półkrawędzie i luźne krawędzie; zobacz obciążony wykres małoletni .

Wielomian charakterystyczny

Wielomian charakterystyczny z bicircular matroid B ( G  ^O ) wyraża w prosty sposób liczba obejmujące lasy (lasy, które zawierają wszystkie wierzchołki G ) każdej wielkości w G . Formuła to

${\ Displaystyle p_ {B (G)} (\ lambda): = \ suma _ {k = 0} ^ {n} (-1) ^ {k} f_ {k} (\ lambda -1) ^ {nk} ,}$

gdzie f _k jest równe liczbie lasów o krawędzi k w G . Zobacz Zasławski (1982) .

Reprezentacja wektorowa

Matroidy dwukołowe, podobnie jak wszystkie inne matroidy poprzeczne, mogą być reprezentowane przez wektory na dowolnym polu nieskończonym . Jednak w przeciwieństwie do matroidów graficznych , nie są one regularne : nie mogą być reprezentowane przez wektory na dowolnym polu skończonym . Pytanie o pola, nad którymi dwukołowy matroid ma reprezentację wektorową, prowadzi do w dużej mierze nierozwiązanego problemu znalezienia pól, nad którymi graf ma przyrosty multiplikatywne . Zobacz Zasławski (2007) .

Bibliografia

• Matthews, Laurence R. (1977), "Bicircular Matroids", Quarterly Journal of Mathematics , druga seria, 28 (110): 213-227, doi : 10.1093/qmath/28.2.213 , MR  0505702.
• Simões-Pereira, JMS (1972), "Na podgrafach jako komórki matroidalne", Mathematische Zeitschrift , 127 : 315-322, doi : 10.1007/BF01111390 , MR  0317973.
• Zaslavsky, Thomas (1982), "geometria dwukołowa i krata lasów wykresu", Quarterly Journal of Mathematics , druga seria, 33 (132): 493-511, doi : 10.1093/qmath/33.4.493 , MR  0679818.
• Zaslavsky, Thomas (1991), "Wykresy stronnicze. II. Trzy matroidy", Journal of Combinatorial Theory , Seria B, 51 (1): 46-72, doi : 10.1016/0095-8956(91)90005-5 , MR  1088626.
• Zaslavsky, Thomas (2007), "Wykresy stronnicze. VII. Kontrawaga i antynapięcia", Journal of Combinatorial Theory , Series B, 97 (6): 1019-1040, doi : 10.1016/j.jctb.2007.03.001 , MR  2354716.