Splittans

I grafteorin , en gren av matematiken, mäter splittansen av en oriktad graf dess avstånd från en delad graf . En delad graf är en graf vars hörn kan delas upp i en oberoende uppsättning (utan kanter inom denna delmängd) och en klick (som har alla möjliga kanter inom denna delmängd). Splittansen är det minsta antalet kanttillägg och borttagningar som omvandlar den givna grafen till en delad graf.

Beräkning från gradföljd

Splittansen för en graf kan endast beräknas utifrån grafens gradsekvens , utan att undersöka grafens detaljerade struktur. Låt G vara vilken graf som helst med n hörn, vars grader i fallande ordning är d ₁ ≥ d ₂ ≥ d ₃ ≥ … ≥ d _n . Låt m vara det största indexet för vilket d _i ≥ i – 1 . Då är splitten av G

$\sigma (G)={\tbinom {m}{2}}-{\frac {1}{2}}\sum _{i=1}^{m}d_{i}+{\frac {1}{2}}\summa _{i=m+1}^{n}d_{i}.$

Den givna grafen är en delad graf redan om σ ( G ) = 0 . Annars kan den göras till en delad graf genom att beräkna m , lägga till alla saknade kanter mellan paren av de m hörn av maximal grad och ta bort alla kanter mellan paren av de återstående hörnen. Som en konsekvens kan splittansen och en sekvens av kanttillägg och -borttagningar som realiserar den beräknas i linjär tid .

Ansökningar

Splitningen av en graf har använts i parameteriserad komplexitet som en parameter för att beskriva effektiviteten hos algoritmer. Till exempel graffärgning med fasta parametrar hanteras under denna parameter: det är möjligt att optimalt färglägga graferna för gränsad splittans i linjär tid .