Základ matroidu - Basis of a matroid

V matematice, a základ a matroid je maximální nezávislá množina matroidu - tj. nezávislá množina, která není obsažena v žádné jiné nezávislé množině.

Příklady

Jako příklad zvažte matroid nad základnou R² (vektory v dvourozměrné euklidovské rovině), s následujícími nezávislými množinami:

{ {}, {(0,1)}, {(2,0)}, {(0,1),(2,0)}, {(0,3)}, {(0,3),(2,0)} }.

Má dvě základny, což jsou množiny {(0,1), (2,0)}, {(0,3), (2,0)}. Toto jsou jediné nezávislé množiny, které jsou při zařazení maximální.

Základ má specializovaný název pro několik specializovaných druhů matroidů:^[1]

• V grafický matroid, kde nezávislými množinami jsou lesy, základnám se říká překlenující lesy grafu.
• V příčný matroid, kde jsou nezávislé množiny koncovými body párování v daném bipartitním grafu, jsou volány báze příčné.
• V lineární matroid, kde jsou nezávislé množiny lineárně nezávislý množiny vektorů v daném vektorovém prostoru, právě se nazývají báze základny vektorového prostoru. Pojem základny matroidu tedy zobecňuje pojem základ z lineární algebry.
• V jednotný matroid, kde nezávislé množiny jsou všechny množiny s mohutností nanejvýš k (pro celé číslo k), základy jsou všechny sady s mohutností přesně k.
• V dělící matroid, kde jsou prvky rozděleny do kategorií a nezávislé sady jsou všechny sady obsahující maximálně k_C prvky z každé kategorie C, základy jsou všechny sady, které obsahují přesně k_C prvky z kategorie C.
• V zdarma matroid, kde jsou všechny podmnožiny základny E jsou nezávislé, jedinečný základ je E.

Vlastnosti

Výměna

Všechny matroidy splňují následující vlastnosti pro libovolné dva odlišné základy ${ displaystyle A}$ a ${ displaystyle B}$:^[2]

• Výměnný majetek: pokud ${ displaystyle a v A setminus B}$, pak existuje prvek ${ displaystyle b in B setminus A}$ takhle ${ displaystyle (A setminus {a }) pohár {b }}$ je základ.
• Symetrická vlastnost směny bází: pokud ${ displaystyle a v A setminus B}$, pak existuje prvek ${ displaystyle b v B setminus A}$ takové, že oba ${ displaystyle (A setminus {a }) pohár {b }}$ a ${ displaystyle (B setminus {b }) pohár {a }}$ jsou základny. Brualdi^[3] ukázal, že je ve skutečnosti ekvivalentní s majetkem směnného kurzu
• Vícenásobná symetrická vlastnost směny bází: pokud ${ displaystyle X subseteq A setminus B}$, pak existuje podmnožina ${ displaystyle Y subseteq B setminus A}$ takové, že oba ${ displaystyle (A setminus X) pohár Y}$ a ${ displaystyle (B setminus Y) pohár X}$ jsou základny. Brylawski, Greene a Woodall (nezávisle) ukázali, že je ve skutečnosti ekvivalentem majetku směnného kurzu.
• Bijektivní směna majetku: Je tu bijekce ${ displaystyle f}$ z ${ displaystyle A}$ na ${ displaystyle B}$, tak, že pro každého ${ displaystyle a v A setminus B}$, ${ displaystyle (A setminus {a }) pohár {f (a) }}$ je základ. Brualdi^[3] ukázal, že je ekvivalentní s majetkem směnného kurzu.
• Majetková výměna přepážek: Pro každý oddíl ${ displaystyle A}$ do m částí, existuje oddíl ${ displaystyle B}$ do m díly, takové, že pro každého ${ displaystyle i v [m]}$, ${ displaystyle (A setminus A_ {i}) pohár B_ {i}}$ je základ.^[4]

Vlastnost výměny základu, která je oba symetrický a bijective není uspokojen všemi matroidy: je splněn pouze tím základní objednatelné matroidy.

Mohutnost

Vyplývá to z výměny základního majetku, že žádný člen ${ displaystyle { mathcal {B}}}$ může být vlastní podmnožinou jiného.

Kromě toho mají všechny základny daného matroidu stejnou mohutnost. V lineárním matroidu se mohutnost všech bází nazývá dimenze vektorového prostoru.

Whiteova domněnka

Předpokládá se, že všechny matroidy splňují následující vlastnost:^[2] Pro každé celé číslo t ≥ 1, Li B a B ' jsou dva t-tuples of bases with the same multi-set union, then there is a sequence of symmetric exchanges that transforms B na B '.

Charakterizace

Báze matroidu matroid zcela charakterizují: množina je nezávislá právě tehdy, je-li podmnožinou základny. Navíc lze definovat matroid ${ displaystyle M}$ být pár ${ displaystyle (E, { mathcal {B}})}$, kde ${ displaystyle E}$ je základna a ${ displaystyle { mathcal {B}}}$ je sbírka podskupin ${ displaystyle E}$, nazývané „báze“, s následujícími vlastnostmi:^[5][6]

(B1) Existuje alespoň jedna základna - ${ displaystyle { mathcal {B}}}$ je neprázdný;

(B2) Pokud ${ displaystyle A}$ a ${ displaystyle B}$ jsou odlišné báze a ${ displaystyle a v A setminus B}$, pak existuje prvek ${ displaystyle b v B setminus A}$ takhle ${ displaystyle (A setminus {a }) pohár {b }}$ je základ (jedná se o vlastnost směny základu).

Dualita

Li ${ displaystyle (E, { mathcal {B}})}$ je konečný matroid, můžeme definovat ortogonální nebo duální matroid ${ displaystyle (E, { mathcal {B}} ^ {*})}$ voláním množiny a základ v ${ displaystyle { mathcal {B}} ^ {*}}$ právě když je jeho doplněk v ${ displaystyle { mathcal {B}}}$. To lze ověřit ${ displaystyle (E, { mathcal {B}} ^ {*})}$ je skutečně matroid. Definice okamžitě znamená, že dvojí ${ displaystyle (E, { mathcal {B}} ^ {*})}$ je ${ displaystyle (E, { mathcal {B}})}$.^[7]:32[8]

Pomocí duality lze dokázat, že vlastnost (B2) lze nahradit následujícím:

(B2 *) Pokud ${ displaystyle A}$ a ${ displaystyle B}$ jsou odlišné báze a ${ displaystyle b in B setminus A}$, pak existuje prvek ${ displaystyle a v A setminus B}$ takhle ${ displaystyle (A setminus {a }) pohár {b }}$ je základ.

Obvody

Dvojí představa základu je a obvod. Obvod v matroidu je minimální závislá množina - tj. Závislá množina, jejíž vlastní podmnožiny jsou všechny nezávislé. Terminologie vzniká, protože obvody grafické matroidy jsou cykly v příslušných grafech.

jeden může definovat matroid ${ displaystyle M}$ být pár ${ displaystyle (E, { mathcal {C}})}$, kde ${ displaystyle E}$ je základna a ${ displaystyle { mathcal {C}}}$ je sbírka podskupin ${ displaystyle E}$, zvané „obvody“, s následujícími vlastnostmi:^[6]

(C1) Prázdná sada není obvod;

(C2) Podmnožina obvodu není obvod;

(C3) Pokud C₁ a C.₂ jsou obvody a X je tedy prvek v jejich průsečíku ${ displaystyle C_ {1} pohár C_ {2} setminus {x }}$ obsahuje obvod.

Další vlastností obvodů je, že pokud je množina J je nezávislý a soubor J ty {X} je závislý (tj. přidání prvku.) X dělá to závislý), pak J ty {X} obsahuje a unikátní obvod C(X,J) a obsahuje X. Tento obvod se nazývá základní obvod z X w.r.t. J. Je to analogické s faktem lineární algebry, že když přidáme vektor X do nezávislé vektorové sady J dělá to závislým, pak existuje jedinečná lineární kombinace prvků J to se rovná X.^[8]

Reference