Polymatroid - Polymatroid
![]() | tento článek potřebuje další citace pro ověření.Únor 2011) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
V matematice, a polymatroid je polytop spojené s a submodulární funkce. Pojem představil Jack Edmonds v roce 1970.[1] To je také popisováno jako multiset analog matroid.
Definice
Nechat být konečný soubor a neklesající submodulární funkce, tedy pro každého my máme a pro každého my máme . Definujeme polymatroid spojené s být následující polytop:
.
Když povolíme vstupy z jako záporný označujeme tento polytop a nazvat jej rozšířeným polymatroidem spojeným s .[2]
Ekvivalentní definice
Nechat být konečný soubor a . Říkáme modul z být součtem všech jejích položek a označit kdykoli pro každého (Všimněte si, že to dává objednat na ). A polymatroid na zemi je neprázdné kompaktní podmnožina v , sada nezávislých vektorů, takže:
- Máme to, pokud , pak pro každého :
- Li s , pak existuje vektor takhle .
Tato definice je ekvivalentní té, která byla popsána dříve[3], kde je funkce definovaná pro každého .
Vztah k matroidům
Každému matroid na zemi můžeme přiřadit soubor , kde pro každého máme to
Tím, že vezme konvexní trup dostaneme polymatroid ve smyslu druhé definice spojené s hodnostní funkcí .
Vztah k zobecněné permutahedře
Protože generalizovaná permutahedra lze zkonstruovat z submodulárních funkcí a každý zobecněný permutahedron má přidruženou submoduulární funkci, máme, že by měla existovat shoda mezi zobecněnými permutahedry a polymatroidy. Ve skutečnosti je každý polymatroid zobecněný permutahedron, který byl přeložen tak, aby měl v počátku vrchol. Tento výsledek naznačuje, že kombinatorické informace o polymatroidech jsou sdíleny s generalizovanou permutahedrou.
Vlastnosti
je neprázdné právě tehdy a to je neprázdné právě tehdy .
Vzhledem k jakémukoli rozšířenému polymatroidu existuje jedinečná submodulární funkce takhle a .
Contrapolymatroidy
Pro supermodulární F jeden může analogicky definovat kontrapolymatroid
To analogicky zobecňuje dominantní postavení překlenovací sada polytop matroidů.
Diskrétní polymatroidy
Když se soustředíme pouze na mřížové body z našich polymatroidů dostaneme to, co se nazývá, diskrétní polymatroidy. Formálně vzato, definice a oddělený polymatroid jde přesně jako ten pro polymatroidy, kromě toho, kde budou vektory žít, místo budou žít v . Tento kombinatorický objekt je velmi zajímavý z důvodu jejich vztahu k monomiální ideály.
Reference
- Poznámky pod čarou
- ^ Edmonds, Jacku. Submodulární funkce, matroidy a určité mnohostěny. 1970. Kombinatorické struktury a jejich aplikace (Proc. Calgary Internat. Conf., Calgary, Alta., 1969), str. 69–87 Gordon and Breach, New York. PAN0270945
- ^ Schrijver, Alexander (2003), Kombinatorická optimalizace, Springer, §44, s. 767, ISBN 3-540-44389-4
- ^ J. Herzog, T. Hibi. Monomiální ideály. 2011. Postgraduální texty z matematiky 260, s. 237–263 Springer-Verlag, Londýn.
- Dodatečné čtení
- Lee, Jon (2004), První kurz kombinatorické optimalizace, Cambridge University Press, ISBN 0-521-01012-8
- Fujishige, Saruto (2005), Submodulární funkce a optimalizace, Elsevier, ISBN 0-444-52086-4
- Narayanan, H. (1997), Submodulární funkce a elektrické sítě, ISBN 0-444-82523-1