Kontur rang

I grafteori er konturrangen [1] af en urettet graf det mindste antal kanter, hvis fjernelse ødelægger alle cyklusser af grafen, hvilket gør den til et træ eller en skov. Konturrækken kan også forstås som antallet af uafhængige cyklusser i en graf. I modsætning til det tilsvarende problem med at finde et cyklusskærende sæt buer for rettede grafer , beregnes konturrangen r let med formlen

,

hvor m er antallet af kanter på den givne graf, n er antallet af hjørner , og c er antallet af forbundne komponenter [2] . Det er også muligt effektivt at konstruere et sæt minimumsstørrelseskanter, der bryder cyklusser ved hjælp af enten den grådige algoritme eller spændingstræ- komplementet .

Konturrækken er også kendt som det cyklomatiske tal på en graf. Det kan forklares i form af algebraisk grafteori som dimensionen af ​​det cykliske rum i en graf, i form af matroider ved at bruge begrebet corrank af grafmatroider [ [3] , og i form af topologi som en af ​​Betti tal for et topologisk rum afledt af en graf. Konturrangen tæller antallet af ører i en ørenedbrydning af en graf, som danner grundlag for forestillingen om kompleksitet på næsten træer og bruges i softwaremetrikker som en del af definitionen af ​​den cyklomatiske kompleksitet af et stykke kode. Under navnet cyklomatisk kompleksitet blev begrebet introduceret af Gustav Kirchhoff [4] [5] .

Matroid-rangering og konstruktion af et minimalt cyklusskæringssæt

Konturrangen af ​​en graf G kan beskrives ved hjælp af matroideteori som corranken af ​​en grafmatroide for G [6] . Under hensyntagen til den grådige egenskab ved matroider betyder det, at det er muligt at finde det mindste sæt af kanter, der ødelægger alle cyklusser, ved hjælp af den grådige algoritme , som ved hvert trin vælger en kant, der hører til mindst én cyklus af den resterende graf.

På den anden side kan det mindste sæt af sæt, der bryder alle cyklusser, findes ved at konstruere en spændende skov af G og vælge et komplementært sæt af kanter, der ikke hører til den spændende skov.

Antal uafhængige cyklusser

I algebraisk grafteori er konturrangen dimensionen af ​​en grafs cyklusrum . Intuitivt kan konturrang forklares som at tælle antallet af uafhængige cyklusser i en graf, hvor et sæt af cyklusser betragtes som uafhængige, hvis det er umuligt at danne en cyklus som den symmetriske forskel af en delmængde af andre cyklusser [2] .

Denne optælling af uafhængige cyklusser kan forklares ved hjælp af homologiteori , en gren af ​​topologi . Enhver graf G kan ses som et eksempel på et 1-dimensionelt forenklet kompleks , en type topologisk rum , dannet ved at repræsentere hver kant af grafen med et segment og lime disse segmenter i enderne. Det cyklomatiske tal er rangeringen af ​​den første (heltals) homologigruppe i dette kompleks [7] ,

I forbindelse med en sådan topologisk sammenhæng kaldes grafens G's cyklomatiske tal også det første Betti-tal på grafen G [8] . Mere generelt tæller det første Betti-tal i ethvert topologisk rum antallet af uafhængige cyklusser i rummet.

Konturrangeringen af ​​en graf er relateret til rangordenen af ​​dens forekomstmatrix gennem relationen .

Ansøgninger

Retikulationskoefficient

En variant af konturrangen for en plan graf , normaliseret ved at dividere med den maksimalt mulige konturrang for enhver plan graf med det samme sæt af hjørner, kaldes nettingfaktoren . For forbundne plane grafer med m kanter og n toppunkter kan netværkskoefficienten beregnes ved hjælp af formlen [9]

I denne formel er tælleren i formlen konturrækken af ​​den givne graf, og nævneren er den størst mulige konturrangering af en plan graf med n toppunkter. Maskefaktoren ligger mellem 0 for træer og 1 for maksimale plane grafer .

Øre nedbrydning

Konturrangen afspejler antallet af ører i ørenedbrydningen af ​​grafen, dekomponeringen af ​​grafens kanter i stier og cyklusser, hvilket ofte er nyttigt i grafalgoritmer. Især er en graf vertex-2-forbundet , hvis og kun hvis den har en åben ørenedbrydning, en sekvens af undergrafer, hvor den første undergraf er en simpel cyklus, og de resterende undergrafer er simple stier, og hver sti starter og slutter ved hjørner tilhørende tidligere undergrafer, og hvert indre hjørne af stien vises for første gang i den sti. I enhver biforbundet graf med konturrang har enhver åben ørenedbrydning nøjagtigt ører [10] .

Næsten træer

En graf med et cyklomatisk tal kaldes også et næsten r - træ , da kun r kanter skal fjernes fra grafen for at gøre den til et træ eller skov. Et næsten 1-træ er næsten et træ - et forbundet næsten træ er en pseudo -skov , en cyklus med (muligvis trivielle) træer med rod i hvert hjørne [11] .

Nogle forfattere har studeret den parametriserede kompleksitet af algoritmer på næsten r- træer med parametrisering ifølge [12] [13] .

Generalisering for rettede grafer

Cyklisk rang er en rettet grafinvariant , der måler niveauet af indlejring af cyklusser i en graf. Denne invariant har en mere kompliceret definition end den cyklomatiske rang (nært forbundet med definitionen af ​​trædybde for urettede grafer) og er meget sværere at beregne. Et andet problem for rettede grafer relateret til cyklomatisk rang er bestemmelsen af ​​det minimale cyklusskærende sæt af buer , det vil sige minimumssættet af buer, hvis fjernelse ødelægger alle rettede cykler. Begge problemer, beregning af den cykliske rangorden og bestemmelse af minimumssættet af buer, der skærer cyklusser, er NP-hårde .

Det er også muligt at beregne en enklere invariant af rettede grafer ved at ignorere kantretninger og beregne den cykliske rangorden af ​​en urettet graf. Dette princip danner grundlaget for at definere cyklomatisk kompleksitet , et mål for computerprogramkompleksitet til at estimere kompleksiteten af ​​et stykke computerkode.

Relaterede begreber

Andre tal defineret med hensyn til fjernelse af kanter fra en urettet graf inkluderer kantforbindelse , det mindste antal kanter, hvis fjernelse forårsager tab af forbindelse, og det matchende undgåelsesnummer , det mindste antal kanter, hvis fjernelse forårsager, at en perfekt matchning ophører at eksistere .

Noter

  1. ↑ I russisksproget litteratur er både cyklusrang og kredsløb ofte oversat på samme måde - cyklisk rang. I engelsk litteratur refererer det første udtryk til rettede grafer, det andet til urettede grafer. I denne artikel bruges udtrykket "cyklisk rang" til rettede grafer og "konturrang" for urettede grafer.
  2. ↑ 12 Berge , 2001 , s. 27-30.
  3. ↑ I russisksproget litteratur bruges også udtrykket grafisk matroid , som er et sporingspapir af den engelske grafiske matroid og ikke helt svarer til essensen af ​​begrebet.
  4. ↑ Kotiuga, 2010 , s. tyve.
  5. ↑ Hage, 1996 , s. 48.
  6. ↑ Berge, 1976 , s. 477.
  7. ↑ Serre, 2003 , s. 23.
  8. ↑ Berkolaiko, Kuchment, 2013 , s. fire.
  9. ↑ Buhl, Gautrais, Sole et al., 2004 , s. 123-129.
  10. ↑ Whitney, 1932 , s. 339-362.
  11. ↑ Brualdi, 2006 , s. 349.
  12. ↑ Coppersmith, Vishkin, 1985 , s. 27-45.
  13. ↑ Fiala, Kloks, Kratochvíl, 2001 , s. 59-72.

Litteratur