Ciklikus rang

A matematika, azon belül a gráfelmélet területén egy irányítatlan gráf ciklikus rangja vagy ciklomatikus száma (circuit rank, cyclomatic number, cycle rank, nullity) az élek minimális száma, melynek eltávolításával a gráf összes köre felbomlik, így a gráf fa vagy erdő lesz. Felfogható úgy is, mint a gráf független köreinek száma. Az irányított gráfok visszacsatoló élhalmaz-problémájától eltérően az r-rel jelölt ciklikus rang a következő képlettel könnyen kiszámítható:

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

ahol m az adott gráf éleinek száma, n a csúcsok száma, c pedig az összefüggő komponenseké. ^[1] A köröket felbontó minimális méretű élhalmaz előállítható akár mohó algoritmus, akár egy feszítőerdő komplementálása segítségével.

A ciklikus rang az algebrai gráfelmélet fogalmai szerint a gráf körterének dimenziószáma, a matroidelmélet szerint a grafikus matroid defektusa (rendjének és rangjának különbsége), a topológia fogalmai szerint pedig a gráfból nyert topologikus tér Betti-számainak egyike. Megszámolja a gráf fülfelbontásában található füleket, a majdnem-fák parametrizált komplexitásának alapját képezi, a szoftvermetrikákban a programkód ciklomatikus bonyolultsága definíciójának részét képezi. A fogalmat Gustav Kirchhoff vezette be ciklomatikus szám néven.^[2][3]

Egy G gráf ciklikus rangja a matroidelmélet leírásában G grafikus matroidjának defektusával egyezik meg.^[4] A matroidok mohó tulajdonságát felhasználva ez azt jelenti, hogy az összes kört felbontó minimális élhalmazt egy mohó algoritmus előállítja, mely minden lépésben kiválaszt egy, a maradék gráf legalább egy köréhez tartozó élt.

Alternatív megoldásként a minimális élhalmaz előállítható G feszítőerdőjének segítségével, annak komplementer élhalmazát, tehát a feszítőerdőbe nem tartozó élek halmazát választva.

Az algebrai gráfelmélet szerint a ciklikus rang egyben ${\displaystyle G}$ körterének dimenziószáma. Intuitívan ez azzal magyarázható, hogy a ciklikus rang a gráf független köreit számolja meg; körök egy halmaza akkor független egymástól, ha a körök egyike sem áll elő a halmaz más köreinek szimmetrikus differenciájaként.^[1]

A független körök száma magyarázható a topológia egy ágának, a homológia-elméletnek az eszközeivel is. Bármely G gráf tekinthető egy egydimenziós szimpliciális komplexusnak, azaz a gráf éleit egyenes szakaszokkal lerajzolva és végpontjaiknál összeragasztva kapott topologikus térnek. A ciklomatikus szám ennek a komplexusnak az első (egész) homológiacsoportjának a rangja:^[5]

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

A topológiai összefüggés miatt a G gráf ciklomatikus számát G első Betti-számának is nevezik.^[6] Általánosabban, bármely topologikus tér első Betti-száma a tér független köreit számolja meg.

A síkbarajzolható gráfok ciklikus rangjának egy változatát, ami az ugyanazon csúcshalmazon lehetséges maximális ciklikus rang értékével van normalizálva, behálózottsági vagy ciklomatikus együtthatónak (meshedness coefficient) nevezik. Egy m éllel és n csúccsal rendelkező, összefüggő síkbarajzolható gráf behálózottsági együtthatóját a következő képlet adja meg:^[7]

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

Itt a számlálóban az ${\displaystyle m-n+1}$ az adott gráf ciklikus rangja, a nevező ${\displaystyle 2n-5}$-je pedig az n-csúcsú síkbarajzolható gráf lehetséges maximális ciklikus rangja. A ciklomatikus együttható minimális értéke 0, amit fák esetében, maximális értéke 1, amit maximális síkgráfokon vesz fel.

A ciklomatikus szám határozza meg a fülek számát a gráf fülfelbontásában; ez a gráf éleinek particionálása utakra és körökre, ami számos gráfalgoritmusban jól jön. Egy gráf pontosan akkor kétszeresen csúcsösszefüggő, ha rendelkezik „jó” avagy „nyitott” fülfelbontással. Ez részgráfok olyan sorozata, amiben az első részgráf egyszerű kör, a többi részgráf egyszerű út, minden út olyan csúcsról indul és olyan csúcson végződik, ami a korábbi részgráfokhoz tartozik, és az utak minden belső csúcsa az adott útban először fordul elő. Bármely kétszeresen összefüggő, ${\displaystyle r}$ ciklomatikus számú gráf tetszőleges nyitott fülfelbontásában pontosan ${\displaystyle r}$ a fülek száma.^[8]

Egy ${\displaystyle r}$ ciklomatikus gráf egyben egy r-majdnem-fa (r-almost-tree), mivel r él eltávolításával a gráf fává, illetve erdővé alakítható. Egy 1-majdnem-fa más néven közel-fa (near-tree): egy összefüggő közel-fa pedig egy pszeudofa, azaz egy kör, melynek minden csúcsában egy (esetleg triviális) fa gyökere található.^[9]

Számos szerző tanulmányozta az r-majdnem-fák gráfalgoritmusainak paraméteres bonyolultságát, ${\displaystyle r}$ szerint parametrizálva.^[10][11]

A körrang (cycle rank) irányított gráfokon értelmezett invariáns, ami a gráf köreinek beágyazottsági szintjét méri meg. A ciklikus rangnál bonyolultabban definiálható (a definíció rokonítható az irányítatlan gráfok famélységének definíciójával), és bonyolultabban számítható ki. A ciklikus ranghoz kapcsolódó másik, irányított gráfokra vonatkozó probléma a minimális visszacsatoló élhalmaz problémája: a legkisebb élhalmaz, melynek eltávolítása minden irányított kört felbont. A körrang és a minimális visszacsatoló élhalmaz kiszámítása is NP-nehéz to compute.

Az irányított gráfok egyszerűbb invariánsát úgy kaphatjuk, ha nem vesszük figyelembe az élek irányát és az így kapott irányítatlan gráf ciklikus rangját tekintjük. Ez az elv adja az alapját a ciklomatikus komplexitásnak, ami a számítógépi kód bonyolultságát becslő szoftvermetrikák egyike.

A kémia, illetve molekuláris informatika területén egy molekulagráf ciklikus rangját Frèrejacque-számnak is nevezik; ez a minimális körbázisban található gyűrűk száma.^[12][13][14]

Az irányítatlan gráfok éltörlési műveletével definiált egyéb számok közé tartozik az élösszefüggőség, a gráf összefüggőségének megszüntetéséhez törölni szükséges élek minimális száma, és a párosítás-kizárási szám (matching preclusion), a teljes párosítás megakadályozásához törölni szükséges élek minimális száma.

• Ez a szócikk részben vagy egészben a Circuit rank című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.