Kontur rang

I grafteorin är konturrangen [1] för en oriktad graf det minsta antalet kanter vars borttagning förstör alla cykler i grafen och förvandlar den till ett träd eller skog. Konturrangen kan också förstås som antalet oberoende cykler i en graf. I motsats till motsvarande problem med att hitta en cykelskärande uppsättning bågar för riktade grafer , beräknas konturrankningen r enkelt med formeln

,

där m är antalet kanter på den givna grafen, n är antalet hörn och c är antalet anslutna komponenter [2] . Det är också möjligt att effektivt konstruera en uppsättning minsta storlekskanter som bryter cykler med antingen den giriga algoritmen eller spännträdskomplementet .

Konturrangen är också känd som det cyklomatiska numret för en graf. Det kan förklaras i termer av algebraisk grafteori som dimensionen av det cykliska utrymmet i en graf, i termer av matroider med begreppet kornk av grafmatroider [3] , och i termer av topologi som en av Betti siffror för ett topologiskt utrymme härlett från en graf. Konturrangen räknar antalet öron i en öronupplösning av en graf, vilket ger grunden för begreppet komplexitet på nästan träd och används i mjukvarumetrik som en del av definitionen av den cyklomatiska komplexiteten hos ett stycke kod. Under namnet cyklomatisk komplexitet introducerades begreppet av Gustav Kirchhoff [4] [5] .

Matroid ranking och konstruktion av en minimal cyklisk skärningsuppsättning

Konturrangen för en graf G kan beskrivas med hjälp av matroideori som corranken för en grafmatroid för G [6] . Med hänsyn till den giriga egenskapen hos matroider, betyder detta att det är möjligt att hitta den minsta uppsättningen av kanter som förstör alla cykler med hjälp av den giriga algoritmen , som vid varje steg väljer en kant som tillhör minst en cykel av den återstående grafen.

Å andra sidan kan den minsta uppsättningen av uppsättningar som bryter alla cykler hittas genom att konstruera en spännande skog av G och välja en kompletterande uppsättning kanter som inte tillhör den spännande skogen.

Antal oberoende cykler

I algebraisk grafteori är konturrangen dimensionen av en grafs cykelrum . Intuitivt kan konturrangen förklaras som att man räknar antalet oberoende cykler i en graf, där en uppsättning cykler anses vara oberoende om det är omöjligt att bilda en cykel som den symmetriska skillnaden för någon delmängd av andra cykler [2] .

Detta antal oberoende cykler kan förklaras med homologiteori , en gren av topologi . Vilken graf G som helst kan ses som ett exempel på ett 1-dimensionellt förenklat komplex , en typ av topologiskt utrymme , bildat genom att representera varje kant av grafen med ett segment och limma dessa segment i ändarna. Det cyklomatiska talet är rangordningen för den första (heltals) homologigruppen i detta komplex [7] ,

I samband med en sådan topologisk koppling kallas det cyklomatiska numret på grafen G också det första Betti-talet på grafen G [8] . Mer generellt räknar det första Betti-talet i ett topologiskt utrymme antalet oberoende cykler i utrymmet.

Konturrankningen av en graf är relaterad till rankningen av dess incidensmatris genom relationen .

Applikationer

Retikulationskoefficient

En variant av konturrangen för en plan graf , normaliserad genom att dividera med den maximala möjliga konturrangen för en plan graf med samma uppsättning hörn, kallas nettingfaktorn . För anslutna plana grafer med m kanter och n hörn kan nätverkskoefficienten beräknas med formeln [9]

I denna formel är täljaren i formeln konturrangen för den givna grafen, och nämnaren är den största möjliga konturrangen för en plan graf med n hörn. Nätfaktorn ligger mellan 0 för träd och 1 för maximala plana grafer .

Öronnedbrytning

Konturrankningen återspeglar antalet öron i grafens sönderdelning, sönderdelningen av grafens kanter till banor och cykler, vilket ofta är användbart i grafalgoritmer. I synnerhet är en graf vertex-2-ansluten om och endast om den har en öppen öronnedbrytning, en sekvens av subgrafer där den första subgrafen är en enkel cykel och de återstående subgraferna är enkla banor och varje bana börjar och slutar vid hörn tillhör tidigare subgrafer, och varje inre hörn av banan visas för första gången i den banan. I alla tvåkopplade grafer med konturrang, har alla öppna öronnedbrytningar exakt öron [10] .

Nästan träd

En graf med ett cyklomatiskt nummer kallas också ett nästan r -träd , eftersom endast r kanter behöver tas bort från grafen för att förvandla den till ett träd eller skog. Ett nästan 1-träd är nästan ett träd — ett sammanhängande nästan träd är en pseudoskog , en cykel med (möjligen triviala) träd rotade vid varje vertex [11] .

Vissa författare har studerat den parametriserade komplexiteten av algoritmer på nästan r -träd med parametrisering enligt [12] [13] .

Generalisering för riktade grafer

Cyklisk rang är en riktad grafinvariant som mäter nivån av kapsling av cykler i en graf. Denna invariant har en mer komplicerad definition än den cyklomatiska rangordningen (nära relaterad till definitionen av träddjup för oriktade grafer) och är mycket svårare att beräkna. Ett annat problem för riktade grafer relaterade till cyklomatisk rang är bestämningen av den minsta cykelskärningsuppsättningen av bågar , det vill säga den minsta uppsättningen av bågar vars borttagning förstör alla riktade cykler. Båda problemen, att beräkna den cykliska rangordningen och bestämma den minsta uppsättningen av bågar som skär cykler, är NP-hårda .

Det är också möjligt att beräkna en enklare invariant av riktade grafer genom att ignorera kantriktningar och beräkna den cykliska rangordningen för en oriktad graf. Denna princip utgör grunden för att definiera cyklomatisk komplexitet , ett mått på datorprograms komplexitet för att uppskatta komplexiteten hos en bit datorkod.

Relaterade begrepp

Andra siffror som definieras i termer av att ta bort kanter från en oriktad graf inkluderar kantanslutningar , det minsta antalet kanter vars borttagning orsakar förlust av anslutningsmöjligheter och det matchande undvikande numret , det minsta antalet kanter vars borttagning gör att en perfekt matchning upphör att existera .

Anteckningar

  1. ↑ I ryskspråkig litteratur översätts ofta både cykelgrad och kretsrankning på samma sätt - cyklisk rang. I engelsk litteratur syftar den första termen på riktade grafer, den andra på oriktade grafer. I den här artikeln används termen "cyklisk rankning" för riktade grafer och "konturrang" för oriktade grafer.
  2. ↑ 12 Berge , 2001 , sid. 27–30.
  3. ↑ I ryskspråkig litteratur används även termen graphic matroid , som är ett spårningspapper av den engelska graphic matroid och inte riktigt motsvarar begreppets essens.
  4. ↑ Kotiuga, 2010 , sid. tjugo.
  5. ↑ Hage, 1996 , sid. 48.
  6. ↑ Berge, 1976 , sid. 477.
  7. ↑ Serre, 2003 , sid. 23.
  8. ↑ Berkolaiko, Kuchment, 2013 , sid. fyra.
  9. ↑ Buhl, Gautrais, Sole et al., 2004 , sid. 123–129.
  10. ↑ Whitney, 1932 , sid. 339–362.
  11. ↑ Brualdi, 2006 , sid. 349.
  12. ↑ Coppersmith, Vishkin, 1985 , sid. 27–45.
  13. ↑ Fiala, Kloks, Kratochvíl, 2001 , sid. 59–72.

Litteratur