En grafs skæringsantal er det mindste antal elementer i repræsentationen af en given graf som en finit sæt skæringsgraf , eller tilsvarende det mindste antal kliker , der kræves for at dække alle grafens kanter [1] [2] [ 3] .
Lad F være en familie af mængder (det er tilladt at gentage mængder i F ). Så er skæringsgrafen F en urettet graf med et toppunkt for hvert medlem af F og en kant mellem to sæt, der har et ikke-tomt skæringspunkt. Enhver graf kan repræsenteres som en skæringsgraf [4] . Skæringstallet for en graf er det mindste tal k , således at der findes en repræsentation af en type, for hvilken foreningen af mængder F har k elementer [1] . Problemet med at finde en repræsentation i form af en skæringsgraf med et givet antal elementer er kendt som problemet med at finde grundlaget for skæringsgrafen [5] .
En alternativ definition af skæringsnummeret for en graf G er det mindste antal kliker i G ( komplette undergrafer af G ), der dækker alle kanter af G [1] [6] . Et sæt af kliker med denne egenskab kaldes kantklikedækning , og derfor kaldes antallet af kryds undertiden for kantklikens dækningsnummer [7] .
Ligheden mellem antallet af kryds og antallet af kantdækninger af kliker er bevist "ligetil". Antag i én retning, at G er skæringsgrafen for en familie F af mængder, hvis forening U har k elementer. Så for ethvert element x fra U , danner delmængden af hjørner af grafen G , der svarer til mængderne, der indeholder x , en klike - to vilkårlige knudepunkter i denne delmængde er tilstødende, da deres tilsvarende mængder har et ikke-tomt skæringspunkt, der indeholder x . Yderligere er enhver kant i G indeholdt i en af disse kliker, da en kant svarer til et ikke-tomt skæringspunkt, og et skæringspunkt er ikke-tomt, hvis det indeholder mindst ét element U . Således kan kanterne af G være dækket af k kliker, en for hvert element af U . I den anden retning, hvis grafen G kan dækkes af k kliker, så kan hvert toppunkt på grafen G repræsenteres af et sæt kliker, der indeholder toppunktet [8] .
Det er klart, at en graf med m kanter har et antal skæringspunkter, der ikke overstiger m - enhver kant danner en klike, og disse kliker dækker tilsammen alle kanter [9] .
Det er også rigtigt, at enhver graf med n toppunkter højst har n 2/4 skæringspunkter . Mere strengt kan kanterne på enhver graf med n toppunkter opdeles i højst n 2 /4 kliker, som enten er enkeltkanter eller trekanter [2] [8] . Dette generaliserer Mantel-sætningen , der siger, at en trekantfri graf højst har n 2 /4 kanter. For grafer uden trekanter har det optimale kantklikedæksel en klike for hver kant, og derfor er antallet af skæringer lig med antallet af kanter [2] .
En endnu stærkere begrænsning er mulig, hvis antallet af kanter er strengt taget større end n 2/4 . Lad p være antallet af par af hjørner, der ikke er forbundet med kanter i den givne graf G , og lad t være det tal, for hvilket t ( t − 1) ≤ p < t ( t + 1) . Så overstiger antallet af skæringspunkter i grafen G ikke p + t [2] [10] .
Grafer, der er komplementer til sparsomme grafer , har et lille antal skæringspunkter — antallet af skæringspunkter for enhver graf G med n toppunkter i overstiger ikke 2 e 2 ( d + 1) 2 ln n , hvor e er basis for den naturlige logaritme af , d er den maksimale grad af den komplementære graf G [11] .
At kontrollere, at antallet af skæringer for en given graf G ikke overstiger et givet tal k , er et NP-komplet problem [12] [13] [14] . Det er således et NP-hårdt problem at beregne skæringstallet for en given graf.
Problemet med at beregne antallet af skæringspunkter er dog fast-parametrisk løseligt . Det vil sige, at der er en funktion f sådan, at når antallet af skæringspunkter er lig med tallet k , overstiger tiden til at beregne dette tal ikke produktet af f ( k ) med et polynomium i n . Dette kan vises ved at bemærke, at der højst er 2k distinkte lukkede kvarterer i grafen. To hjørner, der tilhører det samme sæt af kliker, har de samme naboer, og så har grafen, der dannes ved at vælge et hjørne for hvert lukket kvarter, det samme antal skæringspunkter som den oprindelige graf. Derfor, i polynomiel tid, kan input reduceres til en mindre kerne med maksimalt 2k toppunkter. Anvendelse af backtracking -algoritmen med eksponentiel køretid for denne kerne resulterer i en funktion f , der er den dobbelte eksponent af k [15] . Den dobbelte eksponentielle afhængighed af k kan ikke reduceres til en simpel eksponentiel afhængighed ved at udtrække en kerne af polynomisk størrelse, indtil polynomiehierarkiet forsvinder [16] , og hvis den eksponentielle tidshypotese er korrekt, kan den dobbelte eksponentielle afhængighed ikke undgås, uanset om vi bruger kerne udvinding eller ej [17] .
Mere effektive algoritmer er kendt for visse specielle klasser af grafer. Antallet af skæringspunkter i en intervalgraf er altid lig med antallet af maksimale klik på grafen, som kan beregnes i polynomisk tid [18] [19] . Mere generelt kan antallet af skæringspunkter for akkordgrafer beregnes ved hjælp af en algoritme, der konstruerer den rækkefølge, hvori grafens hjørner er udelukket. Ved hvert trin danner vi for hvert toppunkt v en klike for toppunktet v og dets naboer og udelukker toppunktet, hvis der er kanter, der falder sammen med v , men som endnu ikke er dækket af kliker [19] .