Napsauta Leveys

Graafiteoriassa graafin klikin leveys  on parametri, joka kuvaa graafin rakenteellista monimutkaisuutta . Parametri liittyy läheisesti puunleveyteen , mutta toisin kuin puunleveys, klikin leveyttä voidaan rajoittaa jopa tiheissä kaavioissa . Napsautusleveys määritellään tarrojen vähimmäismääräksi, joka tarvitaan luomaan seuraavat 4 toimintoa

  1. Uuden kärjen v luominen tunnisteella i ( i(v) -toiminto )
  2. Kahden merkittyjen kaavioiden G ja H irrotettu liitto (toiminto )
  3. Jokaisen merkinnällä i varustetun kärjen reunayhteys kuhunkin tunnisteella j varustettuun kärkeen (operaatio η(i, j) ), jossa
  4. Nimeä nimiö i uudelleen muotoon j (operaatio ρ ( i , j ))

Rajoitettuihin klikkinleveyskaavioihin kuuluvat kopiot ja etäisyyden periytyneet kaaviot . Vaikka klikkin leveyden laskeminen on NP-kovaa , koska ylärajaa ei tunneta eikä tiedetä, voidaanko se laskea polynomiajassa, kun yläraja tunnetaan, tehokkaat approksimaatioalgoritmit klikkin leveyden laskemiseen tunnetaan. Näiden algoritmien ja Courcellen lauseen perusteella monet optimointiongelmat kaavioissa, jotka ovat NP-kovia mielivaltaisille kaavioille, voidaan ratkaista tai approksimoida nopeasti graafisille, joilla on rajoitettu klikkin leveys.

Rakennussekvenssit, joihin klikkin leveyden käsite perustuu, muotoilivat Courcelle, Engelfried ja Rosenberg vuonna 1990 [1] ja Vanke [2] . Khlebikov [3] käytti nimeä "napsautusleveys" toisesta käsitteestä . Vuodesta 1993 lähtien termiä on käytetty sen nykyisessä merkityksessä [4] .

Graafeiden erikoisluokat

Kuvaajat ovat täsmälleen kaavioita, joiden klikkin  leveys on enintään kaksi [5] . Minkä tahansa etäisyyden periytyvän graafin klikkin leveys on enintään 3. Intervallikaavioiden klikkin leveyttä ei kuitenkaan ole rajoitettu (hilarakenteen mukaan) [6] . Vastaavasti kaksiosaisten permutaatiograafien klikkin leveyttä ei ole rajoitettu (samanlaisen hilarakenteen mukaan) [7] . Perustuen kuvaukseen graafit ilman generoituja aligraafia, jotka ovat isomorfisia poluille ilman sointuja, useiden kiellettyjen generoitujen aligraafien määrittelemien graafiluokkien klikin leveys luokiteltiin [8] [9] .

Muut graafit, joilla on rajattu klikkin leveys, ovat k - lehtien potenssit k rajatuille arvoille , eli puun T lehtien generoidut osagraafit graafin T k asteeseen . Rajattoman eksponentin omaavien lehtien asteella ei kuitenkaan ole rajoitettua lehtileveyttä [10] [11] .

Reunat

Courcelle ja Olariu [5] sekä Corneil ja Rotix [12] antoivat seuraavat rajat joidenkin graafien klikin leveydelle:

Lisäksi, jos graafin G klikkin leveys k , niin graafin G c asteella on klikkin leveys enintään 2 kc k [18] . Vaikka klikin leveysepäyhtälöissä on eksponentiaalinen vertailu puun leveyden ja graafin asteen kanssa, nämä rajat eivät anna superpositiota - jos graafin G puun leveys on w , niin G c :n klikkin leveys on enintään 2( c + 1) w + 1 − 2 , vain puun leveyden yksinkertainen eksponentti [11] .

Laskennallinen monimutkaisuus

Ratkaisemattomat matematiikan ongelmat : Voiko graafin, jolla on rajoitettu klikkin leveys, tunnistaa polynomiajassa?

Monet optimointiongelmat, jotka ovat NP-vaikeita yleisemmille graafiluokille, voidaan ratkaista tehokkaasti käyttämällä dynaamista ohjelmointia graafisille, joilla on rajoitettu klikinleveys, jos näiden kuvaajien konstruointijärjestys tunnetaan [19] [20] . Erityisesti kaikilla graafiinvariantilla , joka voidaan ilmaista MSO 1 :ssä ( yksipaikkainen toisen asteen logiikka , eräänlainen toisen kertaluvun logiikka, joka sallii kvantisoijat pistejoukkojen yli) sisältää lineaarisen aika-algoritmin rajatulle leveydelle. kaavioita yhdellä Courcellen lauseen [20] formulaatioista . Rajoitetun klikinleveyden graafien optimaaliset värjäykset tai Hamiltonin syklit voidaan löytää myös polynomiajassa, jos graafin rakennussekvenssi tunnetaan, mutta polynomin aste kasvaa klikkin leveyden mukana, ja laskennallisen kompleksisuusteorian argumentit osoittavat, että tällainen riippuvuus näyttää olevan olla väistämätön [21] .

Graafit, joiden klikin leveys on kolme, voidaan tunnistaa ja niiden konstruointijärjestys voidaan löytää polynomiajassa käyttämällä split-dekompositioon perustuvaa algoritmia [22] . Graafiluokille, joilla on rajoittamaton klikkin leveys, tarkan klikkin leveyden laskeminen on NP-kovaa , ja on myös NP-vaikea saada approksimaatio sublineaarisella additiivisella virheellä [23] . Jos klikkin leveyden yläraja on kuitenkin tiedossa, on mahdollista saada graafin rakennussekvenssi, jonka leveys on rajoitettu (eksponentiaalisesti suurempi kuin todellinen klikkin leveys) polynomiajassa [17] [24] [25] . Jää avoimeksi kysymykseksi, voidaanko tarkka klikin leveys tai läheinen approksimaatio laskea kiinteässä parametrisesti erotettavissa ajassa, voidaanko se laskea polynomiajassa graafisille, joilla on mikä tahansa kiinteän klikkin leveyden rajoitus, tai jopa, voidaanko klikin leveydellä varustettuja kuvaajia laskea. Leveys neljä tunnistetaan polynomiajassa [23] .

Linkki puun leveyteen

Rajoitetun klikkinleveyden graafiteorialla on yhtäläisyyksiä rajoitetun puunleveyden graafiteorian kanssa, mutta toisin kuin puunleveys, se sallii tiheät kuvaajat . Jos graafiperheellä on rajattu klikkin leveys, sillä on joko rajattu puunleveys tai mikä tahansa täydellinen kaksiosainen graafi on jonkin perheen graafin aligraafi [16] . Puun leveys ja klikkin leveys liittyvät myös viivagraafiteoriaan  – graafiperheellä on rajallinen puun leveys silloin ja vain, jos niiden viivakaavioilla on rajattu klikkin leveys [26] .

Muistiinpanot

  1. ↑ Courcelle, Engelfriet, Rozenberg, 1993 .
  2. ↑ Wanke, 1994 .
  3. ↑ Chlebíková, 1992 .
  4. ↑ Courcelle, 1993 .
  5. ↑ 12 Courcelle, Olariu, 2000 .
  6. ↑ Golumbic, Rotics, 2000 .
  7. ↑ Brandstädt, Lozin, 2003 .
  8. ↑ Brandstädt, Dragan, Le, Mosca, 2005 .
  9. ↑ Brandstädt, Engelfriet, Le, Lozin, 2006 .
  10. ↑ Brandstädt, Hundt, 2008 .
  11. ↑ 12 Gurski , Wanke, 2009 .
  12. ↑ Corneil, Rotics, 2005 .
  13. ↑ Courcelle, Olariu, 2000 , s. Seuraus 3.3.
  14. ↑ Courcelle, Olariu, 2000 , s. Lause 4.1.
  15. ↑ Corneil, Rotics, 2005 , Vahvistaminen - Courcelle, Olariu, 2000 , Lause 5.5.
  16. ↑ 12 Gurski , Wanke, 2000 .
  17. ↑ 12 Oum , Seymour, 2006 .
  18. ↑ Todinca, 2003 .
  19. ↑ Cogis, Thierry, 2005 .
  20. ↑ 12 Courcelle, Makowsky, Rotics, 2000 .
  21. ↑ Fomin, Golovach, Lokshtanov, Saurabh, 2010 .
  22. ↑ Corneil et al, 2012 .
  23. ↑ 1 2 Fellows, Rosamond, Rotics, Szeider, 2009 .
  24. ↑ Hliněny, Oum, 2008 .
  25. ↑ Oho, 2009 .
  26. ↑ Gurski, Wanke, 2007 .

Kirjallisuus