Greedoid - Greedoid

v kombinatorika, a greedoid je typ nastavený systém. Vyplývá to z pojmu matroid, který původně představil Whitney v roce 1935 studovat rovinné grafy a byl později použit Edmonds charakterizovat třídu optimalizačních problémů, které lze vyřešit pomocí chamtivé algoritmy. Kolem roku 1980, Korte a Lovász představil greedoida, aby dále zobecnil tuto charakterizaci chamtivých algoritmů; odtud název greedoid. kromě matematická optimalizace, byli spojeni také s greedoidy teorie grafů, teorie jazyků, teorie objednávek, a další oblasti matematiky.

Definice

A nastavený systém (F, E) je sbírka F z podmnožiny pozemní sady E (tj. F je podmnožinou souboru napájecí sada E). Když uvažujeme o greedoidu, člen F se nazývá a proveditelná sada. Při zvažování a matroid, proveditelná sada je také známá jako nezávislá sada.

An přístupný systém setů (F, E) je množinový systém, ve kterém každá neprázdná proveditelná množina X obsahuje prvek x takový, že X {x} je proveditelné. To znamená, že jakékoli neprázdné konečný, přístupný souborový systém nutně obsahuje prázdná sada ∅.^[1]

A greedoid (F, E) je systém přístupné sady, který splňuje požadavky směnit majetek:

pro všechna X, Y ∈ F s | X | > | Y |, existuje několik x ∈ X Y takových, že Y∪ {x} ∈ F

(Poznámka: Někteří si tento termín rezervují směnit majetek pro podmínku na základech greedoidu a raději nazýváme výše uvedenou podmínku „vlastnost augmentace“.)

A základ greedoidu je maximální proveditelná množina, což znamená, že je proveditelná množina, ale není obsažena v žádné jiné. Základem podmnožiny X z E je maximální proveditelná množina obsažená v X.

The hodnost greedoidu je velikost základny. Vlastností směny mají všechny báze stejnou velikost. Funkce rank je tedy dobře definované. Hodnost podmnožiny X z E je velikost základu X. Stejně jako u matroidů, i greedoidy mají kryptomorfismus z hlediska hodnostních funkcí.^[2]Funkce ${ displaystyle r: 2 ^ {E} to mathbb {Z}}$ je hodnostní funkce greedoida na základní množině E právě tehdy ${ displaystyle r}$ je subkardinální, monotónní a místně semimodulární, to znamená pro všechny ${ displaystyle X, Y subseteq E}$ a jakékoli ${ displaystyle e, f v E}$ my máme

subkardinalita: ${ displaystyle r (X) leq | X |}$ ;
monotónnost: ${ displaystyle r (X) leq r (Y)}$ kdykoli ${ displaystyle X subseteq Y subseteq E}$ ; a
lokální semimodularita: ${ displaystyle r (X) = r (X pohár {e, f })}$ kdykoli ${ displaystyle r (X) = r (X pohár {e }) = r (X pohár {f })}$ .

Třídy

Většina tříd greedoidů má mnoho ekvivalentních definic, pokud jde o množinový systém, jazyk, poset, zjednodušený komplex, a tak dále. Následující popis pokračuje tradiční cestou výpisu pouze několika známějších charakterizací.

An intervalový greedoid (F, E) je greedoid, který uspokojuje Intervalová vlastnost:

pokud A, B, C ∈ F s A ⊆ B ⊆ C, pak pro všechna x ∈ E C, (A∪ {x} ∈ F a C∪ {x} ∈ F) znamená B∪ {x} ∈ F

Ekvivalentně je intervalový greedoid takovým greedoidem, že sjednocení libovolných dvou proveditelných množin je proveditelné, pokud je obsaženo v jiné proveditelné množině.

An antihmota (F, E) je greedoid, který uspokojuje Intervalová vlastnost bez horních mezí:

pokud A, B ∈ F s A ⊆ B, tedy pro všechna x ∈ E B, A∪ {x} ∈ F znamená B∪ {x} ∈ F

Ekvivalentně je antihmota (i) greedoid s jedinečným základem; nebo ii) systém přístupné sady uzavřený sjednocením. Je snadné vidět, že antihmota je také intervalový greedoid.

A matroid (F, E) je neprázdný greedoid, který uspokojuje Intervalová vlastnost bez dolních mezí:

pokud B, C ∈ F s B ⊆ C, tedy pro všechna x ∈ E C, C ∪ {x} ∈ F znamená B∪ {x} ∈ F

Je snadné vidět, že matroid je také intervalový greedoid.

Příklady

Zvažte neorientovaného graf G. Nechť základní sada bude hrany G a proveditelné sady budou hranová sada každé z nich les (tj. podgraf neobsahující žádný cyklus) G. Tato množinová soustava se nazývá cyklus matroid. O nastaveném systému se říká, že grafický matroid pokud je to matroid cyklu nějakého grafu. (Původně cyklus matroid byl definován na obvodůnebo minimální závislé množiny. Odtud název cyklu.)
Uvažujme konečný, neorientovaný graf G. zakořeněné na vrcholu r. Nechť pozemní množina jsou vrcholy G a proveditelné množiny vrcholové podmnožiny obsahující r, které indukují spojené podgrafy G. Tomu se říká vyhledávání vrcholů greedoid a je to druh antihmoty.
Zvažte konečnou, řízený graf D zakořeněné v r. Nechť pozemní množina jsou (směrované) hrany D a proveditelné množiny jsou hranové množiny každého směrovaného podstromu zakořeněného na r, přičemž všechny hrany směřují od r. Tomu se říká vyhledávání linek greedoidnebo směrovaný rozvětvený greedoid. Je to intervalový greedoid, ale ani antihmota, ani matroid.
Zvažte písmeno m matice M. Nechť základní sada E jsou indexy sloupců od 1 do n a proveditelné sady budou F = {X ⊆ E: submatice M_{{1, ..., | X |}, X} je invertibilní matice }. Tomu se říká Gaussova eliminační greedoid protože tato struktura je základem Gaussova eliminace algoritmus. Je to greedoid, ale ne intervalový greedoid.

Chamtivý algoritmus

Obecně platí, že chamtivý algoritmus je jen iterační proces, ve kterém a místně nejlepší volba, obvykle vstup maximální hmotnosti, se volí každé kolo, dokud nejsou vyčerpány všechny dostupné možnosti. Abychom popsali stav založený na greedoidu, ve kterém je chamtivý algoritmus optimální (tj. získá základ maximální hodnoty), potřebujeme nějaké běžnější terminologie v teorii greedoidů.Bez ztráty obecnosti, považujeme greedoid G = (F, E) s E konečný.

Podmnožina X z E je hodnost proveditelná pokud má největší průsečík X s libovolnou proveditelnou množinou velikost rovnou hodnosti X. V matroidu je každá podmnožina E hodnocená. Rovnost však neplatí pro greedoidy obecně.

Funkce w: E → ℝ je R-kompatibilní pokud {x ∈ E: w (x) ≥ c} je hodnocení proveditelné pro všechny reálná čísla C.

Objektivní funkce f: 2^S → ℝ je lineární přes množinu S, jestliže pro všechna X ⊆ S máme f (X) = Σ_{x ∈ X} w (x) pro některé váhová funkce w: S → ℜ.

Tvrzení. Chamtivý algoritmus je optimální pro každého R-kompatibilní lineární objektivní funkce nad greedoidem.

Intuicí za tímto návrhem je, že během iteračního procesu je každá optimální výměna minimální váhy umožněna vlastností výměny a optimální výsledky lze získat z proveditelných sad v podkladovém greedoidu. Tento výsledek zaručuje optimálnost mnoha známých algoritmů. Například a minimální kostra a vážený graf lze získat pomocí Kruskalův algoritmus, což je chamtivý algoritmus pro matroid cyklu. Primův algoritmus lze vysvětlit tím, že místo toho použijeme vyhledávání vrcholů greedoid.

Viz také

Reference

^ Všimněte si, že vlastnost usnadnění je přísně slabší než dědičné vlastnictví a matroid, což vyžaduje každý podmnožina nezávislé množiny být nezávislá.
^ Björner, Anders; Ziegler, Günter M. (1992), „8. Introduction to greedoids“, in White, Neil (ed.), Matroid aplikace Encyklopedie matematiky a její aplikace, 40, Cambridge: Cambridge University Press, str.284–357, doi:10.1017 / CBO9780511662041.009, ISBN 0-521-38165-7, PAN 1165537, Zbl 0772.05026CS1 maint: ref = harv (odkaz)

Björner, Anders; Ziegler, Günter M. (1992), „8. Introduction to greedoids“, in White, Neil (ed.), Matroid aplikace Encyklopedie matematiky a její aplikace, 40, Cambridge: Cambridge University Press, str.284–357, doi:10.1017 / CBO9780511662041.009, ISBN 0-521-38165-7, PAN 1165537, Zbl 0772.05026CS1 maint: ref = harv (odkaz)
Edmonds, Jacku (1971), „Matroidi a chamtivý algoritmus“, Matematické programování, 1: 127–136, doi:10.1007 / BF01584082, Zbl 0253.90027.
Helman, Paul; Moret, Bernard M. E .; Shapiro, Henry D. (1993), „Přesná charakteristika chamtivých struktur“, SIAM Journal on Discrete Mathematics, 6 (2): 274–283, CiteSeerX 10.1.1.37.1825, doi:10.1137/0406021, Zbl 0798.68061.
Korte, Bernhard; Lovász, László (1981), „Matematické struktury, které tvoří základ chamtivých algoritmů“, Gecseg, Ferenc (ed.), Základy teorie výpočtu: Sborník mezinárodní konference FCT z roku 1981, Szeged, Maďarsko, 24. – 28. Srpna 1981, Přednášky v informatice, 117, Berlín: Springer-Verlag, str. 205–209, doi:10.1007/3-540-10854-8_22, Zbl 0473.68019.
Korte, Bernhard; Lovász, László; Schrader, Rainer (1991), GreedoidsAlgoritmy a kombinatorika, 4, New York, Berlín: Springer-Verlag, ISBN 3-540-18190-3, Zbl 0733.05023.
Oxley, James G. (1992), Teorie matroidů, Oxford Science Publications, Oxford: Oxford University Press, ISBN 0-19-853563-5, Zbl 0784.05002.
Whitney, Hassler (1935), „O abstraktních vlastnostech lineární nezávislosti“, American Journal of Mathematics, 57 (3): 509–533, doi:10.2307/2371182, hdl:10338.dmlcz / 100694, JSTOR 2371182, Zbl 0012.00404.

externí odkazy

[1] Všimněte si, že vlastnost usnadnění je přísně slabší než dědičné vlastnictví a matroid, což vyžaduje každý podmnožina nezávislé množiny být nezávislá.

[2] Björner, Anders; Ziegler, Günter M. (1992), „8. Introduction to greedoids“, in White, Neil (ed.), Matroid aplikace Encyklopedie matematiky a její aplikace, 40, Cambridge: Cambridge University Press, str.284–357, doi:10.1017 / CBO9780511662041.009, ISBN 0-521-38165-7, PAN 1165537, Zbl 0772.05026CS1 maint: ref = harv (odkaz)

[1]

[2]