Blackberry (gráfelmélet)

A gráfelméletben egy irányítatlan G gráf szederje egy G gráf egymással összefüggő részgráfjainak családja : minden olyan részgráfpárhoz, amelynek nincs közös csúcsa, kell lennie egy élnek, amelynek végpontjai ebben a kettőben vannak. részgráfok. A szeder sorrendje a G csúcshalmaz legkisebb mérete, amelynek nem üres metszéspontja van a szeder minden részgráfjával. A szeder a G grafikon faszélességének leírására szolgál [1] .

Faszélesség és borítás

A G gráf k - rendű borítója egy β függvény , amely minden k -nél kisebb csúcsú X halmazt egy összefüggő G  −  X komponensbe vesz úgy, hogy bármely két β ( X ) és β ( Y ) részhalmaz érintse egymást. . Vagyis a β képei k - rendű szederet alkotnak G -ben . Ezzel szemben bármely szeder felhasználható menedék létrehozására – minden X halmazhoz, amely kisebb, mint a szeder sorrendje, egyetlen összefüggő β ( X ) komponens található, amely tartalmazza a szeder összes olyan részgráfját, amely nem kapcsolódik X -hez .

Ahogy Seymour és Thomas megmutatta , a szeder (vagy azzal egyenértékű, menedékhely) sorrendje leírja a faszélességet – a  gráfnak akkor és csak akkor van k nagyságú szederje, ha a fa szélessége legalább k − 1 [1] .

Szeder mérete

Amint Grohe és Marx megjegyezte, a korlátos fokozatú bővítők faszélessége arányos a csúcsok számával, és ahhoz, hogy minden olyan részgráfot tartalmazzon, amelyek nem osztoznak csúcsokon az adott méretű részhalmazokkal, az ilyen gráfok szederjének exponenciálisan sok különálló részgráfot kell tartalmaznia. Pontosabban, ezeknél a grafikonoknál még azoknak a szedereknek is exponenciális mérettel kell rendelkezniük, amelyek sorrendje valamivel nagyobb, mint a faszélesség négyzetgyöke. Azonban Groh és Marx azt is megmutatta, hogy minden k faszélességű gráfnak polinom méretű és rendű csíkja van [2] .

Számítási összetettség

Mivel a szálak exponenciális méretűek lehetnek, nem mindig lehetséges polinomiális időben megszerkeszteni őket korlátlan faszélességű gráfoknál. Ha azonban a fa szélessége korlátozott, lehetséges a polinomiális építési idő – ha van ilyen , időben találhatunk egy k rendű szedert , ahol n  a gráf csúcsainak száma. Még gyorsabb algoritmusok is lehetségesek kis számú minimális elválasztóval rendelkező gráfokhoz [3] .

Bodlender, Grigoriev és Coster [4] heurisztikus algoritmusokat tanulmányozott a magasrendű szeder megtalálására. Módszereik nem mindig a faszélességhez közeli nagyságrenddel adták meg a szedereket, de síkgráfokhoz állandó közelítési tényezőt adnak . Kreutzer és Tazari [5] polinomiális idejű valószínűségi keresőalgoritmusokat javasol olyan gráfokon, amelyek faszélességű , polinomiális méretű és rendű tölcsérrel rendelkeznek , ami megfelel a Grohe és Marx által levezetett logaritmikus sorrendtényezőnek ( Grohe, Marx 2009 ) a polinomok létére. méret.

Linkek

  1. ↑ 1 2 Paul D. Seymour, Robin Thomas. Gráfkeresés és egy min-max tétel a faszélességhez // Journal of Combinatorial Theory . - 1993. - T. 58 , sz. 1 . – S. 22–33 . - doi : 10.1006/jctb.1993.1027 . . Ebben a cikkben a szedereket „képernyőknek”, sorrendjüket pedig „vastagságnak” nevezzük.
  2. ↑ Martin Grohe, Daniel Marx. A fa szélességéről, a szárméretről és a kiterjedésről // Journal of Combinatorial Theory . - 2009. - T. 99 , sz. 1 . – S. 218–228 . - doi : 10.1016/j.jctb.2008.06.004 . .
  3. ↑ Mathieu Chapelle, Frédéric Mazoit, Ioan Todinca. A számítástechnika matematikai alapjai 2009: 34. Nemzetközi Szimpózium, MFCS 2009, Újtátrafüred, Magas-Tátra, Szlovákia, 2009. augusztus 24-28., Proceedings. - Berlin: Springer, 2009. - T. 5734. - S. 223-234. - doi : 10.1007/978-3-642-03816-7_20 . .
  4. ↑ Bodlaender. Faszélesség alsó határa szárral. — Algorithmica . - 2008. - T. 51. - S. 81–98. - doi : 10.1007/s00453-007-9056-z . .
  5. ↑ Stephan Kreutzer, Siamak Tazari. A diszkrét algoritmusokról szóló huszonegyedik éves ACM-SIAM szimpózium (SODA '10) anyaga. - 2010. - S. 354-364. .