Nyomtáv

A gráfelméletben a G gráf útvonaldekompozíciója  informálisan a G gráf „megvastagított” útvonalként való ábrázolása [1] , a G gráf útszélessége pedig egy szám, amely azt méri, hogy G  gráf mennyi volt már. megvastagodott. Formálisabban az útfelbontás a G gráf egy részhalmazának csúcsainak sorozata úgy, hogy az egyes élek végpontjai az egyik részhalmazban jelennek meg, és mindegyik csúcs (legalább) az egyik halmazhoz tartozik [2] , és az út szélessége eggyel kisebb, mint a legnagyobb halmaz mérete egy ilyen bontásban. A vágányszélességet intervallumvastagságnak is nevezik .(eggyel kisebb, mint a G gráf intervallum szupergráfjának legnagyobb klikkje ) , a csúcsosztás értéke vagy a csúcskeresési szám [3] [4] .

Az útvonal szélessége és az útvonal felbontása szorosan analóg a faszélességgel és a fa dekompozícióval . Kulcsszerepet játszanak a gráf- mollok elméletében  – a gráf-mollok alá zárt gráfcsaládok , amelyek nem tartalmaznak minden erdőt , úgy jellemezhetők, hogy korlátozott az útszélességük [2] , és az általános szerkezetben keletkező "örvények" a kiskorúak vonatkozásában zárt gráfcsaládok elmélete korlátozott útszélességgel rendelkezik [5] . Az útvonalszélesség és a korlátos útvonalszélességű gráfok a VLSI tervezésben , a gráfvizualizációban és a számítógépes nyelvészetben használhatók .

A tetszőleges gráfok útvonalának megtalálásának problémája NP-nehéz . Sőt, még az útszélesség pontos közelítése is NP-nehéz [6] [7] . Ez a probléma azonban fix-parametrikusan megoldható  – annak tesztelése, hogy egy gráfnak van -e k útszélessége, megoldható időben, amely a gráf méretében lineáris, de k-ban szuperexponenciális [ 8] Ezenkívül néhány speciális gráfosztályra, mint pl. fák , az útszélesség polinomiális időben is kiszámítható k -tól függetlenül [9] [10] . A gráfelmélet számos problémája hatékonyan megoldható korlátozott útvonalszélességű gráfokon a gráf útvonalbontásának dinamikus programozásával [11] . A fa dekompozíció felhasználható a dinamikus programozási algoritmusok kapacitásbonyolultságának becslésére is korlátozott faszélességű gráfokon [12] .

Definíció

A gráf minorokról szóló első híres cikksorozatában Robertson és Seymour [2] a G gráf útvonaldekompozícióját a G gráf csúcsainak X i részhalmazainak sorozataként határozta meg két tulajdonsággal:

  1. Minden G élhez van olyan i , hogy az él mindkét végpontja az X i részhalmazhoz tartozik
  2. Bármely három i ≤ j ≤ k index esetén X i ∩ X k ⊆ X j .

E két tulajdonság közül a második egyenértékű azzal a követelménnyel, hogy bármely csúcsot tartalmazó részhalmazok a teljes sorozat folytonos részsorozatát képezzék. Robertson és Seymour későbbi, gráf-mollokról szóló sorozatának nyelvén az útfelbontás ( X , T ) fafelbontása, amelyben az alapul szolgáló T dekompozíciós fa egy útvonal .

Az útvonal dekompozíció szélessége ugyanúgy van megadva, mint a fabontásnál, max i  | X i | − 1, és a G gráf útszélessége egyenlő a G gráf összes útdekompozíciójának minimális szélességével . Az X i méretéből egyet levonva ebben a definícióban kevés hatása van az útvonalszélesség legtöbb alkalmazására, de egyenlővé teszi az útvonalszélességet eggyel.

Alternatív leírások

Ahogy Bodlaender [3] írja , az útvonal szélességét sok ekvivalens módon leírhatjuk.

Ragasztási szekvenciák

A fa dekompozíciót G i gráfok sorozataként írhatjuk le , amelyeket a sorozat szomszédos gráfjaiban csúcspárok azonosításával ragasztunk össze, és ennek az összeillesztésnek eredményeként egy G gráf jön létre . G i gráfokként vehetjük az X i halmazok generált részgráfjait az útbontás első definíciójában, a szomszédos generált részgráfokban csúcsokat ragasztva, ha ezeket a csúcsokat ugyanaz a G -beli csúcs generálja . Egy másik irányban felvehetjük X i -t a G i gráfok csúcskészleteiként . A fa dekompozíció szélessége ekkor eggyel kisebb, mint az egyik G i gráf csúcsainak maximális száma [2] .

Intervallumvastagság

Bármely G gráf útvonalszélessége eggyel kisebb, mint a G -t részgráfként tartalmazó intervallumgráf legkisebb klikkszáma [14] . Vagyis a G gráf tetszőleges fa dekompozíciójához találhatunk egy intervallum szupergráfot, és bármely G intervallum szupergráfhoz megtalálhatjuk a G gráf fa dekompozícióját, amelynek a dekompozíció szélessége eggyel kisebb, mint az intervallumgráf klikkszáma. .

Egy irányban tegyük fel, hogy adott egy G gráf fafelbontása . Ekkor ábrázolhatjuk a dekompozíció csúcsait az egyenes pontjaiként (abban a sorrendben, ahogy belépnek az útvonalba), és minden v csúcsot zárt intervallumként ábrázolhatunk, amelyeknek ezek a pontjai a végpontok. Legyen például ( X 1 , . . . , X r ) a G gráf útfelbontása , pontok az [1, . . . , r], akkor a v csúcs reprezentációja az intervallum . Ekkor a v -t tartalmazó csúcsok fafelbontása megfelel a v intervallum reprezentációjának (vagyis végpontjainak) . A G csúcsaiból képzett intervallummetszés gráf egy G -t részgráfként tartalmazó intervallumgráf. Maximális klikkjeit a reprezentáló pontokat tartalmazó intervallumhalmaz adja, legnagyobb klikkméretük pedig eggyel nagyobb, mint a G gráf útszélessége .

A másik irányban, ha G egy p  + 1 klikkszámú intervallumgráf részgráfja, akkor G -nek van egy p szélességű fadekompozíciója, amelynek csúcsait az intervallumgráf maximális klikkjei adják. Például az ábrán az intervallumábrázolást tartalmazó intervallumgráfnak van egy fafelbontása, amelynek öt csúcsa az ABC , ACD , CDE , CDF és FG öt maximális klikknek felel meg . A maximális klikk mérete három, ennek a fabontásnak a szélessége pedig kettő.

Ez az ekvivalencia az útszélesség és az intervallumvastagság között szoros analógia a faszélesség és a minimális klikkszám (mínusz egy) közötti ekvivalenciával egy akkordgráfban , amelynek az adott gráf részgráfja. Az intervallumgráfok az akkordgráfok speciális esetei, az akkordgráfok pedig általános fák részfa-metszéspont-gráfjaiként ábrázolhatók, ami általánosítja azt a megközelítést, amelyben az intervallumgráfokat út-alút metszéspont-gráfokként értelmezzük.

Vertex split summa

Tegyük fel, hogy a G gráf csúcsai lineárisan rendezettek . Ekkor G csúcspartíciójának nagysága az a legkisebb s szám , amelynek minden v csúcsához legfeljebb s olyan csúcs előzi meg v -t a sorrendben, amelynek v vagy a következő csúcsok egyike van a szomszédságában. A G gráf csúcsfelosztási értéke a G gráf bármely lineáris tetszőleges lineáris rendezésének minimális csúcsfelosztási értéke . A csúcsfelosztás értékét Ellis, Sudborough és Turner vezette be [15] , és megegyezik a G gráf útvonalszélességével [16] [17] . Ez következik az intervallumgráfok és a klikkszámok korábban említett ekvivalenciájából - ha G egy I intervallumgráf részgráfja, amelyet (mint az ábrán) úgy ábrázolunk, hogy az intervallumok minden vége különböző, akkor az intervallumok sorrendje Az I. gráf intervallumainak bal végei eggyel kisebb csúcselválasztási értékkel rendelkeznek, mint az I. oszlop klikkszámai . A másik irányban, G lineáris rendezéséből, olyan intervallumábrázolást kaphatunk, amelyben a v csúcs intervallumának bal végpontja a sorrendben lévő pozíció, a jobb oldali pedig v utolsó szomszédjának pozíciója a rendelés.

Vertex-keresési szám

A grafikonon a legjobban találó játék az üldözés-elkerülő játék egy fajtája , amelyben több üldöző együtt dolgozik, hogy felkutassák a grafikonon rejtőzködő szökevényt. Az üldözők a gráf csúcsaiban helyezkednek el, míg a szökevény a gráf bármely szélén elhelyezkedhet, elhelyezkedése és lépései nem láthatók az üldözők számára. A következő lépés során az üldözők egy része (vagy mindegyike) mozoghat (tetszőlegesen, nem feltétlenül élek mentén) az egyik csúcsból a másikba, és a szökevény ezután a gráf bármely útvonalán mozog, de nem tud áthaladni a gráf által elfoglalt csúcsokon. üldözők. A szökevényt akkor kapják el, amikor az ív mindkét végét üldözők foglalják el. A gráf csúcskeresési száma az üldözők minimális száma, amely a szökevény elfogásának garantálásához szükséges, függetlenül a viselkedésétől. Ahogy Kyrouzis és Panadimitriou [18] kimutatta , egy gráf csúcskeresési száma megegyezik az intervallumvastagságával. Az üldözők számára az optimális stratégia azok a lépések, amelyek során az üldözők egymás után, a minimális csúcselválasztással lineáris rendezettség elválasztó halmazokat alkotnak.

Szegélyek

Bármely n csúcsú és k útszélességű gráfnak legfeljebb k ( n − k + ( k − 1)/2)) éle van, és a maximális gráfoknak k útszélességű (gráfok, amelyekhez nem adható él hozzá az útvonal növelése nélkül szélesség) a pontosság az élek száma. A k útszélességű maximális gráfnak vagy k -útvonalnak vagy k -hernyónak kell lennie , azaz. a két speciális k -fa egyike. A k -fa egy akkordgráf, amely pontosan n − k maximális klikket tartalmaz, amelyek mindegyike k + 1 csúcsot tartalmaz. Egy olyan k - fában, amely önmagában nem ( k + 1)-klikk , minden maximális klikk vagy két vagy több komponensre osztja a gráfot, vagy egyetlen levélcsúcsot tartalmaz, egy olyan csúcsot, amely csak egy maximális klikkhez tartozik. A k -út egy k -fa legfeljebb két levelével, a k -hernyó pedig egy k -fa, amely felosztható egy k -útra és egy k -levél halmazra , amelyek mindegyike szomszédos a k-klikk elválasztóval. a k - útról . Konkrétan az első útszélesség maximális grafikonjai pontosan hernyógráfok [19] .

Mivel az útvonalbontások a fabontások speciális esetei, bármely gráf útvonalszélessége nagyobb vagy egyenlő, mint a fa szélessége . Az útvonal szélessége is kisebb vagy egyenlő, mint a vágásszélesség, vagyis azon élek minimális száma, amelyek az alacsonyabb indexű és magasabb indexű csúcsok közötti vágást metszik a gráf csúcsainak optimális lineáris sorrendjében. Ez abból következik, hogy a csúcsfelosztás nagysága, az alacsonyabb indexű csúcsok száma a magasabb indexű szomszédokkal, nem nagyobb, mint a vágóélek száma [20] [21] . Ugyanebből az okból kifolyólag a vágási szélesség nem haladja meg az adott gráf csúcsainak maximális fokával szorozva az útszélességet [22] [23] .

Minden n csúcsú  erdőnek O(log n ) [24] [25] [26] útvonala van . Egy erdő esetében mindig találhatunk állandó számú csúcsot, amelyek eltávolítása egy olyan erdőt eredményez, amely két kisebb, legfeljebb 2 n /3 csúcsú erdőre osztható fel . Az ilyen partíció rekurzív alkalmazásával létrehozott lineáris rendezésnek logaritmikus keresési száma van a csúcsokhoz. Ugyanez a technika egy gráf fabontásánál is azt mutatja, hogy ha egy n csúcsú G gráf faszélessége t , akkor G útszélessége O( t  log  n ) [27] [28] . Mivel a külső síkbeli gráfok , párhuzamos soros gráfok és Halin gráfok korlátos faszélességgel rendelkeznek, mindegyiküknek van egy maximális logaritmikus útszélessége.

Amellett, hogy a faszélességhez kapcsolódik, az útvonal szélessége a vonaldiagramokon keresztül kapcsolódik a kattintási és vágási szélességhez is . Egy G gráf L ( G ) vonalgráfjának van egy csúcsa G minden éléhez, és L ( G ) két csúcsa szomszédos, ha a megfelelő két élnek közös G végpontja van. Bármely gráfcsaládnak akkor és csak akkor van korlátos útszélessége, ha vonalgráfjainak lineáris klikkszélessége van korlátos, ahol a lineáris klikkszélesség a klikkszélesség definíciójában szereplő egyesülési műveletet egyetlen új csúcs csatolásának műveletével helyettesíti [29] . Ha egy három vagy több csúcsú összefüggő gráf maximális foka 3, akkor a vágási szélessége megegyezik a vonalgráf csúcsfelosztásával [30] .

Bármely síkgráfban az útvonal szélessége a legrosszabb esetben arányos a csúcsok számának négyzetgyökével [31] . Az ilyen szélességű útfelbontás egyik módja az, hogy (hasonlóan a fent leírt log-szélesség útbontáshoz) a síkbeli particionálási tétel segítségével keressük meg az O(√ n ) csúcsok halmazát, amelyek eltávolítása a gráfot két részgráfra osztja maximum 2 n /3 csúcs mindegyikben, és kösd össze a két részgráfhoz rekurzívan megszerkesztett útvonal-dekompozíciókat. Ugyanez a technika alkalmazható a gráfok bármely osztályára, amelyre egy hasonló particionálási tétel érvényes [32] . Mivel a minorok felvételére zárt gráfcsaládok bármelyike, mint a síkgráfok esetében, rendelkezik egy O(√ n ) [33] méretű felosztó csúcshalmazzal , ebből az következik, hogy a gráfok útszélessége bármely, a minorok alá zárt rögzített családban ismét O(√ n ). A síkgráfok egyes osztályainál a gráf útvonalának és duális gráfjának útszélességének egy olyan intervallumban kell lennie, amelynek határai lineárisan függenek az értékektől – ilyen határvonalak ismertek a kétszeresen összekapcsolt külső síkbeli gráfoknál [34] [35] és a politópnál. grafikonok [36] [37] . Kettős kapcsolatú síkgráfok esetén a duális gráf útszélessége kisebb, mint a vonalgráf [38] pályaszélessége . Nyitott kérdés marad, hogy a síkgráf és duális útszélességei a többi esetben mindig lineáris határvonalon vannak-e.

Egyes gráfosztályok esetében bebizonyosodott, hogy az útvonal és a faszélesség mindig egyenlő egymással - ez igaz a kográfokra [39] , a permutációs gráfokra [40] , az összehasonlíthatósági gráfok [41] komplementereire és az intervallumsorrendek összehasonlíthatósági gráfjaira [42] .

Megoldatlan problémák a matematikában : Mekkora a csúcsokkal rendelkező köbös gráf maximális útvonalszélessége ?

Bármely köbös gráfban , vagy általánosabban bármely gráfban, amelynek csúcsfoka legfeljebb 3, az útvonal szélessége legfeljebb n /6 + o( n ), ahol n a gráf csúcsainak száma. Léteznek 0,082 n útszélességű köbös gráfok , de nem ismert, hogyan lehet ezt a rést bezárni az alsó és az n /6 felső korlát között [43] .

Útvonal-dekompozíciók számítása

Annak meghatározása, hogy az útvonal szélessége túllép-e egy adott k értéket egy adott gráf esetében, NP-teljes , ha k egy bemenet [6] . A legismertebb időhatárok ( legrosszabb esetben ) egy tetszőleges, n csúcsú gráf útszélességének kiszámításához O(2 n  n c ) valamilyen c állandóra [44] . Egyes útvonalbontási algoritmusokról azonban ismert, hogy hatékonyabbak, ha az útvonal szélessége kicsi, ha a bemeneti gráfosztály korlátozott, vagy ha az útvonal szélességét közelíteni kell.

Rögzített paraméteres feloldhatóság

Az útszélesség fix-parametrikusan feloldható – bármely k konstans esetén ellenőrizhető, hogy a pályaszélesség meghaladja -e a k -t , és ha nem, akkor megkereshetjük a k szélesség lineáris időbeli útbontását [8] . Általában ezek az algoritmusok két szakaszban működnek. Az első lépés azt a feltevést használja, hogy a gráfnak k útszélessége van , hogy megtalálja az útvonal- vagy fadekompozíciót. Ez a bontás nem optimális, de a szélessége korlátozható k függvényével . A második lépésben egy dinamikus programozási algoritmust alkalmazunk az optimális dekompozíció megtalálására. Az ilyen típusú ismert algoritmusok időkorlátja azonban exponenciális k 2 -ben , és nincs gyakorlati jelentősége, kivéve talán a kis k értékeit [45] . A k  = 2 esetre Fleiter lineáris idő algoritmust adott, amely 2-es útszélességű gráfok strukturális dekompozícióján alapul [46] .

A gráfok speciális osztályai

Bodlaender [9] áttekintést adott az útvonalszélesség-problémák összetettségéről a különböző speciális gráfosztályokon. Annak meghatározása, hogy egy G gráf útszélessége meghaladja -e k -t, NP-teljes probléma marad, ha G - t korlátos fokú gráfokból [47] , síkgráfokból [47] , korlátos fokú síkgráfokból [47] , akkordgráfokból [48] vesszük , akkorddominók [49] , összehasonlíthatósági gráfok [41] komplementerei és bipartit távolság-örökölt gráfok [50] . Ez azonnal arra utal, hogy a probléma NP-teljes a kétrészes távolság öröklött gráfokat tartalmazó gráfcsaládok esetében is, beleértve a bipartit gráfokat, akkordális bipartit gráfokat, távolság öröklött gráfokat és körgráfokat [50] .

Az út szélessége azonban lineáris időben számítható fák és erdők esetében [10] . Ez az érték polinomidőben számítható ki korlátos faszélességű gráfokhoz, amelyek párhuzamos szekvenciális gráfokat , külső síkbeli gráfokat és Halin gráfokat [8] , valamint osztott gráfokat [51] [48] , akkordgráfok komplementereit tartalmaznak [ 52] , permutációs gráfok [40] , kográfok [39] , körív gráfok [53] , intervallumsorrend összehasonlíthatósági grafikonok [42] , és természetesen maguk az intervallumgráfok , mert ezeknél az útvonal szélessége egyszerűen eggyel kisebb, mint a maximális intervallum lefedettség az intervallumábrázolási grafikon bármely pontjának száma.

Közelítő algoritmusok

Egy NP-nehéz probléma egy gráf útszélességének additív állandóval való közelítése [7] . A polinomiális idő közelítési algoritmusok  legismertebb közelítési együtthatója az útszélességre O((log n ) 3/2 ) [54] . A korai útszélesség-közelítő algoritmusok megtalálhatók Bodlaender, Gilbert, Hafsteinsson, Klox [7] és Gooh [55] könyveiben . A korlátozott gráfosztályok közelítését lásd Clox és Bodlaender [51] könyvében .

Kiskorúak száma

A G gráf mollja egy másik gráf, amelyet G -ből élek összehúzásával, élek és csúcsok törlésével hozunk létre. A gráf minorok mély elmélettel rendelkeznek, amelyben néhány fontos eredmény elérési útvonalat használ.

Erdőkizárás

Ha az F gráfcsalád a kiskorúak felvételének művelete alatt zárva van (az F család bármely tagjának kiskorútja is benne van F ), akkor a Robertson–Seymour tétel alapján az F család olyan gráfokként jellemezhető, amelyek nem kiskorúakat tartalmaznak X -ből , ahol X a tiltott kiskorúak véges halmaza [56] . Például Wagner tétele kimondja, hogy a síkgráfok olyan gráfok, amelyek nem tartalmazzák mellékként sem a teljes K 5 gráfot, sem a K 3,3 teljes kétrészes gráfot . Sok esetben F tulajdonságai és X tulajdonságai szorosan összefüggenek, és ennek a típusnak az első eredményét Robertson és Seymour [2] kapta, és ez a korlátos útszélesség létezését egy erdő jelenlétével hozza összefüggésbe a tiltott kiskorúak családja. Pontosabban, egy F gráfcsaládot korlátos útvonalszélességűként határozunk meg, ha létezik olyan p konstans, hogy az F -beli bármely gráfnak legfeljebb p útszélessége van . Ekkor egy F kiskorú-zárt családnak akkor és csak akkor van korlátos útszélessége, ha az F tiltott kiskorúak X halmaza legalább egy erdőt tartalmaz.

Egy irányban ez az eredmény közvetlenül igazolható – nevezetesen, hogy ha X nem tartalmaz legalább egy erdőt, akkor az X -minormentes gráfoknak nincs korlátos útszélessége. Ebben az esetben az X -minor nélküli gráfok az összes erdőt, és különösen a tökéletes bináris fákat tartalmazzák . De a tökéletes bináris fák 2k  + 1 szinttel rendelkeznek k útszélességgel , tehát ebben az esetben az X -minor-mentes gráfok korlátlan útszélességgel rendelkeznek. Ellenkező irányban, ha X egy n csúcsú erdőt tartalmaz , akkor az X -minor-mentes gráfok útszélessége legfeljebb n  − 2 [57] [58] [59] .

Nyomtáv becslések

Az a tulajdonság, hogy az útszélesség legfeljebb p , önmagában egy mellékzárt tulajdonság – ha G -nek legfeljebb p szélességű útfelbontása van , akkor ugyanaz az útfelbontás igaz marad, ha G -ből eltávolítunk egy élt is. mint bármely csúcs eltávolítható G -ből és annak útfelbontásából a szélesség növelése nélkül. Egy élösszehúzódás a felbontás szélességének növelése nélkül is végrehajtható, ha összevonjuk a zsugorított él két végét reprezentáló részpályákat. Így a legfeljebb p útszélességű gráfok a tiltott kiskorúak X p halmazával jellemezhetők [56] [16] [60] [61] .

Bár X p szükségszerűen tartalmaz legalább egy erdőt, nem igaz, hogy X p minden gráfja erdő. Például X 1 két gráfból, egy hét csúcsú fából és egy K 3 háromszögből áll . Az X p -ben lévő fák halmaza azonban pontosan leírható - pontosan ezek azok a fák, amelyek X p  − 1 -ből három fából alakíthatók ki úgy, hogy új gyökeret képeznek, és azt élekkel összekötik kisebb fák tetszőlegesen kiválasztott csúcsaival. Például egy X 1 -ben hét csúcsú fa olyan fákból jön létre, amelyeknek X 0 -ból két csúcsa (egy éle) van . E konstrukció alapján kimutatható, hogy X p -ben a tiltott kiskorúak száma nem kevesebb, mint ( p !) 2 [16] [60] [61] . Kiszámításra került a 2-es útszélességű gráfok tiltott kiskorúak X 2 teljes halmaza . Ez a készlet 110 különböző grafikont tartalmaz [62] .

Strukturális elmélet

A kisebb zárt gráfok családjainak gráfszerkezeti tétele kimondja, hogy minden F családra, amelyben a gráfok klikkösszegekre bonthatók , olyan gráfok, amelyek beágyazhatók a korlátos nemzetség felületeibe korlátos számú csúcsokkal és örvényekkel együtt. a klikkösszeg összetevője . A csúcs az a csúcs, amely szomszédos az összetevő összes csúcsával, az örvény pedig egy korlátos útszélességű gráf, amelyet a komponens felületére ragasztunk a korlátos nemzetség befecskendezésével. Az örvény beágyazott felülete körüli csúcsok ciklikus sorrendjének összeegyeztethetőnek kell lennie az örvény fafelbontásával abban az értelemben, hogy a ciklus lineáris sorrend kialakításához történő megszakítása egy korlátozott mértékű csúcselválasztású sorrendet eredményez . 5] . Ennek az elméletnek, amelyben az útvonal szélessége szorosan összefügg tetszőleges, minor alá zárt gráfcsaládokkal, fontos algoritmikus alkalmazása [63] .

Alkalmazások

VLSI

A VLSI fejlesztése során a csúcsok felosztásának problémáját eredetileg úgy tanulmányozták, hogy a láncokat kisebb alrendszerekre bontsák fel, kevés komponenssel a rendszerek határán [47] .

Otsuki, Mori, Kuh és Kashiwabara [64] az intervallumvastagságot használta a szükséges vezetékek számának modellezésére a hálózati rendszerrel összekapcsolandó több modulból álló VLSI áramkörök egydimenziós elrendezésében. Modelljükben létrehozhatunk olyan gráfot, amelyben a csúcsok láncokat reprezentálnak, és amelyben két csúcsot egy él köt össze, ha láncaik ugyanahhoz a modulhoz kapcsolódnak. Vagyis ha a modulokat és láncokat a hipergráf csúcsaiként és hiperéleiként értjük , akkor a belőlük alkotott gráf egy hipergráf vonalgráfja . Ennek a vonalgráfnak a szupergráf intervallumábrázolása a szupergráf színezésével együtt leírja a hálók elrendezését vízszintes pályák mentén (minden színhez egy sáv), így a modulok lineáris sorrendben rendezhetők el a pályák mentén, és csatlakoztathatók a kívánt hálók. Abból, hogy az intervallumgráfok tökéletesek [65] , az következik, hogy az ilyen típusú optimális elrendezéshez szükséges színek száma megegyezik a láncgráf intervallum-komplementerének klikkszámával.

A kapcsolómátrix halmozás [66] a CMOS VLSI halmozás egy speciális fajtája logikai algebrai áramkörökhöz . A kapcsolók mátrixos halmozásánál a jel "vonalak" (függőleges szegmensek) mentén terjed, miközben minden kapcsolót egy vízszintes szegmensen elhelyezkedő elemsor alkotja. Így az egyes kapcsolókhoz tartozó vízszintes szegmenseknek metszniük kell a kapcsoló bemeneteként vagy kimeneteként szolgáló vonalak függőleges szegmenseit. Akárcsak az Otsuki, Mori, Kuha és Kashiwabara halmozásoknál [64] , ez a fajta halmozás, amely minimálisra csökkenti a függőleges vonalak számát, kiszámítható egy olyan gráf útvonalszélességének kiszámításával, amelynek csúcsai vonalak és egy sorpár tartozik élként egy kapcsoló [67 ] . Ugyanez az algoritmikus megközelítés használható a programozható logikai integrált áramkörök halmozási problémáinak modellezésére is [68] [69] .

Grafikonábrázolás

A Pathwidth számos gráfvizualizációs alkalmazással rendelkezik :

Fordító tervezés

Magas szintű programozási nyelvek fordításakor az útvonal szélessége felmerül a lineáris kód (vagyis a vezérlőlogika nélküli kód - átmenetek és hurkok) újrarendezésének problémájában oly módon, hogy a kódban kiszámított összes érték gépi regiszterekben legyen , és nem kényszerül ki a fő memóriába. Ebben az alkalmazásban a lefordított kód irányított aciklikus gráfként (DAG) van ábrázolva, amelyben a csúcsok a kód bemeneti értékeit és a kódon belüli műveletek eredményeként kiszámított értékeket képviselik. Ebben a NAG-ban az x csomóponttól az y csomópontig tartó él azt a tényt jelenti, hogy az x érték az y művelet egyik bemenete . A csúcsok topológiai rendezése ebben a NAG-ban a kód helyes rendezését jelenti, és a kód ebben a sorrendben történő végrehajtásához szükséges regiszterek számát a rendezés csúcsfelosztása adja meg [74] .

Egy gépben tetszőleges számú rögzített w számú regiszter esetén lineáris időben meghatározható, hogy egy lineáris kódrészlet átrendezhető-e úgy, hogy a kód legfeljebb w regisztert igényeljen. Ha egy topológiai rendezés csúcsszétválasztása legfeljebb w , akkor az összes rendezés között a csúcsok minimális elválasztása nem lehet nagyobb, ezért a fent leírt NAG orientáció figyelmen kívül hagyásával kialakított irányítatlan gráfok útszélessége legfeljebb w lehet . Ismert rögzített paraméterű, eldönthető útvonalszélesség-algoritmusokkal ellenőrizhető, hogy ez igaz-e, és ha igaz, akkor az irányítatlan gráfokhoz lineáris időben kereshetünk útvonalbontást, feltételezve, hogy w konstans. Ha megtaláltuk a fafelbontást, akkor a w szélességű topológiai sorrend (ha van) dinamikus programozással megkereshető, ismét lineáris időben [74] .

Nyelvtudomány

Karnai és Tutsa [75] leírta az útszélesség alkalmazását a természetes nyelvi feldolgozásban . Ebben az alkalmazásban a mondatok gráfokként vannak modellezve, ahol a csúcsok a szavakat, az élek pedig a szavak közötti kapcsolatokat jelentik. Például, ha egy melléknév módosít egy főnevet, akkor a gráfnak van egy éle a két szó között. Az emberi rövid távú memória korlátozott kapacitása miatt Miller [76] , Kornai és Tutsa azzal érvel, hogy ennek a gráfnak korlátozott útvonalszélességgel kell rendelkeznie (pontosabban azt állítják, hogy ez az útszélesség nem haladja meg a hatot), különben az emberek nem lennének képesek hogy helyesen ismerje fel a beszédet.

Exponenciális algoritmusok

Számos gráfelméleti probléma hatékonyan megoldható kis útvonalszélességű gráfokon dinamikus programozással , a gráf útvonalbontása alapján [11] . Például, ha egy n csúcsú G gráf csúcsainak lineáris sorrendje adott , és a csúcsok szétválasztási értéke egyenlő w -vel , akkor meg lehet találni a G gráf legnagyobb független halmazát az O(2 w n ) függvényben. idő [43] . Korlátozott útvonalszélességű gráfon ez a megközelítés fix-parametrikusan eldönthető, útvonalszélesség-paraméterezett algoritmusokhoz vezet [67] . Ilyen eredményeket nem gyakran találunk a szakirodalomban, mivel ezek a hasonló faszélesség-paraméterezett algoritmusok csoportjába tartoznak. Az útvonalszélesség azonban még a faszélesség-alapú dinamikus programozási algoritmusokban is megjelenik, amikor ezeknek az algoritmusoknak a kapacitásbonyolultságát mérik [12] .

Ugyanez a dinamikus programozási technika alkalmazható korlátlan útvonalszélességű gráfokhoz, ami olyan algoritmusokhoz vezet, amelyek exponenciális idő alatt oldják meg a gráfok nem paraméterezett problémáit . Például, ha a dinamikus programozási megközelítést kombináljuk azzal a ténnyel, hogy a kocka gráfok útszélessége n /6 + o( n ) azt mutatja, hogy a köbös gráfok esetében a maximális független halmaz építhető fel O(2 n /6 + o( n ) függvényben. ) idő.amely gyorsabb a korábban ismert módszereknél [43] . Egy hasonló megközelítés javított exponenciális idő algoritmusokhoz vezet a maximális vágási és minimális domináns halmazproblémákhoz köbös gráfok [43] és néhány más NP-nehéz optimalizálási probléma [77] [78] esetén .

Lásd még

Jegyzetek

  1. ↑ Diestel, Kühn, 2005 .
  2. ↑ 1 2 3 4 5 Robertson, Seymour, 1983 .
  3. ↑ 1 2 Bodlaender, 1998 .
  4. ↑ A cikkben használt kifejezések közül sok megtalálható F. V. Fomin disszertációjának bevezetőjében (( Fomin 1996 ))
  5. ↑ 12 Robertson , Seymour, 2003 .
  6. ↑ 1 2 Kashiwabara, Fujisawa, 1979 ; Ohtsuki, Mori, Kuh, Kashiwabara, Fujisawa, 1979 ; Lengauer 1981 ; Arnborg, Corneil, Proskurowski, 1987 .
  7. ↑ 1 2 3 Bodlaender, Gilbert, Hafsteinsson, Kloks, 1992 .
  8. ↑ 1 2 3 Bodlaender (1996 ); Bodlaender, Kloks (1996 )
  9. ↑ 1 2 Bodlaender, 1994 .
  10. ↑ 12 Möhring , 1990 ; Scheffler, 1990 ; Ellis, Sudborough, Turner, 1994 ; Coudert, Huc, Mazauric, 1998 ; Peng, Ho, Hsu, Ko, Tang, 1998 ; Skodinis, 2000 ; Skodinis (2003 ).
  11. ↑ Arnborg 12. , 1985 .
  12. ↑ 1 2 Aspvall, Proskurowski, Telle, 2000 .
  13. ↑ Bodlaender, 1994 , p. 1–2.
  14. ↑ Bodlaender, 1998 , p. 13, 29. tétel.
  15. ↑ Ellis, Sudborough, Turner, 1983 .
  16. ↑ 1 2 3 Kinnersley, 1992 .
  17. ↑ Bodlaender, 1998 , p. 51. tétel.
  18. ↑ Kirousis, Papadimitriou, 1985 .
  19. ↑ Proskurowski, Telle, 1999 .
  20. ↑ Korach, Solel, 1993 , p. 99, 3. lemma.
  21. ↑ Bodlaender, 1998 , p. 24, 47. tétel.
  22. ↑ Korach, Solel, 1993 , p. 99, 1. lemma.
  23. ↑ Bodlaender, 1998 , p. 24, 49. tétel.
  24. ↑ Korach, Solel, 1993 , p. 99, 5. tétel.
  25. ↑ Bodlaender, 1998 , p. 30, 66. tétel.
  26. ↑ Scheffler (1992 ) erősebb korlátot ad egy n csúcsú erdő log 3 (2 n  + 1) útszélességére.
  27. ↑ Korach, Solel, 1993 , p. 100, 6. tétel.
  28. ↑ Bodlaender, 1998 , p. 10. Következmény 24.
  29. ↑ Gurski, Wanke, 2007 .
  30. ↑ Golovach, 1993 .
  31. ↑ Bodlaender, 1998 , p. 10. Következmény 23.
  32. ↑ Bodlaender, 1998 , p. 9, 20. tétel.
  33. ↑ Alon, Seymour, Thomas, 1990 .
  34. ↑ Bodlaender, Fomin, 2002 .
  35. ↑ Coudert, Huc, Sereni, 2007 .
  36. ↑ Fomin, Thilikos, 2007 .
  37. ↑ Amini, Huc, Perennes, 2009 .
  38. ↑ Fomin, 2003 .
  39. ↑ 1 2 Bodlaender, Möhring, 1990 .
  40. ↑ 1 2 Bodlaender, Kloks, Kratsch, 1993 .
  41. ↑ 1 2 Habib, Möhring, 1994 .
  42. ↑ Garbe 12 , 1995 .
  43. ↑ 1 2 3 4 Fomin, Høie, 2006 .
  44. ↑ Fomin, Kratsch, Todinca, Villanger, 2008 .
  45. ↑ Downey, Fellows, 1999 , p. 12.
  46. ↑ de Fluiter, 1997 .
  47. ↑ 1 2 3 4 Monien, Sudborough, 1988 .
  48. ↑ 1993. Gusted 12 .
  49. ↑ Kloks, Kratsch, Müller, 1995 . Az akkorddominó egy akkordgráf, amelyben bármely csúcs legfeljebb két maximális klikkhez tartozik
  50. ↑ 1 2 Kloks, Bodlaender, Müller, Kratsch, 1993 .
  51. ↑ 1 2 Kloks, Bodlaender, 1992 .
  52. ↑ Garbe (1995 ) ezt az eredményt Ton Clox 1993-as disszertációjának tulajdonítja. Garbe polinomiális idő algoritmusa az intervallumrendezések összehasonlíthatósági gráfjaihoz általánosítja ezt az eredményt, mivel minden akkordgráfnak ilyen típusú összehasonlítási gráfnak kell lennie.
  53. ↑ Suchan, Todinca, 2007 .
  54. ↑ Feige, Hajiaghayi, Lee, 2005 .
  55. ↑ Guha, 2000 .
  56. ↑ 12 Robertson , Seymour, 2004 .
  57. ↑ Bienstock, Robertson, Seymour, Thomas, 1991 .
  58. ↑ Diestel, 1995 .
  59. ↑ Cattell, Dinneen, Fellows, 1996 .
  60. ↑ 1 2 Takahashi, Ueno, Kajitani, 1994 .
  61. ↑ 1 2 Bodlaender, 1998 , p. nyolc.
  62. ↑ Kinnersley, Langston, 1994 .
  63. ↑ Demaine, Hajiaghayi, Kawarabayashi, 2005 .
  64. ↑ 1 2 Ohtsuki, Mori, Kuh, Kashiwabara, Fujisawa, 1979 .
  65. ↑ Berge, 1967 .
  66. ↑ Lopez, Law, 1980 .
  67. ↑ 12 Fellows , Langston, 1989 .
  68. ↑ Möhring, 1990 .
  69. ↑ Ferreira, Song, 1992 .
  70. ↑ Hlineny, 2003 .
  71. ↑ Suderman, 2004 .
  72. ↑ Dujmović, Fellows, Kitching et al., 2008 .
  73. ↑ Dujmovic, Morin, Wood, 2003 .
  74. ↑ 1 2 Bodlaender, Gustedt, Telle, 1998 .
  75. ↑ Kornai, Tuza, 1992 .
  76. ↑ Miller, 1956 .
  77. ↑ Kneis, Mölle, Richter, Rossmanith, 2005 .
  78. ↑ Björklund, Husfeldt, 2008 .

Irodalom