Blackberry (grafteori)

I grafteori er en brombær for en urettet graf G en familie af forbundne undergrafer af en graf G , der rører hinanden: for ethvert par af undergrafer, der ikke har fælles knudepunkter, skal der være en kant, hvis endespidser ligger i disse to underafsnit. Rækkefølgen af ​​brombær er den mindste størrelse af toppunktet G , der har et ikke-tomt skæringspunkt med hver undergraf af brombæret. Brombær bruges til at beskrive træbredden af ​​en graf G [1] .

Træbredde og dæksel

En dækning af orden k i en graf G er en funktion β , der tager hvert sæt X med mindre end k hjørner ind i en forbundet komponent G  −  X på en sådan måde, at to vilkårlige delmængder β ( X ) og β ( Y ) berører hinanden . Det vil sige, at billederne af β danner et brombær med orden k i G. Omvendt kan en hvilken som helst brombær bruges til at skabe et husly — for hvert sæt X , der er mindre end rækkefølgen af ​​brombær, er der en enkelt tilsluttet komponent β ( X ), der indeholder alle undergrafer i brombæret, der ikke er forbundet til X .

Som Seymour og Thomas har vist , beskriver rækkefølgen af ​​et brombær (eller tilsvarende ly) træbredden  - en graf har et brombær af orden k , hvis og kun hvis træbredden er mindst k − 1 [1] .

Størrelse af brombær

Som Grohe og Marx bemærkede, har afgrænsede gradudvidere en træbredde, der er proportional med antallet af hjørner, og for at inkludere alle undergrafer, der ikke deler spidser med hver undergruppe af den størrelse, skal brombæret for sådanne grafer indeholde eksponentielt mange forskellige undergrafer. Mere præcist, for disse grafer, skal selv de brombær, hvis rækkefølge er lidt større end kvadratroden af ​​træbredden, have eksponentiel størrelse. Groh og Marx viste dog også, at enhver graf med træbredde k har en torne med polynomisk størrelse og rækkefølge [2] .

Beregningsmæssig kompleksitet

Da torne kan have eksponentiel størrelse, er det ikke altid muligt at konstruere dem i polynomisk tid for grafer med ubegrænset træbredde. Men hvis træbredden er begrænset, er polynomial konstruktionstid mulig - det er muligt at finde en brombær af orden k , hvis en sådan findes, i tid , hvor n  er antallet af hjørner i grafen. Endnu hurtigere algoritmer er mulige for grafer med et lille antal minimale separatorer [3] .

Bodlender, Grigoriev og Coster [4] studerede heuristiske algoritmer til at finde brombær af høj orden. Deres metoder gav ikke altid brombær med en rækkefølge tæt på træbredden, men for plane grafer giver de en konstant tilnærmelsesfaktor . Kreutzer og Tazari [5] foreslår polynomisk- tidssandsynlighedssøgealgoritmer på grafer med træbredde k - brønde af polynomisk størrelse og rækkefølge , hvilket svarer til den logaritmiske ordensfaktor, der er udledt af Grohe og Marx ( Grohe, Marx 2009 ) for eksistensen af ​​polynomium størrelse.

Links

  1. ↑ 1 2 Paul D. Seymour, Robin Thomas. Grafsøgning og en min-max-sætning for træbredde // Journal of Combinatorial Theory . - 1993. - T. 58 , no. 1 . — S. 22–33 . - doi : 10.1006/jctb.1993.1027 . . I denne artikel kaldes brombær "skærme", og deres ordrer kaldes "tykkelse".
  2. ↑ Martin Grohe, Daniel Marx. Om træets bredde, tornes størrelse og ekspansion // Journal of Combinatorial Theory . - 2009. - T. 99 , no. 1 . — S. 218–228 . - doi : 10.1016/j.jctb.2008.06.004 . .
  3. ↑ Mathieu Chapelle, Frédéric Mazoit, Ioan Todinca. Mathematical Foundations of Computer Science 2009: 34th International Symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakiet, August 24-28, 2009, Proceedings. - Berlin: Springer, 2009. - T. 5734. - S. 223-234. - doi : 10.1007/978-3-642-03816-7_20 . .
  4. ↑ Bodlaender. Træbredde nedre grænser med brambær. - Algoritmik . - 2008. - T. 51. - S. 81–98. - doi : 10.1007/s00453-007-9056-z . .
  5. ↑ Stephan Kreutzer, Siamak Tazari. Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '10). - 2010. - S. 354-364. .