Obvod matroidu - Matroid girth - Wikipedia

v teorie matroidů, matematická disciplína, obvod matroidu je velikost jeho nejmenšího obvodu nebo závislé množiny. The souhvězdí matroidu je obvod jeho duální matroid. Obvod matroidu zobecňuje pojem nejkratšího cyklu v grafu, konektivitu okraje grafu, Hallovy množiny v bipartitních grafech, dokonce množiny v rodinách množin a obecnou polohu množin bodů. Je těžké to spočítat, ale fixovatelný parametr pro lineární matroidy při parametrizaci oběma hodnost matroidů a velikost pole lineárního vyjádření.

Příklady

Terminologie "obvodu" zobecňuje použití obvod v teorii grafů, což znamená délku nejkratšího cyklu v grafu: obvod a grafický matroid je stejný jako obvod podkladového grafu.[1]

Obvod ostatních tříd matroidů také odpovídá důležitým kombinatorickým problémům. Například obvod co-grafického matroidu (nebo cogirth grafického matroidu) se rovná okrajová konektivita základního grafu, počet hran v a minimální řez grafu.[1] Obvod a příčný matroid udává mohutnost minimální Hallovy množiny v bipartitním grafu: jedná se o množinu vrcholů na jedné straně bipartice, která netvoří množinu koncových bodů vhodný v grafu.[2]

Libovolná sada bodů v Euklidovský prostor dává vzniknout realitě lineární matroid tlumočením Kartézské souřadnice bodů jako vektory a reprezentace matroidu Obvod výsledného matroidu se rovná jedné plus rozměr prostoru, když je základní množina bodu v obecná pozice Jinak je menší. Obvody skutečných lineárních matroidů také vznikají v komprimované snímání, kde je stejný koncept označován jako jiskra matice.[3]

Obvod a binární matroid dává mohutnost minimální sudé sady, podkolekce rodiny sad, která zahrnuje sudý počet kopií každého prvku sady.[2]

Výpočetní složitost

Určení obvodu a binární matroid je NP-tvrdé.[4]

Navíc, určení obvodu lineárního matroidu dané maticí představující matroid je W [1] - tvrdý když je parametrizován obvodem nebo hodností matroidu, ale fixovatelný s možností parametrizace kombinací hodnosti a velikosti podkladu pole.[2]

Pro libovolný matroid daný znakem věštba nezávislosti, je nemožné najít obvod pomocí subexponenciálního počtu matroidových dotazů.[5] Podobně pro skutečný lineární matroid hodnosti r, s n prvky, popsané věštcem, který dává orientace ze všech r-tuple prvků, to vyžaduje věštecké dotazy k určení obvodu.[6]

Rovněž byly vzaty v úvahu výpočty využívající obvodový věštec (věštec, který hlásí nejmenší závislou podmnožinu dané sady prvků).[7]

Reference

  1. ^ A b Cho, Jung Jin; Chen, Yong; Ding, Yu (2007), „Na (ko) obvodu spojeného matroidu“, Diskrétní aplikovaná matematika, 155 (18): 2456–2470, doi:10.1016 / j.dam.2007.06.015, PAN  2365057.
  2. ^ A b C Panolan, Fahad; Ramanujan, M. S .; Saurabh, Saket (2015), „K parametrizované složitosti obvodů a problémům s připojením na lineárních matroidech“ (PDF), Dehne, Frank; Sack, Jörg-Rüdiger; Stege, Ulrike (eds.), Algoritmy a datové struktury: 14. mezinárodní sympozium, WADS 2015, Victoria, BC, Kanada, 5. – 7. Srpna 2015, sborník, Přednášky v informatice, 9214, Springer, str. 566–577, doi:10.1007/978-3-319-21840-3_47.
  3. ^ Donoho, David L.; Elad, Michael (2003), „Optimálně řídké zastoupení obecně (neorthogonálních) slovníků pomocí ℓ1 minimalizace ", Sborník Národní akademie věd Spojených států amerických, 100 (5): 2197–2202, doi:10.1073 / pnas.0437847100, PMC  153464, PMID  16576749.
  4. ^ Cho, Chen & Ding (2007) Všimněte si, že se jedná o důsledek výsledku Alexander Vardy v teorii kódování: Vardy, Alexander (1997), „Neřešitelnost výpočtu minimální vzdálenosti kódu“, Transakce IEEE na teorii informací, 43 (6): 1757–1766, doi:10.1109/18.641542, PAN  1481035.
  5. ^ Jensen, Per M .; Korte, Bernhard (1982), „Složitost algoritmů vlastností matroidů“, SIAM Journal on Computing, 11 (1): 184–190, doi:10.1137/0211014, PAN  0646772.
  6. ^ Erickson, J .; Seidel, R. (1995), „Lepší dolní hranice pro detekci afinních a sférických degenerací“, Diskrétní a výpočetní geometrie, 13 (1): 41–57, doi:10.1007 / BF02574027, PAN  1300508.
  7. ^ Hausmann, D .; Korte, B. (1981), „Algoritmické versus axiomatické definice matroidů“, Matematické programování na Oberwolfach (Proc. Conf., Math. Forschungsinstitut, Oberwolfach, 1979), Matematické programovací studie, 14, str. 98–111, doi:10.1007 / BFb0120924, PAN  0600125.