Klik problem

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 27. november 2019; checks kræver 4 redigeringer .

Klikeproblemet hører til klassen af NP-komplette problemer inden for grafteori . Den blev først formuleret i 1972 af Richard Karp . [en]

En klike i en urettet graf er en delmængde af hjørner, som hver to er forbundet med en kant af grafen. Det er med andre ord en komplet undergraf af den originale graf. Klikstørrelsen er defineret som antallet af hjørner i den. Klikeproblemet findes i to versioner: I genkendelsesproblemet kræves det at bestemme, om der er enklike af størrelsen k i en given graf G , mens det i en beregningsvariant kræves at finde enklike med maksimal størrelse i en givet graf G.

NP-komplet

NP-fuldstændigheden af klikeproblemet følger af NP-fuldstændigheden af det uafhængige vertexsætproblem. Det er let at vise, at en nødvendig og tilstrækkelig betingelse for eksistensen af en klike af størrelse k er tilstedeværelsen af et uafhængigt sæt af størrelse mindst k i komplementet af grafen. Dette er indlysende, da fuldstændigheden af en undergraf betyder, at dens komplement ikke indeholder nogen kanter.

Et andet bevis på NP-fuldstændighed kan findes i Algorithms: Construction and Analysis. [2]

Algoritmer

Hvad angår andre NP-komplette problemer, er der endnu ikke fundet en effektiv algoritme til at finde en klike af en given størrelse. En udtømmende søgning af alle mulige undergrafer af størrelsen k , der kontrollerer, om mindst én af dem er fuldstændig, er ineffektiv, da det samlede antal af sådanne undergrafer i en graf med v hjørner er lig med den binomiale koefficient ${v \choose k} = \frac{v!}{k!(vk)!}.$

En anden algoritme fungerer således: to kliker af størrelse n og m "limes" ind i en stor klik med størrelse n + m , og et separat toppunkt på grafen antages at være en klik på størrelse 1 . Algoritmen afsluttes, så snart der ikke kan foretages flere fletninger. Køretiden for denne algoritme er lineær, men den er heuristisk , da den ikke altid fører til at finde en klike af den maksimale størrelse. Et eksempel på en mislykket afslutning er tilfældet, når de hjørner, der hører til den maksimale klike, er adskilt og er i mindre kliker, og sidstnævnte ikke længere kan "limes" sammen.

Det er bevist, at der under betingelse af ulighed mellem klasserne P og NP , er der ingen polynomial tilnærmelsesalgoritme med absolut fejl lig med vilkårlig . Betragt en graf u - det direkte produkt af en graf og en klike af størrelse . Det er klart, at grafens kliknummer vil være lig med . Antag, at der er en tilnærmelsesalgoritme med en absolut fejl lig med . Så fodrer vi grafen som input , og under betingelsen får vi . Lade være kliker af grafer af formen , hvor . Bemærk gyldigheden af uligheden og indsæt den i ovenstående ulighed som følger: . Efter transformationen får vi , hvilket betyder, at der eksisterer sådan, at og derfor er klikproblemet løseligt i polynomisk tid, hvilket modsiger ulighedsbetingelsen for klasserne P og NP. $k\in {\mathbb {N}}$ $G$ ${\displaystyle G^{k}=G\ gange C_{k))$ $G$ $C_{k}$ $k$ ${\displaystyle G^{k))$ $\omega (G^{k})=\omega (G)\cdot k$ $EN$ $k\in {\mathbb {N}}$ $EN$ $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$ $jeg$ $C_{i}=\omega (G)$

Se også

Bron-Kerbosh algoritme - hurtig søgning af alle kliker

Noter

↑ Karp, Richard (1972). "Reducerbarhed blandt kombinatoriske problemer" (PDF) . Proceedings of a Symposium on the Complexity of Computer Computations . Plenum Press. Arkiveret fra originalen (PDF) 2011-06-29 . Hentet 2010-03-21 . Forældet parameter brugt |deadlink=( hjælp )
↑ Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmer: konstruktion og analyse = Introduktion til algoritmer / Ed. I. V. Krasikova. - 2. udg. - M. : Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 .

Litteratur

Cook, Stephen A. (1971). "Kompleksiteten af teorembevisende procedurer" . Proceedings of the Third Annual ACM Symposium on Theory of Computing . Shaker Heights, Ohio. pp. 151-158. Arkiveret fra originalen 2006-05-03 . Hentet 2007-06-11 . Forældet parameter brugt |deadlink=( hjælp ) Arkiveret 3. maj 2006 på Wayback Machine
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.

Links

Udfordrende benchmarks for maksimal klike, maksimalt uafhængigt sæt, minimum vertexdæksel og vertexfarvning

NP-komplette problemer
Maksimeringsproblem ved stabling (pakning)	Emballering i containere todimensionel pakning lineær pakning pakning efter vægt emballage efter værdi Rygsækproblemet
grafteori mængdeteori	Vertex Cover Problem Klik problem Problemet med et uafhængigt sæt (sæt) Sæt dækningsproblem Steiners problem Problemet med den rejsende sælger Generaliseret rejsende sælger problem
Algoritmiske problemer	Tilfredshedsproblem for booleske formler (i konjunktiv normal form)
Logiske spil og puslespil	Generaliserede tags (spil i N 2 -1) korteste løsningsproblem Problemer, hvis løsninger anvendes i Tetris Generaliseret Sudoku problem Latinsk kvadratisk påfyldningsproblem Kakuros opgave
Sværhedsklasser Operationsforskning Optimering Kombinatorisk optimering Anvendt matematik Teori om algoritmer Dynamisk programmering 21 NP-komplet Karp problem