Contour rank

Graafiteoriassa suuntaamattoman graafin ääriviivaluokka [ 1] on pienin määrä reunoja, joiden poistaminen tuhoaa kaikki graafin syklit ja muuttaa sen puuksi tai metsäksi. Ääriviivan arvo voidaan ymmärtää myös riippumattomien syklien lukumääränä kaaviossa. Päinvastoin kuin vastaava ongelma löytää kiertoleikkauskaaret suunnatuille kaavioille , ääriviivan arvo r on helppo laskea kaavalla

,

missä m on annetun graafin reunojen lukumäärä, n on pisteiden lukumäärä ja c on yhdistettyjen komponenttien lukumäärä [2] . On myös mahdollista rakentaa tehokkaasti joukko vähimmäiskokoisia reunoja, jotka katkaisevat jaksoja joko ahneella algoritmilla tai virittävän puun komplementilla .

Ääriviivat tunnetaan myös kaavion syklomaattisena numerona . Se voidaan selittää algebrallisella graafiteorialla graafin syklisen avaruuden ulottuvuutena , matroideina käyttämällä graafimatroidien korunkin käsitettä [ [3] , ja topologian kannalta yhtenä Bettin . graafista johdetut topologisen avaruuden numerot . Contour rank laskee korvien lukumäärän graafin korvahajotelmassa , joka muodostaa perustan monimutkaisuuden käsitteelle lähes puissa ja jota käytetään ohjelmistometriikassa osana koodin syklomaattisen monimutkaisuuden määrittelyä . Syklomaattisen kompleksisuuden alla käsitteen esitteli Gustav Kirchhoff [4] [5] .

Matroid-arvo ja minimaalisen syklinleikkaussarjan rakentaminen

Graafin G ääriviivat voidaan kuvata käyttämällä matroiditeoriaa graafin matroidin korkina G :lle [6] . Matroidien ahne-ominaisuus huomioon ottaen tämä tarkoittaa, että on mahdollista löytää kaikki syklit tuhoava minimireunojen joukko käyttämällä ahnealgoritmia , joka valitsee jokaisessa vaiheessa reunan, joka kuuluu ainakin yhteen jäljellä olevan graafin sykliin.

Toisaalta vähimmäisjoukkojen joukko, joka katkaisee kaikki syklit, löytyy rakentamalla G:n virittävä metsä ja valitsemalla täydentävä joukko reunoja, jotka eivät kuulu ulottuvaan metsään.

Riippumattomien jaksojen lukumäärä

Algebrallisessa graafiteoriassa ääriviiva on graafin sykliavaruuden ulottuvuus . Intuitiivisesti ääriviivajärjestys voidaan selittää graafin riippumattomien syklien lukumäärän laskemisella, jossa syklien joukkoa pidetään itsenäisenä, jos on mahdotonta muodostaa yhtä sykliä muiden syklien jonkin osajoukon symmetriseksi eroksi [2] .

Tämä riippumattomien syklien määrä voidaan selittää homologiateorialla , topologian haaralla . Mitä tahansa graafia G voidaan nähdä esimerkkinä 1-ulotteisesta yksinkertaisesta kompleksista , yhden tyyppisestä topologisesta avaruudesta , joka muodostetaan edustamalla graafin jokaista reunaa segmentillä ja liimaamalla nämä segmentit päihin. Syklomaattinen luku on tämän kompleksin ensimmäisen (kokonaisluvun) homologiaryhmän järjestys [7] ,

Tällaisen topologisen yhteyden yhteydessä graafin G syklomaattista lukua kutsutaan myös graafin G ensimmäiseksi Betti - luvuksi [ 8] . Yleisemmin minkä tahansa topologisen avaruuden ensimmäinen Betti-luku laskee avaruudessa olevien itsenäisten syklien määrän.

Graafin ääriviivasijoitus on suhteessa sen esiintyvyysmatriisin järjestykseen relaatiolla .

Sovellukset

Verkkokerroin

Tasograafin ääriviivaluokituksen muunnelmaa , joka normalisoidaan jakamalla minkä tahansa tasograafin, jolla on samat kärkijoukot, maksimiarvolla, kutsutaan nettokertoimeksi . Yhdistetyille tasograafille, jossa on m reunaa ja n kärkeä, verkkokerroin voidaan laskea kaavalla [9]

Tässä kaavassa kaavan osoittaja on annetun graafin ääriviiva, ja nimittäjä on tasograafin, jossa on n pistettä, suurin mahdollinen ääriviiva. Silmäkerroin on välillä 0 puille ja 1 maksimaalisille tasokaavioille .

Korvan hajoaminen

Contour rank heijastaa korvien lukumäärää graafin korvahajotelmassa , graafin reunojen hajottamista poluiksi ja sykleiksi, mikä on usein hyödyllistä graafialgoritmeissa. Erityisesti graafi on vertex-2-kytketty , jos ja vain jos siinä on avoin korvahajotus, aligraafien sarja, jossa ensimmäinen osagraafi on yksinkertainen sykli ja loput osagraafit ovat yksinkertaisia ​​polkuja ja jokainen polku alkaa ja päättyy pisteisiin. jotka kuuluvat aikaisempiin aligraafiin, ja jokainen polun sisäinen kärkipiste esiintyy ensimmäistä kertaa kyseisessä polussa. Missä tahansa kaksoiskytkentäisessä kaaviossa, jolla on ääriviivat, kaikilla avoimella korvahajotelmilla on täsmälleen korvat [10] .

Melkein puita

Graafia, jossa on syklomaattinen luku , kutsutaan myös melkein r -puuksi , koska graafista tarvitsee poistaa vain r reunaa, jotta se muuttuu puuksi tai metsäksi. Lähes 1-puu on melkein puu - yhdistetty melkein puu on pseudometsä , kiertokulku, jonka jokaisessa kärjessä on (mahdollisesti triviaaleja) puita [11] .

Jotkut kirjoittajat ovat tutkineet algoritmien parametroitua monimutkaisuutta lähes r -puilla parametrisoinnilla [12] [13] .

Yleistys suunnatuille kaavioille

Cyclic rank on suunnattu graafin invariantti , joka mittaa syklien sisäkkäisyyden tasoa kaaviossa. Tällä invariantilla on monimutkaisempi määritelmä kuin syklomaattisella järjestyksellä (liittyy läheisesti suuntaamattomien graafien puun syvyyden määritelmään ) ja se on paljon vaikeampi laskea. Toinen syklomaattiseen järjestykseen liittyvien suunnattujen graafien ongelma on syklin katkaisevan kaarien minimijoukon määrittäminen, eli kaarien vähimmäisjoukko, jonka poistaminen tuhoaa kaikki suunnatut syklit. Molemmat tehtävät, syklisen järjestyksen laskeminen ja sykliä leikkaavien kaarien vähimmäisjoukon määrittäminen, ovat NP-kovia .

On myös mahdollista laskea yksinkertaisempi suunnattujen graafien invariantti jättämällä huomioimatta reunasuunnat ja laskemalla suuntaamattoman graafin syklinen arvo. Tämä periaate muodostaa perustan syklomaattisen monimutkaisuuden määrittämiselle , joka on tietokoneohjelman monimutkaisuuden mitta tietokonekoodin osan monimutkaisuuden arvioimiseksi.

Aiheeseen liittyvät käsitteet

Muita suuntaamattoman graafin reunojen poistamisen kannalta määriteltyjä lukuja ovat reunan liitettävyys , niiden reunojen vähimmäismäärä, joiden poistaminen aiheuttaa yhteyden katkeamisen, ja täsmäämisen välttämisluku , reunojen vähimmäismäärä, jonka poistaminen lopettaa täydellisen sovituksen . olla olemassa .

Muistiinpanot

  1. ↑ Venäjänkielisessä kirjallisuudessa sekä syklin arvo että piiriarvo käännetään usein samalla tavalla - syklinen rank. Englanninkielisessä kirjallisuudessa ensimmäinen termi viittaa suunnattuihin graafisiin ja toinen suuntaamattomiin graafisiin. Tässä artikkelissa termiä "syklinen sijoitus" käytetään suunnatuille kuvaajille ja "ääriviivat" suuntaamattomille kuvaajille.
  2. ↑ 12 Berge , 2001 , s. 27–30.
  3. ↑ Venäjänkielisessä kirjallisuudessa käytetään myös termiä graphic matroid , joka on englanninkielisen graafisen matroidin kuultopaperi eikä täysin vastaa käsitteen ydintä.
  4. ↑ Kotiuga, 2010 , s. kaksikymmentä.
  5. ↑ Hage, 1996 , s. 48.
  6. ↑ Berge, 1976 , s. 477.
  7. ↑ Serre, 2003 , s. 23.
  8. ↑ Berkolaiko, Kuchment, 2013 , s. neljä.
  9. ↑ Buhl, Gautrais, Sole et ai., 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.

Kirjallisuus