Roncier (grafteori)

I grafteori, et brombær træ (eller en brombær ) til en ikke-orienteret graf G er en familie af forbundne subgraphs af G , som er forbundet to og to: for hvert par af disjunkte subgraphs eksisterer der en kant af G som har en ende i hver af disse underbilleder. Den rækkefølge af en bramble træ er den mindste størrelse af en dækning , dvs. af et sæt af knudepunkter af G , som har en ikke tom skæringspunktet med hver af subgraphs. De brambles kan anvendes til at karakterisere træ-bredde af G .

Akselbredde og tilflugt

Et tilflugtssted for orden k i en graf G er en funktion, der med hvert sæt X på mindre end k- hjørner forbinder en tilsluttet komponent, således at to underundersæt og har en kant, der forbinder dem. Således er billedsættet af et klodsetræ i G af rækkefølge k . Omvendt kan hver roncier anvendes til at bestemme et tilflugtssted for hvert sæt X af størrelse mindre end rækkefølgen af krat, der er en enkelt tilsluttet komponent , der indeholder alle subgraphs af roncier, der er udskilt fra X . $\ beta$ ${\ displaystyle GX}$ ${\ displaystyle \ beta (X)}$ ${\ displaystyle \ beta (Y)}$ $\ beta$ ${\ displaystyle \ beta (X)}$

Som Seymour og Thomas har vist, kendetegner rækkefølgen af et klodsetræ (eller ligesom et tilflugtssted) arborescentbredden : en graf har en klods af ordren k, hvis og kun hvis den har en bredde d 'træ større end eller lig med k -1.

Brambles størrelse

De grafer ekspandere af grad afgrænset have en træ-bredde proportional med deres antal knudepunkter, og dermed også have en lineær orden brombærranker. Men som Martin Grohe og Dániel Marx har vist, skal et sådant højt ordensbramletræ for disse grafer indeholde et eksponentielt antal sæt. Mere præcist, for disse grafer skal selv klodser, hvis rækkefølge er lidt større end kvadratroden af træbredden, have en eksponentiel størrelse. Imidlertid viste Grohe og Marx også, at en hvilken som helst graf med træbredde k indrømmer en bramble af polynomisk størrelse og rækkefølge . ${\ displaystyle \ Omega (k ^ {1/2} / \ log ^ {2} k)}$

Computational kompleksitet

Da klodser kan have en eksponentiel størrelse, er det ikke altid muligt at konstruere dem på polynomisk tid til grafer med ubegrænset træbredde. Men når træets bredde er afgrænset, er en konstruktion i polynomisk tid mulig: det er muligt at finde en bramble af rækkefølge k , når der findes i tid , hvor n er antallet af hjørner af den givne graf. Endnu hurtigere algoritmer findes for grafer med få minimale separatorer. ${\ displaystyle O (n ^ {k + 2})}$

Bodlaender, Grigoriev og Koster studerede heuristik for at finde højordensbrambles. Deres metoder genererer ikke altid rækkefølger tæt på træbredden i inputgrafen, men for plane grafer giver de en konstant tilnærmelsesgrad . Kreutzer og Tazari giver randomiserede algoritmer, som på grafer af træbredde k finder brambles af polynomial størrelse og orden i polynomial tid og dermed nærmer sig op til en logaritmisk faktor den rækkefølge, som Grohe og Marx viste eksistens for brambles af polynomial størrelse. ${\ displaystyle \ Omega (k ^ {1/2} / \ log ^ {3} k)}$

Orienterede brambles

Begrebet bramble er også defineret for rettet graf. I en rettet graf D er et klodsetræ en samling af stærkt forbundne underbilleder af D, der er forbundet to-to-to: for hvert par af uensartede elementer X , Y af klatretræet findes der i D en bue af X til Y og en bue fra Y til X. den rækkefølge af en bramble træ er den mindste størrelse af et sæt af repræsentanter , et sæt af knudepunkter af D , der har en ikke-tom skæringspunktet med hver af elementerne i tornebusken træ. Det antal af brombærranker af D er den maksimale orden af en bramble træ D. antallet af brombærranker af en orienteret graf er op til en konstant faktor, som er lig med dens orienterede Skovagtige bredde.

Noter og referencer

(fr) Denne artikel er helt eller delvist taget fra Wikipedia-artiklen på engelsk med titlen " Bramble (grafteori) " ( se forfatterlisten ) .

Paul D. Seymour og Robin Thomas , " Graph Searching and a Min-Max Theorem for Tree-Width ", Journal of Combinatorial Theory, serie B , bind. 58, nr . 1,1993, s. 22–33 ( ISSN 0095-8956 , DOI 10.1006 / jctb.1993.1027 ). Brambles kaldes "skærme", og deres rækkefølge kaldes "tykkelse".
Martin Grohe og Dániel Marx , “ On tree width, bramble size, and expansion ”, Journal of Combinatorial Theory , bind. 99, nr . 1,2009, s. 218–228 ( DOI 10.1016 / j.jctb.2008.06.004 , Matematikanmeldelser 2467827 ).
Mathieu Chapelle , Frédéric Mazoit og Ioan Todinca , ”Constructing brombær” , i Matematiske Foundations of Computer Science 2009: 34th International Symposium, MFCS 2009 Novy Smokovec, High Tatras, Slovakiet, August 24-28, 2009, Proceedings , Berlin, Springer , koll. "Forelæsningsnotater inden for datalogi" ( nr . 5734), 2009, 223-234 s. ( DOI 10.1007 / 978-3-642-03816-7_20 , Bibcode 2009LNCS.5734..223C , Matematikanmeldelser 2539494 ).
Hans L. Bodlaender Alexander Grigoriev og Arie MCA Koster , " trebredde lavere grænser med brambles " Algorithmica , vol. 51, n o 1,2008, s. 81–98 ( DOI 10.1007 / s00453-007-9056-z , matematikanmeldelser 2385750 ).
Stephan Kreutzer og Siamak Tazari , "Om brambles, gitterlignende mindreårige og parametreret intraktabilitet af monadisk andenordenslogik" , i Proceedings of the First-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '10) ,2010( læs online ) , s. 354-364.
Bruce Reed , " Introduktion af rettet træbredde, " Elsevier , vol. 3,1999, s. 222–229 ( DOI 10.1016 / S1571-0653 (05) 80061-7 )
Thor Johnson , Neil Robertson , Paul Seymour og Robin Thomas , ” Directed Tree-Width ”, Journal of kombinatorisk Teori, serie B , vol. 82, nr . 1,2001, s. 138–154 ( DOI 10.1006 / jctb.2000.2031 )
Ken-ichi Kawarabayashi og Stephan Kreutzer , " The Directed Grid Theorem ", ACM , Portland, Oregon, USA,2015, s. 655–664 ( DOI 10.1145 / 2746539.2746586 , arXiv 1411.5681 )