Kretsrankning - Circuit rank

Denna graf har kretsrankning r = 2 eftersom den kan göras till ett träd genom att ta bort två kanter, till exempel kanterna 1–2 och 2–3, men att ta bort en kant lämnar en cykel i diagrammet.

I grafteorin är en gren av matematik , kretsrankning , cyklomatiskt tal , cykelrangering eller ogiltighet hos en icke-riktad graf det minsta antalet kanter som måste tas bort från diagrammet för att bryta alla dess cykler , vilket gör det till ett träd eller skog. Det är lika med antalet oberoende cykler i diagrammet (storleken på en cykelbas ). Till skillnad från motsvarande återkopplingsbåguppsättningsproblem för riktade grafer beräknas kretsrankningen r enkelt med hjälp av formeln

${\ displaystyle r = m-n + c}$,

där m är antalet kanter i den angivna grafen, n är antalet hörnpunkter och c är antalet anslutna komponenter . Det är också möjligt att konstruera en minsta storlek av kanter som bryter alla cykler effektivt, antingen med en girig algoritm eller genom att komplettera en spännande skog .

Kretsrankningen kan förklaras i termer av algebraisk grafteori som dimensionen på cykelutrymmet i en graf, i termer av matroidteori som corank av en grafisk matroid , och i termer av topologi som en av Betti-siffrorna för en topologisk utrymme härledd från diagrammet. Det räknar öronen i en sönderdelning av örat i grafen, utgör grunden för parametrerad komplexitet på nästan träd och har använts i mjukvarumätvärden som en del av definitionen av cyklomatisk komplexitet i en kodkod. Under namnet cyclomatic nummer introducerades konceptet av Gustav Kirchhoff .

Matroid rankning och konstruktion av en minsta återkopplingssats

Kretsen rangen av en graf G kan beskrivas med användning matroid teori som corank av grafiska matroid av G . Med hjälp av den giriga egenskapen hos matroider betyder det att man kan hitta en minsta uppsättning kanter som bryter alla cykler med hjälp av en girig algoritm som vid varje steg väljer en kant som tillhör minst en cykel i den återstående grafen.

Alternativt kan en minsta uppsättning kanter som bryter alla cykler hittas genom att konstruera en spännande skog av G och välja den kompletterande uppsättning kanter som inte tillhör spännskogen.

Antalet oberoende cykler

I algebraisk grafteori , är kretsen rang även dimensionen på cykeln utrymmet av . Intuitivt kan detta förklaras så att kretsrankningen räknar antalet oberoende cykler i diagrammet, där en samling cykler är oberoende om det inte är möjligt att bilda en av cyklerna som den symmetriska skillnaden för någon delmängd av de andra . ${\ displaystyle G}$

Detta antal oberoende cykler kan också förklaras med hjälp av homologiteori , en gren av topologi . Vilken som helst graf G kan ses som ett exempel på ett 1-dimensionellt förenklat komplex , en typ av topologiskt utrymme som bildas genom att representera varje grafkant av ett linjesegment och limma samman dessa linjesegment vid sina slutpunkter. Det cyklomatiska talet är rankningen för den första (heltal) homologigruppen i detta komplex,

${\ displaystyle r = \ operatorname {rank} \ left [H_ {1} (G, \ mathbb {Z}) \ right].}$

På grund av detta topologiska sammanhang cyklomatisk antalet en graf G kallas också den första Betti antal av G . Mer allmänt räknar det första Betti-numret i varje topologiskt utrymme, definierat på samma sätt, antalet oberoende cykler i utrymmet.

Applikationer

Meshedness koefficient

En variant av kretsrankningen för plana grafer , normaliserad genom att dividera med den maximala möjliga kretsrankningen för alla plana diagram med samma toppunkt, kallas maskningskoefficienten . För en ansluten plan graf med m- kanter och n- hörn kan maskingekoefficienten beräknas med formeln

${\ displaystyle {\ frac {m-n + 1} {2n-5}}.}$

Här är täljaren för formeln kretsrankningen för den angivna grafen, och nämnaren är den största möjliga kretsrankningen för en n- vertikal plan graf. Maskingskoefficienten varierar mellan 0 för träd och 1 för maximala plana grafer . ${\ displaystyle m-n + 1}$${\ displaystyle 2n-5}$

Öronnedbrytning

Kretsrankningen styr antalet öron i en sönderdelning av en graf, en delning av kanterna på diagrammet i banor och cykler som är användbart i många grafalgoritmer. I synnerhet är en graf 2-vertex-ansluten om och bara om den har en öppen nedbrytning. Detta är en sekvens av underbilder, där den första underbilden är en enkel cykel, de återstående delbilderna är alla enkla vägar, varje väg börjar och slutar på hörn som tillhör tidigare underbilder, och varje interna toppunkt för en väg visas för första gången i den vägen. I alla tvåkopplade diagram med kretsrankning har varje öppen nedbrytning exakt öron. ${\ displaystyle r}$${\ displaystyle r}$

Nästan-träd

En graf med cyklomatiskt nummer kallas också ett r -nästan-träd , eftersom endast r- kanter behöver tas bort från diagrammet för att göra det till ett träd eller en skog. Ett 1-nästan-träd är ett nästan-träd : ett anslutet nära-träd är ett pseudotree , en cykel med ett (möjligen trivialt) träd rotat vid varje toppunkt. ${\ displaystyle r}$

Flera författare har studerat den parametrerade komplexiteten för grafalgoritmer på r -nära träd, parametrerad av . ${\ displaystyle r}$

Generaliseringar till riktade grafer

Den cykel rang är en invariant av riktade grafer som mäter nivån av häckar av cykler i grafen. Den har en mer komplicerad definition än kretsrankning (nära relaterad till definitionen av trädjup för oriktade grafer) och är svårare att beräkna. Ett annat problem för riktade grafer relaterade till kretsrankningen är minsta återkopplingsbågsats , den minsta uppsättningen kanter vars avlägsnande bryter alla riktade cykler. Både cykelrankning och minsta återkopplingsbågsats är NP-svåra att beräkna.

Det är också möjligt att beräkna en enklare invariant av riktade grafer genom att ignorera kanternas riktningar och beräkna kretsrankningen för den underliggande oriktade grafen. Denna princip ligger till grund för definitionen av cyklomatisk komplexitet , ett mjukvarumätvärde för att uppskatta hur komplicerat en datorkod är.

Beräkningskemi

Inom områdena kemi och keminformatik kallas kretsrankningen för ett molekylärt diagram (antalet ringar i den minsta uppsättningen minsta ringar ) ibland Frèrejacque-numret .

Parametriserad komplexitet

Vissa beräkningsproblem i grafer är NP-hårda i allmänhet, men kan lösas på polynomtid för grafer med liten kretsrankning. Ett exempel är vägen omkonfigurering problem.

Relaterade begrepp

Andra siffror definierade i termer av att ta bort saker från grafer är:

• Kantanslutning - det minsta antalet kanter som ska raderas för att koppla bort grafen;
• Matchande uteslutning - det minsta antalet kanter som ska raderas för att förhindra att det finns en perfekt matchning ;
• Återkopplingsverksuppsättningsnummer - det minsta antalet vertikaler som ska raderas för att göra grafen acyklisk;
• Återkopplingsbågeset - det minsta antalet bågar som ska raderas från en riktad graf för att göra den acyklisk.

Referenser