Bramble (teorie grafů) - Bramble (graph theory)

Ostružina řádu čtyři v mřížkovém grafu 3 × 3, skládající se ze šesti vzájemně se dotýkajících připojených podgrafů

V teorii grafů, a ostružiní pro neorientovaný graf G je rodina připojeno podgrafy z G že se všichni navzájem dotýkají: pro každý pár disjunktních podgrafů musí existovat hrana G který má v každém podgrafu jeden koncový bod. The objednat ostružiníku je nejmenší velikost a bít set, sada vrcholů G který má neprázdnou křižovatku s každým ze subgrafů. Brambles lze použít k charakterizaci šířka stromu z G.[1]

Šířka stromu a ráje

A útočiště řádu k v grafu G je funkce β který mapuje každou sadu X méně než k vrcholy k připojené součásti G − X, a to takovým způsobem, že každé dvě podmnožiny β(X) a β(Y) dotýkejte se navzájem. Tedy soubor obrazů β tvoří ostružinu v G, s objednávkou k. Naopak, každý ostružiník lze použít k určení útočiště: pro každou sadu X o velikosti menší, než je řád ostružiníku, existuje jedinečná připojená součást β(X), který obsahuje všechny podgrafy v ostružině, od nichž se disjunktuje X.

Jak ukázali Seymour a Thomas, charakterizuje se řád ostružiny (nebo ekvivalentně útočiště) šířka stromu: graf má ostružinu řádu k právě když má alespoň šířku stromu k − 1.[1]

Velikost ostružin

Expandovací grafy omezeného stupeň mají šířku stromu úměrnou jejich počtu vrcholů, a proto mají také ostružiny lineárního řádu. Nicméně, jak Martin Grohe a Dániel Marx ukázal, že pro tyto grafy musí ostružina tak vysokého řádu obsahovat exponenciálně mnoho sad. Silněji pro tyto grafy musí mít exponenciální velikost i ostružiny, jejichž pořadí je o něco větší než druhá odmocnina šířky stromu. Grohe a Marx však také ukázali, že každý graf šířky stromu k má ostružinu polynomiální velikosti a řádu .[2]

Výpočetní složitost

Protože ostružiny mohou mít exponenciální velikost, není vždy možné je konstruovat polynomiální čas pro grafy neomezené šířky stromu. Když je však šířka stromu omezená, je možná polynomiální časová konstrukce: je možné najít ostružinu řádu k, pokud existuje, v čase O (nk + 2) kde n je počet vrcholů v daném grafu. Pro grafy s několika minimálními oddělovači jsou možné ještě rychlejší algoritmy.[3]

Bodlaender, Grigorjev a Koster[4] studoval heuristiku pro hledání ostružin vyššího řádu. Jejich metody ne vždy generují ostružiny řádu blízké šířce stromu vstupního grafu, ale pro rovinné grafy dávají konstantní přibližný poměr. Kreutzer a Tazari[5] poskytnout randomizované algoritmy že na grafech šířky stromu k, najděte ostružiny velikosti polynomu a řádu v polynomiálním čase, přicházející do logaritmického faktoru řádu zobrazeného Grohe & Marx (2009) existovat pro ostružiny o velikosti polynomu.

Řízené bramble

Koncept ostružiníku byl také definován pro směrované grafy.[6][7] V řízený graf D, a ostružiní je sbírka silně propojený podgrafy D že se všichni navzájem dotýkají: pro každou dvojici disjunktních prvků X, Y ostružiníku musí existovat oblouk D z X na Y a jeden z Y na X. The objednat ostružiníku je nejmenší velikost a bít set, sada vrcholů D který má neprázdnou křižovatku s každým z prvků ostružiny. The číslo ostružiny z D je maximální řád ostružiny v DOstružinové číslo směrovaného grafu je v konstantním faktoru jeho směrované šířky stromu.[8]

Reference

  1. ^ A b Seymour, Paul D.; Thomas, Robin (1993), „Hledání grafů a věta o min-max pro šířku stromu“, Journal of Combinatorial Theory, Řada B, 58 (1): 22–33, doi:10.1006 / jctb.1993.1027, PAN  1214888. V tomto odkazu se ostružiny nazývají „obrazovky“ a jejich pořadí se nazývá „tloušťka“.
  2. ^ Grohe, Martin; Marx, Dániel (2009), „O šířce stromu, velikosti ostružin a rozšíření“, Journal of Combinatorial Theory, Řada B, 99 (1): 218–228, doi:10.1016 / j.jctb.2008.06.004, PAN  2467827.
  3. ^ Chapelle, Mathieu; Mazoit, Frédéric; Todinca, Ioan (2009), „Constructing brambles“, Matematické základy informatiky 2009: 34. mezinárodní sympozium, MFCS 2009, Nový Smokovec, Vysoké Tatry, Slovensko, 24. – 28. Srpna 2009, sborník, Přednášky v informatice, 5734, Berlín: Springer, s. 223–234, Bibcode:2009LNCS.5734..223C, doi:10.1007/978-3-642-03816-7_20, PAN  2539494.
  4. ^ Bodlaender, Hans L.; Grigorjev, Alexander; Koster, Arie M. C. A. (2008), „Dolní hranice šířky stromu s ostružinami“, Algorithmica, 51 (1): 81–98, doi:10.1007 / s00453-007-9056-z, PAN  2385750.
  5. ^ Kreutzer, Stephan; Tazari, Siamak (2010), „O ostružinách, nezletilých podobných mřížce a parametrizované neúčinnosti monadické logiky druhého řádu“, Sborník dvacátého prvního výročního sympozia ACM-SIAM o diskrétních algoritmech (SODA '10), str. 354–364.
  6. ^ Reed, Bruce (1999), „Představujeme směrovanou šířku stromu“, Elektronické poznámky v diskrétní matematice, 3, Elsevier, s. 222–229, doi:10.1016 / S1571-0653 (05) 80061-7
  7. ^ Johnson, Thor; Robertson, Neil; Seymour, Paul; Thomas, Robin (2001), „Directed Tree-Width“, Journal of Combinatorial Theory, Series B, 82, str. 138–154, doi:10.1006 / jctb.2000.2031
  8. ^ Kawarabayashi, Ken-ichi; Kreutzer, Stephan (2015), „Theeded Grid Theorem“, Sborník ze čtyřicátého sedmého výročního symposia ACM o teorii práce s počítači (STOC '15), Portland, Oregon, USA: ACM, str. 655–664, arXiv:1411.5681, doi:10.1145/2746539.2746586