Graafin leikkauspistemäärä on pienin elementtien määrä tietyn graafin esityksessä rajallisena joukon leikkausgraafina tai vastaavasti pienin määrä klikkejä , jotka tarvitaan peittämään kaikki graafin reunat [1] [2] [ 3] .
Olkoon F joukkojen perhe (joukkoja saa toistaa F :ssä ). Tällöin leikkausgraafi F on suuntaamaton graafi , jossa on piste jokaiselle F : n jäsenelle ja reuna minkä tahansa kahden joukon välillä, joilla on ei-tyhjä leikkauspiste. Mikä tahansa graafi voidaan esittää leikkausgraafina [4] . Graafin leikkausnumero on pienin luku k siten, että on olemassa esitys tyypistä, jolle joukkojen F liitossa on k alkiota [1] . Esityksen löytäminen leikkausgraafin muodossa tietyllä määrällä elementtejä tunnetaan ongelmana leikkauskuvaajan perustan löytämisessä [5] .
Vaihtoehtoinen graafin G leikkausnumeron määritelmä on pienin G :n klikkien lukumäärä ( G :n täydelliset aligraafit ), jotka kattavat G :n kaikki reunat [1] [6] . Joukkoa klikejä, joilla on tämä ominaisuus, kutsutaan reunaklikkien peittoalueeksi , ja siksi leikkauspisteiden lukumäärää kutsutaan joskus reunaklikkien peittoluvuksi [7] .
Risteysten lukumäärän ja klikkien reunapeittomäärien yhtäläisyys on todistettu "suoraksi". Yhdessä suunnassa oletetaan, että G on joukon perheen F leikkauskaavio, jonka liitossa U on k alkiota. Sitten mille tahansa U:n elementille x graafin G kärkien osajoukko, joka vastaa x:n sisältäviä joukkoja, muodostaa klikkin — tämän osajoukon mitkä tahansa kaksi kärkeä ovat vierekkäisiä, koska niitä vastaavilla joukoilla on ei-tyhjä leikkauspiste, joka sisältää x :n . Lisäksi mikä tahansa G :n reuna sisältyy johonkin näistä klikeistä, koska reuna vastaa ei-tyhjää leikkauspistettä ja leikkaus on ei-tyhjä , jos se sisältää vähintään yhden elementin U. Siten G :n reunat voidaan peittää k klikeillä, yksi kutakin U :n elementtiä kohden . Toisessa suunnassa, jos graafi G voidaan kattaa k klikeillä, niin jokainen graafin G kärki voidaan esittää joukolla klikkejä, jotka sisältävät kärjen [8] .
Ilmeisesti graafissa, jossa on m reunaa, on useita leikkauskohtia, jotka eivät ylitä m - mikä tahansa reuna muodostaa klikkin, ja nämä klikkit yhdessä kattavat kaikki reunat [9] .
On myös totta, että millä tahansa graafilla, jossa on n kärkeä , on enintään n 2/4 leikkauspistettä . Tarkemmin sanottuna minkä tahansa graafin, jossa on n kärkeä, reunat voidaan jakaa enintään n 2 /4 -klikeiksi, jotka ovat joko yksittäisiä reunoja tai kolmioita [2] [8] . Tämä yleistää Mantel-lauseen , jonka mukaan kolmiovapaalla graafilla on enintään n 2 /4 reunaa. Graafeissa ilman kolmioita optimaalisella reunaklikkipeitolla on klikki jokaiselle reunalle, ja siksi leikkauspisteiden määrä on yhtä suuri kuin reunojen lukumäärä [2] .
Vielä vahvempi rajoitus on mahdollinen, jos reunojen lukumäärä on ehdottomasti suurempi kuin n 2 /4 . Olkoon p niiden kärkiparien lukumäärä, joita ei ole liitetty kulmiin annetussa graafissa G , ja olkoon t luku, jolle t ( t − 1) ≤ p < t ( t + 1) . Tällöin graafin G leikkauspisteiden määrä ei ylitä p + t [2] [10] .
Graafeissa, jotka ovat harvalukuisten graafien komplementteja , on pieni määrä leikkauspisteitä — minkä tahansa graafin G , jossa on n kärkeä i, leikkauspisteiden määrä ei ylitä 2 e 2 ( d + 1) 2 ln n , missä e on luonnollisen logaritmin kanta , d on komplementaarisen graafin G maksimiaste [ 11] .
Sen tarkistaminen, että tietyn graafin G leikkauspisteiden määrä ei ylitä annettua lukua k , on NP-täydellinen tehtävä [12] [13] [14] . Näin ollen tietyn graafin leikkausnumeron laskeminen on NP-kova tehtävä.
Leikkausten lukumäärän laskentaongelma on kuitenkin kiinteä-parametrisesti ratkaistava . Toisin sanoen on olemassa funktio f , joka on sellainen, että kun leikkauspisteiden lukumäärä on yhtä suuri kuin luku k , tämän luvun laskemisaika ei ylitä f ( k ) :n tuloa n: n polynomilla . Tämä voidaan osoittaa huomioimalla, että kaaviossa on enintään 2k erillistä suljettua aluetta . Kahdella samaan klikkijoukkoon kuuluvalla kärjellä on samat naapurit, ja sitten graafissa, joka muodostetaan valitsemalla yksi kärki kullekin suljetulle naapurustolle, on sama määrä leikkauspisteitä kuin alkuperäisellä graafilla. Siksi polynomiajassa syöte voidaan pienentää pienempään ytimeen , jossa on enintään 2k kärkipistettä. Peruutusalgoritmin soveltaminen eksponentiaalisella käyntiajalla tälle ytimelle johtaa funktioon f , joka on k :n [15] kaksoiseksponentti ] . Kaksinkertaista eksponentiaalista riippuvuutta k : stä ei voida pelkistää yksinkertaiseksi eksponentiaaliseksi riippuvuudeksi poimimalla polynomikokoinen ydin, kunnes polynomihierarkia katoaa [16] , ja jos eksponentiaalinen aikahypoteesi on oikea, kaksinkertaista eksponentiaalista riippuvuutta ei voida välttää, jos käytämme ydintä. louhinta vai ei [17] .
Tehokkaampia algoritmeja tunnetaan tietyille erityisluokille graafit. Intervalligraafin leikkauspisteiden määrä on aina yhtä suuri kuin graafin maksimiklikkien lukumäärä , joka voidaan laskea polynomiajassa [18] [19] . Yleisemmin sointukaavioiden leikkauspisteiden lukumäärä voidaan laskea algoritmilla, joka muodostaa järjestyksen, jossa graafin kärjet jätetään pois. Muodostamme jokaisessa vaiheessa kullekin pisteelle v klikin kärjelle v ja sen naapureille ja suljemme kärjen pois, jos on reunoja, jotka kohtaavat v :n kanssa, mutta joita klikkit eivät vielä peitä [19] .