Vertex-kannen ongelma

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

Vertex cover -ongelma on NP-täydellinen tietojenkäsittelytieteen ongelma graafiteorian alalla . Käytetään usein monimutkaisuusteoriassa monimutkaisempien ongelmien NP-täydellisyyden osoittamiseen.

Määritelmä

Suuntaamattoman graafin kärjen kansi on joukko sen kärkipisteitä siten, että jokaisessa graafin reunassa vähintään yksi päistä tulee kärkeen alkaen . $G=(V,E)$ $S$ $S$

Vertex-peitteen koko on sen sisältämien kärkien lukumäärä.

Esimerkki: Oikealla olevan kaavion kärjen peite on kooltaan 4. Tämä ei kuitenkaan ole pienin pistepeite, koska on pienempiä kärkipeitteitä, kuten ja . $\{1,3,5,6\}$ $\{2,4,5\}$ $\{1,2,4\}$

Huippupeiteongelmana on löytää tietyn graafin pienimmän kokoinen kärjen peite (tätä kokoa kutsutaan graafin kärjen peitteen numeroksi ).

Sisäänkäynti: Count .

G=(V,E)

Tulos: joukko on graafin pienin huippupiste .

C\subseteq V

G

Myös kysymys voidaan esittää vastaavana ratkaisuongelmana :

Syöttö: Kaavio ja positiivinen kokonaisluku .

G

k

Kysymys: Onko korkeintaan koon graafiselle pisteen kansi ?

C

G

k

Vertex cover - ongelma on samanlainen kuin riippumaton joukko - tehtävä . Koska pistejoukko on kärjen peite silloin ja vain jos sen komplementti on riippumaton joukko, ongelmat pelkistyvät toisiinsa. $C$ $V\setminus C$

NP-täydellinen

Koska kärkipeiteongelma on NP-täydellinen , ei valitettavasti ole tunnettuja algoritmeja sen ratkaisemiseksi polynomiajassa. On kuitenkin olemassa approksimaatioalgoritmeja, jotka antavat "likimääräisen" ratkaisun tähän ongelmaan polynomiajassa - voit löytää huippupisteen peitteen, jossa pisteiden lukumäärä on enintään kaksi kertaa mahdollisimman pieni.

Yksi ensimmäisistä mieleen tulevan ongelman ratkaisutavoista on approksimaatio ahneella algoritmilla : Vertex-peittoon on lisättävä pisteitä, joissa on maksimimäärä naapureita, kunnes ongelma on ratkaistu, mutta sellaisella ratkaisulla ei ole -approximaatiota . mille tahansa vakiolle . $\rho$ $\rho$

Toinen ratkaisu on etsiä annetusta graafista suurin vastaavuus ja valita joukko kärkipeitteenä . Tällaisen algoritmin oikeellisuuden todistaa ristiriita: If ei ole kärkipeite (ei välttämättä pienin), ts. , silloin se ei ole maksimaalinen vastaavuus. Approksimointikerroin todistetaan seuraavasti: Olkoon , missä on graafin riippumattomuusluku ja on graafin suurin vastaavuus . Sitten approksimaatiokerroin on . $M\in E$ $G=(V,E)$ $C=\bigcup _{e\in M}e$ $C$ $\exists e\colon e\cap C=\emptyset$ $M$ $\tau (G)=|V|-\alpha (G)$ $\alpha (G)$ $G$ $M_{max}(G)$ $G$ ${\frac {2\cdot |M|}{\tau (G)))\leqslant {\frac {2\cdot |M_{max}(G)|}{\tau (G)))\ leqslant {\frac {2\cdot |M_{max}(G)|}{|M_{max}(G)|}}=2$

Yleisesti ottaen kärkipeiteongelma voidaan arvioida kertoimella . $2-{\frac {\log \log n}{2\cdot \log n))$

Vertex cover -ongelma kaksiosaisissa kaavioissa

Kaksiosaisissa graafeissa kärjen peittotehtävä on ratkaistavissa polynomiajassa, koska se pelkistyy suurimmaksi sovitusongelmaksi ( Königin lause ).

Linkit

Kirjallisuus

Thomas H. Kormen ym. Luku 36. NP-täydellisyys // Algoritmit: Konstruointi ja analyysi = JOHDANTO ALGORITMEIHIN. - 1. painos - M .: Moskovan matematiikan jatkuvan koulutuksen keskus, 2001. - S. 866.

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