Napsauta ongelma

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 27. marraskuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 4 muokkausta .

Klikkiongelma kuuluu NP-täydellisten ongelmien luokkaan graafiteorian alalla . Sen muotoili ensimmäisen kerran vuonna 1972 Richard Karp . [yksi]

Klikki ohjaamattomassa graafissa on osajoukko pisteitä, joista kukin kaksi on yhdistetty graafin reunalla. Toisin sanoen se onalkuperäisen kaavion täydellinen aligraafi . Klikin koko määritellään siinä olevien kärkien lukumääränä. Klikkiongelma on olemassa kahdessa versiossa: tunnistusongelmassa on määritettävä, onko tietyssä graafissa G kooltaan k klikkia , kun taas laskennallisessa muunnelmassa on löydettävämaksimikokoinen klikki annettu graafi G.

NP-täydellinen

Klikkitehtävän NP-täydellisyys seuraa riippumattoman kärkijoukon ongelman NP-täydellisyydestä. On helppo osoittaa, että välttämätön ja riittävä ehto k-koon klikin olemassaololle on vähintään k -koon riippumattoman joukon läsnäolo graafin komplementissa. Tämä on ilmeistä, koska aligraafin täydellisyys tarkoittaa, että sen komplementti ei sisällä reunoja.

Toinen todiste NP-täydellisyydestä löytyy julkaisusta Algorithms: Construction and Analysis. [2]

Algoritmit

Mitä tulee muihin NP-täydellisiin ongelmiin, tehokasta algoritmia tietyn kokoisen klikkin löytämiseksi ei ole vielä löydetty. Kaikkien mahdollisten k koon aligraafien tyhjentävä haku , jossa tarkistetaan, onko ainakin yksi niistä valmis, on tehotonta, koska tällaisten alagraafien kokonaismäärä v -pisteellä varustetussa graafissa on yhtä suuri kuin binomikerroin. ${v \choose k} = \frac{v!}{k!(vk)!}.$

Toinen algoritmi toimii näin: kaksi n- ja m -kokoista klikkia "liimataan" suureksi koon n + m -klikiksi, ja graafin erilliseksi kärjeksi oletetaan olevan koon 1 klikki. Algoritmi päättyy heti, kun yhdistämistä ei voida enää tehdä. Tämän algoritmin ajoaika on lineaarinen, mutta se on heuristinen , koska se ei aina johda maksimikokoisen klikkin löytämiseen. Esimerkki epäonnistuneesta valmistumisesta on tapaus, jossa maksimiklikkiin kuuluvat kärjet erotetaan toisistaan ja ovat pienemmissä klikeissä, eikä jälkimmäisiä voida enää "liimata" yhteen.

On osoitettu, että luokkien P ja NP epäyhtälössä ei ole polynomin approksimaatioalgoritmia, jonka absoluuttinen virhe on yhtä suuri kuin mielivaltainen . Tarkastellaan kuvaajaa u - graafin ja koon klikkin suora tulo . Ilmeisesti kaavion klikkausluku on yhtä suuri kuin . Oletetaan, että on olemassa approksimaatioalgoritmi , jonka absoluuttinen virhe on yhtä suuri kuin . Sitten syötämme kaavion syötteeksi ja ehdolla saamme . Antaa olla klikejä kaavioiden muodossa , jossa . Huomioi epäyhtälön pätevyys ja korvaa se yllä olevalla epäyhtälöllä seuraavasti: . Muunnoksen jälkeen saadaan , mikä tarkoittaa, että on olemassa sellainen, että ja siksi klikkiongelma on ratkaistavissa polynomiajassa, mikä on ristiriidassa luokkien P ja NP epäyhtälöehdon kanssa. $k\in {\mathbb {N}}$ $G$ ${\displaystyle G^{k}=G\times C_{k))$ $G$ $C_{k}$ $k$ ${\displaystyle G^{k))$ $\omega (G^{k})=\omega (G)\cdot k$ $A$ $k\in {\mathbb {N}}$ $A$ $G^{k+1}$ $OPT\leqslant A(I)+k$ $\omega (G^{k+1})-A(G^{k+1})=(k+1)\cdot \omega (G)-A(G^{k+1})\ leqslant k$ $C_{i}$ ${\displaystyle G^{i))$ $1\leqslant i\leqslant k+1$ $C_{i}\leqslant \omega (G)$ $(k+1)\cdot \omega (G)-\sum _{i=1}^{k+1}|C_{i}|\leqslant k$ $\sum _{i=1}^{k+1}\omega (G)-|C_{i}|\leqslant k$ $i$ $C_{i}=\omega (G)$

Katso myös

Bron-Kerbosh-algoritmi - kaikkien klikkien nopea etsintä

Muistiinpanot

↑ Karp, Richard (1972). "Reducibility among Combinatorical Problems" (PDF) . Proceedings of Symposium on the Complexity of Computer Computations . Plenum Press. Arkistoitu alkuperäisestä (PDF) 29.06.2011 . Haettu 21.03.2010 . Käytöstä poistettu parametri |deadlink=( ohje )
↑ Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmit: rakentaminen ja analyysi = Introduction to Algorithms / Ed. I. V. Krasikova. - 2. painos - M .: Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 .

Kirjallisuus

Cook, Stephen A. (1971). "Lauheiden todistamismenettelyjen monimutkaisuus" . Proceedings of Third Annual ACM Symposium on Theory of Computing . Shaker Heights, Ohio. s. 151-158. Arkistoitu alkuperäisestä 2006-05-03 . Haettu 11.6.2007 . Käytöstä poistettu parametri |deadlink=( ohje ) Arkistoitu 3. toukokuuta 2006 Wayback Machinessa
Garey, Michael R. & Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , W. H. Freeman, ISBN 0-7167-1045-5 A1.2: GT19, s. 194.

Linkit

Haastavat vertailuarvot maksimaaliselle klikkaukselle, suurimmalle itsenäiselle sarjalle, minimivertex-peitteelle ja värjäyspisteille

NP-täydellisiä ongelmia
Pinoamisen (pakkauksen) maksimointiongelma	Pakkaus säiliöihin kaksiulotteinen pakkaus lineaarinen pakkaus pakkaus painon mukaan pakkaus arvon mukaan Reppu ongelma
graafiteorian joukkoteoria	Vertex-kannen ongelma Napsauta ongelma Itsenäisen joukon (joukon) ongelma Aseta peittoongelma Steinerin ongelma Matkamyyjän ongelma Yleinen matkamyyjän ongelma
Algoritmiset ongelmat	Boolen kaavojen tyydyttävyysongelma (konjunktiivisessa normaalimuodossa)
Logiikkapelejä ja pulmia	Yleiset tunnisteet (peli N 2 -1:ssä) lyhin ratkaisu ongelma Ongelmat, joiden ratkaisuja käytetään Tetrisissä Yleistynyt Sudoku-ongelma Latinalaisen neliön täyttöongelma Kakuron tehtävä
Vaikeusluokat Toimintatutkimus Optimointi Kombinatorinen optimointi Sovellettu matematiikka Algoritmien teoria Dynaaminen ohjelmointi 21 NP-täydellinen Karp-ongelma