Kattintson a probléma

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. november 27-én felülvizsgált verziótól ; az ellenőrzések 4 szerkesztést igényelnek .

A klikk probléma a gráfelmélet területén az NP-teljes problémák osztályába tartozik . Először Richard Karp fogalmazta meg 1972-ben . [egy]

Az irányítatlan gráfban a klikk csúcsok részhalmaza, amelyek mindegyikét a gráf egy éle köti össze. Más szóval, ez az eredeti gráf teljes részgráfja . A klikk méretét a benne lévő csúcsok számaként határozzuk meg. A klikk probléma két változatban létezik: a felismerési feladatban meg kell határozni, hogy van-e k méretű klikk egy adott G gráfban , míg egy számítási változatban meg kell találni egymaximális méretű klikket egy adott G gráfban. adott G gráf.

NP-teljes

A klikk probléma NP-teljessége a független csúcshalmaz probléma NP-teljességéből következik. Könnyen kimutatható, hogy a k méretű klikk létezésének szükséges és elégséges feltétele egy legalább k méretű független halmaz jelenléte a gráf komplementerében. Ez nyilvánvaló, hiszen egy részgráf teljessége azt jelenti, hogy a komplementere nem tartalmaz éleket.

Az NP-teljesség másik bizonyítéka az Algoritmusok: Konstrukció és elemzés című könyvben található. [2]

Algoritmusok

Ami a többi NP-teljes problémát illeti, még nem találtak hatékony algoritmust egy adott méretű klikk megtalálására. Az összes lehetséges k méretű részgráf kimerítő keresése , annak ellenőrzése, hogy legalább az egyik teljes-e, nem hatékony, mivel az ilyen részgráfok száma egy v csúcsú gráfban megegyezik a binomiális együtthatóval . ${v \choose k} = \frac{v!}{k!(vk)!}.$

Egy másik algoritmus a következőképpen működik: két n és m méretű klikket "összeragasztunk" egy nagy, n + m méretű klikkbe, és a gráf különálló csúcsa egy 1 méretű klikket feltételez. Az algoritmus leáll, amint már nem lehet több egyesítést végrehajtani. Ennek az algoritmusnak a futási ideje lineáris, de heurisztikus , mivel nem mindig vezet a maximális méretű klikk megtalálásához. Sikertelen befejezésre példa az az eset, amikor a maximális klikkhez tartozó csúcsok szétválnak és kisebb klikkekben vannak, és az utóbbiakat már nem lehet „összeragasztani”.

Bebizonyosodott, hogy a P és NP osztályok egyenlőtlenségének feltétele mellett nincs olyan polinomiális közelítési algoritmus , amelynek abszolút hibája tetszőleges . Tekintsünk egy u gráfot – egy gráf és egy méretklikk közvetlen szorzata . Nyilvánvaló, hogy a grafikon klikkszáma egyenlő lesz . Tegyük fel, hogy van egy közelítő algoritmus , amelynek abszolút hibája egyenlő . Ezután betápláljuk a gráfot bemenetként , és a feltétel mellett megkapjuk a . Legyenek olyan grafikonok klikkjei , ahol . Jegyezzük fel az egyenlőtlenség érvényességét, és cseréljük be a fenti egyenlőtlenségbe a következőképpen: . A transzformáció után megkapjuk a -t , ami azt jelenti, hogy létezik olyan, amely és ezért a klikkfeladat polinomiális időben megoldható, ami ellentmond a P és NP osztályok egyenlőtlenségi feltételének. $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}$ $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$ $én$ $C_{i}=\omega (G)$

Lásd még

Bron-Kerbosh algoritmus - az összes klikk gyors megtalálása

Jegyzetek

↑ Karp, Richard (1972). „Csökkenthetőség a kombinatorikus problémák között” (PDF) . A számítógépes számítások összetettségéről szóló szimpózium előadásai . Plenum Press. Archivált az eredetiből (PDF) ekkor: 2011-06-29 . Letöltve: 2010-03-21 . Elavult használt paraméter |deadlink=( súgó )
↑ Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algorithms: construction and analysis = Introduction to Algorithms / Szerk. I. V. Krasikova. - 2. kiadás - M. : Williams, 2005. - 1296 p. — ISBN 5-8459-0857-4 .

Irodalom

Cook, Stephen A. (1971). „A tételbizonyítási eljárások bonyolultsága” . Proceedings of the Third Annual ACM Symposium on Theory of Computing . Shaker Heights, Ohio. pp. 151–158. Archiválva az eredetiből , ekkor: 2006-05-03 . Letöltve: 2007-06-11 . Elavult használt paraméter |deadlink=( súgó ) Archiválva : 2006. május 3. a Wayback Machine -nél
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, pg.194.

Linkek

Kihívást jelentő mércék a maximális kattintáshoz, a maximális független készlethez, a minimális csúcsfedéshez és a csúcsszínezéshez

NP-teljes problémák
A halmozás (csomagolás) maximalizálási problémája	Csomagolás konténerekbe kétdimenziós csomagolás lineáris csomagolás súly szerinti csomagolás érték szerinti csomagolás A hátizsák probléma
gráfelmélet halmazelmélet	Csúcsborítási probléma Kattintson a probléma Egy független halmaz (halmaz) problémája Állítsa be a fedési problémát Steiner probléma Az utazó eladó probléma Általános utazó eladó probléma
Algoritmikus problémák	Kielégíthetőségi probléma Boole-képleteknél (konjunktív normál formában)
Logikai játékok és rejtvények	Általános címkék (játék N 2 -1-ben) legrövidebb megoldási probléma Problémák, amelyek megoldásait a Tetrisben alkalmazzák Általános Sudoku probléma Latin négyzet kitöltési probléma Kakuro feladata
Nehézségi osztályok Operációkutatás Optimalizálás Kombinatorikus optimalizálás Alkalmazott matematika Algoritmusok elmélete Dinamikus programozás 21 NP-teljes Karp probléma