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ó:

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]

Matroid rangja és a minimális visszacsatoló élhalmaz konstruálása

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.

A független körök száma

Az algebrai gráfelmélet szerint a ciklikus rang egyben $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]

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.

Alkalmazások

Behálózottsági együttható

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]

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

Itt a számlálóban az $m-n+1$ az adott gráf ciklikus rangja, a nevező $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.

Fülfelbontás

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ő, $r$ ciklomatikus számú gráf tetszőleges nyitott fülfelbontásában pontosan $r$ a fülek száma.^[8]

Majdnem-fák

Egy $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, $r$ szerint parametrizálva.^[10]^[11]

Irányított gráfokra való általánosítások

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.

Számítási kémia

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]

Kapcsolódó fogalmak

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.

Fordítás

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.

Jegyzetek

↑ ^a ^b Berge, Claude (2001), "Cyclomatic number", The Theory of Graphs, Courier Dover Publications, pp. 27–30, ISBN 9780486419756, <https://books.google.com/books?id=h5BjnaoKyOwC&pg=PA27>.
↑ Peter Robert Kotiuga. A Celebration of the Mathematical Legacy of Raoul Bott. American Mathematical Soc., 20. o. (2010). ISBN 978-0-8218-8381-5
↑ Per Hage. Island Networks: Communication, Kinship, and Classification Structures in Oceania. Cambridge University Press, 48. o. (1996). ISBN 978-0-521-55232-5
↑ Berge, Claude (1976), Graphs and Hypergraphs, vol. 6, North-Holland Mathematical Library, Elsevier, p. 477, ISBN 9780720424539, <https://books.google.com/books?id=Wy2mhanRnk4C&pg=PA477>.
↑ Serre, Jean-Pierre (2003), Trees, Springer Monographs in Mathematics, Springer, p. 23, <https://books.google.com/books?id=MOAqeoYlBMQC&pg=PA23>.
↑ Introduction to Quantum Graphs. American Mathematical Soc., 4. o. (2013). ISBN 978-0-8218-9211-4
↑ Buhl, J.; Gautrais, J. & Sole, R.V. et al. (2004), "Efficiency and robustness in ant networks of galleries", The European Physical Journal B (Springer-Verlag) 42 (1): 123–129, DOI 10.1140/epjb/e2004-00364-9.
↑ Whitney, H. (1932), "Non-separable and planar graphs", Transactions of the American Mathematical Society 34: 339–362, DOI 10.2307/1989545. Lásd főleg: Theorem 18 (a fülfelbontás és a ciklikus rang összefüggéséről) és Theorem 19 (a fülfelbontások létezéséről).
↑ Brualdi, Richard A. (2006), Combinatorial Matrix Classes, vol. 108, Encyclopedia of Mathematics and Its Applications, Cambridge: Cambridge University Press, p. 349, ISBN 0-521-86565-4
↑ Coppersmith, Don & Vishkin, Uzi (1985), "Solving NP-hard problems in 'almost trees': Vertex cover", Discrete Applied Mathematics 10 (1): 27–45, DOI 10.1016/0166-218X(85)90057-5.
↑ Fiala, Jiří; Kloks, Ton & Kratochvíl, Jan (2001), "Fixed-parameter complexity of λ-labelings", Discrete Applied Mathematics 113 (1): 59–72, DOI 10.1016/S0166-218X(00)00387-5.
↑ (2014) „Efficient ring perception for the Chemistry Development Kit”. Journal of Cheminformatics 6 (3). DOI:10.1186/1758-2946-6-3. PMID 24479757. PMC 3922685.
↑ (1989) „A review of Ring Perception Algorithms for Chemical Graphs”. J. Chem. Inf. Comput. Sci. 29 (3), 172–187. o. DOI:10.1021/ci00063a007.
↑ (1939) „No. 108-Condensation d'une molecule organique”. Bull. Soc. Chim. Fr. 5, 1008–1011. o.

[berge-1] Berge, Claude (2001), "Cyclomatic number", The Theory of Graphs, Courier Dover Publications, pp. 27–30, ISBN 9780486419756, <https://books.google.com/books?id=h5BjnaoKyOwC&pg=PA27>.

[Kotiuga2010-2] Peter Robert Kotiuga. A Celebration of the Mathematical Legacy of Raoul Bott. American Mathematical Soc., 20. o. (2010). ISBN 978-0-8218-8381-5

[Hage1996-3] Per Hage. Island Networks: Communication, Kinship, and Classification Structures in Oceania. Cambridge University Press, 48. o. (1996). ISBN 978-0-521-55232-5

[4] Berge, Claude (1976), Graphs and Hypergraphs, vol. 6, North-Holland Mathematical Library, Elsevier, p. 477, ISBN 9780720424539, <https://books.google.com/books?id=Wy2mhanRnk4C&pg=PA477>.

[5] Serre, Jean-Pierre (2003), Trees, Springer Monographs in Mathematics, Springer, p. 23, <https://books.google.com/books?id=MOAqeoYlBMQC&pg=PA23>.

[BerkolaikoKuchment2013-6] Introduction to Quantum Graphs. American Mathematical Soc., 4. o. (2013). ISBN 978-0-8218-9211-4

[7] Buhl, J.; Gautrais, J. & Sole, R.V. et al. (2004), "Efficiency and robustness in ant networks of galleries", The European Physical Journal B (Springer-Verlag) 42 (1): 123–129, DOI 10.1140/epjb/e2004-00364-9.

[8] Whitney, H. (1932), "Non-separable and planar graphs", Transactions of the American Mathematical Society 34: 339–362, DOI 10.2307/1989545. Lásd főleg: Theorem 18 (a fülfelbontás és a ciklikus rang összefüggéséről) és Theorem 19 (a fülfelbontások létezéséről).

[CMC349-9] Brualdi, Richard A. (2006), Combinatorial Matrix Classes, vol. 108, Encyclopedia of Mathematics and Its Applications, Cambridge: Cambridge University Press, p. 349, ISBN 0-521-86565-4

[10] Coppersmith, Don & Vishkin, Uzi (1985), "Solving NP-hard problems in 'almost trees': Vertex cover", Discrete Applied Mathematics 10 (1): 27–45, DOI 10.1016/0166-218X(85)90057-5.

[11] Fiala, Jiří; Kloks, Ton & Kratochvíl, Jan (2001), "Fixed-parameter complexity of λ-labelings", Discrete Applied Mathematics 113 (1): 59–72, DOI 10.1016/S0166-218X(00)00387-5.

[12] (2014) „Efficient ring perception for the Chemistry Development Kit”. Journal of Cheminformatics 6 (3). DOI:10.1186/1758-2946-6-3. PMID 24479757. PMC 3922685.

[13] (1989) „A review of Ring Perception Algorithms for Chemical Graphs”. J. Chem. Inf. Comput. Sci. 29 (3), 172–187. o. DOI:10.1021/ci00063a007.

[14] (1939) „No. 108-Condensation d'une molecule organique”. Bull. Soc. Chim. Fr. 5, 1008–1011. o.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]