Pořadí vrstevnic

V teorii grafů je hodnost obrysu [1] neorientovaného grafu minimální počet hran, jejichž odstranění zničí všechny cykly grafu a změní jej ve strom nebo les. Pořadí vrstevnic lze také chápat jako počet nezávislých cyklů v grafu. Na rozdíl od odpovídajícího problému nalezení sady oblouků pro řezání cyklem pro orientované grafy lze hodnost obrysu r snadno vypočítat podle vzorce

,

kde m je počet hran daného grafu, n je počet vrcholů a c je počet spojených komponent [2] . Je také možné efektivně zkonstruovat sadu hran s minimální velikostí, které přeruší cykly pomocí buď hltavého algoritmu nebo doplňku spanning tree .

Pořadí vrstevnic je také známé jako cyklomatické číslo grafu. Lze jej vysvětlit z hlediska algebraické teorie grafů jako rozměr cyklického prostoru grafu, z hlediska matroidů pomocí pojmu corank grafových matroidů [3] a z hlediska topologie jako jednu z Betti čísla topologického prostoru odvozená z grafu. Pořadí vrstevnic počítá počet uší v ušním rozkladu grafu, který poskytuje základ pro představu složitosti na téměř stromech a používá se v softwarových metrikách jako součást definice cyklomatické složitosti části kódu. Pod názvem cyklomatická složitost pojem představil Gustav Kirchhoff [4] [5] .

Hodnost matroidu a konstrukce minimální sady na řezání cyklů

Pořadí vrstevnic grafu G lze popsat pomocí teorie matroidů jako korek matroidu grafu pro G [6] . S přihlédnutím k chamtivé vlastnosti matroidů to znamená, že je možné najít minimální množinu hran, které zničí všechny cykly, pomocí algoritmu greedy , který v každém kroku vybere hranu, která patří alespoň jednomu cyklu zbývajícího grafu.

Na druhou stranu, minimální množinu množin, která přeruší všechny cykly, lze nalézt vytvořením překlenovacího lesa G a výběrem komplementární množiny hran, které do překlenovacího lesa nepatří.

Počet nezávislých cyklů

V algebraické teorii grafů je pozice obrysu rozměrem prostoru cyklu grafu . Intuitivně lze hodnost kontury vysvětlit jako počítání počtu nezávislých cyklů grafu, kde množina cyklů je považována za nezávislou, pokud není možné vytvořit jeden cyklus jako symetrický rozdíl nějaké podmnožiny jiných cyklů [2] .

Tento počet nezávislých cyklů lze vysvětlit pomocí teorie homologie , odvětví topologie . Jakýkoli graf G lze považovat za příklad jednorozměrného simpliciálního komplexu , jednoho typu topologického prostoru , vytvořeného reprezentací každé hrany grafu segmentem a slepením těchto segmentů na koncích. Cyklomatické číslo je hodnost první (celočíselné) homologní skupiny tohoto komplexu [7] ,

V souvislosti s takovým topologickým spojením se cyklomatické číslo grafu G nazývá také prvním Bettiho číslem grafu G [8] . Obecněji platí, že první Bettiho číslo jakéhokoli topologického prostoru počítá počet nezávislých cyklů v prostoru.

Hodnost obrysu grafu souvisí s hodností jeho incidenční matice prostřednictvím vztahu .

Aplikace

Koeficient síťování

Varianta hodnosti vrstevnic rovinného grafu , normalizovaná dělením maximální možnou hodností vrstevnic libovolného rovinného grafu se stejnou sadou vrcholů, se nazývá faktor započtení . Pro spojené rovinné grafy s m hranami a n vrcholy lze koeficient sítě vypočítat pomocí vzorce [9]

V tomto vzorci je čitatelem ve vzorci hodnost obrysu daného grafu a jmenovatelem je největší možná hodnost obrysu rovinného grafu s n vrcholy. Faktor sítě leží mezi 0 pro stromy a 1 pro maximální rovinné grafy .

Rozklad ucha

Pořadí vrstevnic odráží počet uší v ušním rozkladu grafu, rozklad hran grafu na dráhy a cykly, což je často užitečné v grafových algoritmech. Konkrétně graf je spojen s vrcholem 2 tehdy a jen tehdy, když má otevřený klasový rozklad, sekvenci podgrafů, ve kterých první podgraf je jednoduchý cyklus a zbývající podgrafy jsou jednoduché cesty a každá cesta začíná a končí ve vrcholech. patřící do předchozích podgrafů a každý vnitřní vrchol cesty se v této cestě objeví poprvé. V jakémkoli biconnected grafu s vrstevnicovou hodností má každý rozklad otevřeného ucha přesně uši [10] .

Téměř stromy

Graf s cyklomatickým číslem se také nazývá téměř r - strom , protože z grafu je třeba odstranit pouze r hran, aby se změnil na strom nebo les. Téměř 1-strom je téměř strom — spojený téměř strom je pseudoles , cyklus s (možná triviálními) stromy zakořeněnými v každém vrcholu [11] .

Někteří autoři studovali parametrizovanou složitost algoritmů na téměř r -stromech s parametrizací podle [12] [13] .

Zobecnění pro orientované grafy

Cyklická hodnost je orientovaný invariant grafu , který měří úroveň vnoření cyklů do grafu. Tento invariant má složitější definici než cyklomatická hodnost (úzce souvisí s definicí hloubky stromu pro neorientované grafy) a je mnohem obtížnější jej vypočítat. Dalším problémem pro orientované grafy týkající se cyklomatického pořadí je stanovení minimální sady oblouků pro řezání cyklu , tedy minimální sady oblouků, jejichž odstranění zničí všechny směrované cykly. Oba problémy, výpočet pořadí cyklů a určení minimální sady oblouků, které cykly přeruší, jsou NP-těžké .

Je také možné vypočítat jednodušší invariant orientovaných grafů ignorováním směrů hran a výpočtem cyklické hodnosti neorientovaného grafu. Tento princip tvoří základ pro definování cyklomatické složitosti , měřítka složitosti počítačového programu pro odhadování složitosti části počítačového kódu.

Související pojmy

Další čísla definovaná jako odstranění hran z neorientovaného grafu zahrnují konektivitu hran , minimální počet hran, jejichž odstranění způsobí ztrátu konektivity, a odpovídající počet vyhýbání , minimální počet hran, jejichž odstranění způsobí ukončení dokonalého párování . existovat .

Poznámky

  1. ↑ V ruskojazyčné literatuře se jak hodnost cyklu, tak hodnost obvodu často překládá stejným způsobem – cyklická hodnost. V anglické literatuře se první termín vztahuje k řízeným grafům, druhý k neorientovaným grafům. V tomto článku se termín „cyklická pozice“ používá pro orientované grafy a „pořadí vrstevnic“ pro neorientované grafy.
  2. ↑ 12 Berge , 2001 , s. 27–30.
  3. ↑ V ruskojazyčné literatuře se také používá termín graphic matroid , což je pauzovací papír anglického graphic matroid a ne zcela odpovídá podstatě konceptu.
  4. ↑ Kotiuga, 2010 , str. dvacet.
  5. ↑ Hage, 1996 , str. 48.
  6. ↑ Berge, 1976 , s. 477.
  7. ↑ Serre, 2003 , str. 23.
  8. ↑ Berkolaiko, Kuchment, 2013 , s. čtyři.
  9. ↑ Buhl, Gautrais, Sole a kol., 2004 , str. 123–129.
  10. ↑ Whitney, 1932 , s. 339–362.
  11. ↑ Brualdi, 2006 , str. 349.
  12. ↑ Coppersmith, Vishkin, 1985 , str. 27–45.
  13. ↑ Fiala, Kloks, Kratochvíl, 2001 , str. 59–72.

Literatura