Kontúr rang

A gráfelméletben egy irányítatlan gráf kontúrrangja [1] azon élek minimális száma, amelyek eltávolítása a gráf minden ciklusát tönkreteszi, és fává vagy erdővé változtatja. A kontúr rangja felfogható egy gráf független ciklusainak számaként is. Ellentétben az irányított gráfok ciklusvágó ívkészletének megtalálásának megfelelő problémájával , az r kontúrrang könnyen kiszámítható a képlettel

,

ahol m az adott gráf éleinek száma, n a csúcsok száma , c pedig az összefüggő komponensek száma [2] . Hatékonyan létrehozható minimális méretű élek halmaza is, amelyek megszakítják a ciklusokat a mohó algoritmus vagy a feszítőfa komplementer használatával .

A kontúrrangot a gráf ciklomatikus számának is nevezik . Megmagyarázható az algebrai gráfelméletben a gráf ciklikus terének dimenziójaként , a matroidok szempontjából a gráfmatroidok koronája [3] használatával, topológia szempontjából pedig a Betti egyike. gráfból származtatott topológiai tér számai . A kontúrrang a fülek számát számolja meg egy gráf füldekompozíciójában , amely szinte fákon alapozza meg a komplexitás fogalmát, és a szoftvermetrikákban egy kódrészlet ciklomatikus összetettségének meghatározása részeként használatos. Ciklomatikus komplexitás néven a fogalmat Gustav Kirchhoff [4] [5] vezette be .

Matroid rang és egy minimális ciklusvágó készlet felépítése

A G gráf kontúrrangja a matroid elmélet segítségével leírható, mint egy gráfmatroid koronja G -hez [6] . Figyelembe véve a matroidok mohó tulajdonságát, ez azt jelenti, hogy meg lehet találni azt a minimális élhalmazt, amely minden ciklust megsemmisít a mohó algoritmus segítségével , amely minden lépésben kiválaszt egy élt, amely a fennmaradó gráf legalább egy ciklusához tartozik.

Másrészt az összes ciklust megszakító halmaz minimális halmazát úgy találhatjuk meg, hogy megszerkesztjük a G feszítőerdőjét , és kiválasztunk egy kiegészítő élhalmazt, amely nem tartozik a feszítő erdőhöz.

Független ciklusok száma

Az algebrai gráfelméletben a kontúrrang a gráf ciklusterének dimenziója . Intuitív módon a kontúrrangsor egy gráf független ciklusainak megszámlálásával magyarázható, ahol egy ciklushalmaz akkor tekinthető függetlennek, ha lehetetlen egy ciklust más ciklusok valamelyik részhalmazának szimmetrikus különbségeként létrehozni [2] .

Ez a független ciklusszám a homológia elmélettel, a topológia egyik ágával magyarázható . Bármely G gráf tekinthető egy 1-dimenziós egyszerűsített komplexnek , a topológiai tér egyik típusának , amelyet úgy alakítunk ki, hogy a gráf minden élét egy szegmenssel ábrázoljuk, és ezeket a szegmenseket a végeihez ragasztjuk. A ciklomatikus szám a komplex első (egész) homológiacsoportjának rangja [7] ,

Egy ilyen topológiai kapcsolat kapcsán a G gráf ciklomatikus számát a G gráf első Betti - számának is nevezik [8] . Általánosabban, bármely topológiai tér első Betti-száma a térben lévő független ciklusok számát számolja.

Egy gráf kontúrrangja a reláción keresztül kapcsolódik az előfordulási mátrix rangjához .

Alkalmazások

Retikulációs együttható

Egy síkgráf kontúrrangsorának egy változatát , amelyet úgy normalizálunk, hogy elosztjuk bármely, azonos csúcskészletű síkgráf lehetséges kontúrrangsorával, nettó tényezőnek nevezzük . Összekapcsolt, m élű és n csúcsú síkgráfok esetén a hálózati együttható a [9] képlet segítségével számítható ki .

Ebben a képletben a képletben szereplő számláló az adott gráf kontúrrangja, nevezője pedig egy n csúcsú síkgráf lehetséges legnagyobb kontúrrangja . A hálótényező fák esetén 0 és maximális síkgráfok esetén 1 között van .

Fül bomlás

A kontúrrang a fülek számát tükrözi a gráf füldekompozíciójában , a gráf éleinek pályákra és ciklusokra bontását, ami gyakran hasznos a gráfalgoritmusokban. Konkrétan egy gráf akkor és csak akkor kapcsolódik a 2-es csúcshoz , ha nyitott fülű dekompozíciója van, olyan részgráfok sorozata, amelyben az első részgráf egy egyszerű ciklus, a többi részgráf pedig egyszerű utak, és minden út csúcsokban kezdődik és végződik. az előző részgráfokhoz tartoznak, és az útvonal minden belső csúcsa először ezen az útvonalon jelenik meg. Bármely kontúrrangú kétösszefüggõ gráfban minden nyitott fül dekompozíciónak pontosan vannak fülei [10] .

Majdnem fák

A ciklomatikus számmal rendelkező gráfot majdnem r - fának is nevezik , mivel csak r élt kell eltávolítani a gráfból, hogy fává vagy erdővé alakítsuk. Egy majdnem 1-fa majdnem egy fa – egy összefüggő majdnem fa egy álerdő , egy ciklus (esetleg triviális) fákkal, amelyek minden csúcsában gyökereznek [11] .

Egyes szerzők a [12] [13] szerinti paraméterezéssel vizsgálták az algoritmusok parametrizált komplexitását majdnem r -fákon .

Általánosítás irányított gráfokhoz

A ciklikus rang egy irányított gráfinvariáns , amely a ciklusok egymásba ágyazásának szintjét méri egy gráfban. Ennek az invariánsnak a definíciója bonyolultabb, mint a ciklomatikus rangnak (szorosan kapcsolódik az irányítatlan gráfok famélységének meghatározásához), és sokkal nehezebb kiszámítani. A ciklomatikus ranghoz kapcsolódó irányított gráfok másik problémája a minimális ciklusvágó ívhalmaz meghatározása, vagyis az ívek azon minimális halmaza, amelynek eltávolítása az összes irányított ciklust tönkreteszi. Mindkét probléma, a ciklikus rang kiszámítása és a ciklusokat levágó ívek minimális halmazának meghatározása, NP-nehéz .

Lehetőség van irányított gráfok egyszerűbb invariánsának kiszámítására is az élirányok figyelmen kívül hagyásával és egy irányítatlan gráf ciklikus rangjának kiszámításával. Ez az elv képezi az alapját a ciklomatikus komplexitás meghatározásának , amely a számítógépes program bonyolultságának mértéke egy számítógépes kódrészlet összetettségének becsléséhez.

Kapcsolódó fogalmak

Az irányítatlan gráf éleinek eltávolítására vonatkozó egyéb számok közé tartozik az élösszeköthetőség , azon élek minimális száma, amelyek eltávolítása a kapcsolat elvesztését okozza, és az illesztés elkerülési szám , azon élek minimális száma, amelyek eltávolítása a tökéletes illeszkedést megszünteti. létezni .

Jegyzetek

  1. ↑ Az orosz nyelvű irodalomban a ciklusrangot és az áramköri rangot is gyakran ugyanúgy fordítják - ciklikus rangot. Az angol szakirodalomban az első kifejezés az irányított gráfokra, a második az irányítatlan gráfokra vonatkozik. Ebben a cikkben a „ciklikus rang” kifejezést az irányított gráfokra, a „kontúrrang” kifejezést az irányítatlan gráfokra használjuk.
  2. ↑ Berge 12. , 2001 , p. 27–30.
  3. ↑ Az orosz nyelvű szakirodalomban a graphic matroid kifejezés is használatos, ami az angol graphic matroid pauszpapírja, és nem egészen felel meg a fogalom lényegének.
  4. ↑ Kotiuga, 2010 , p. húsz.
  5. ↑ Hage, 1996 , p. 48.
  6. ↑ Berge, 1976 , p. 477.
  7. ↑ Serre, 2003 , p. 23.
  8. ↑ Berkolaiko, Kuchment, 2013 , p. négy.
  9. ↑ Buhl, Gautrais, Sole et al., 2004 , p. 123–129.
  10. ↑ Whitney, 1932 , p. 339–362.
  11. ↑ Brualdi, 2006 , p. 349.
  12. ↑ Coppersmith, Vishkin, 1985 , p. 27–45.
  13. ↑ Fiala, Kloks, Kratochvíl, 2001 , p. 59–72.

Irodalom