| dbo:abstract
|
- 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 -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ó: , ahol m az adott gráf éleinek száma, n a csúcsok száma, c pedig az összefüggő komponenseké. A köröket felbontó minimális méretű élhalmaz előállítható akár mohó algoritmus, akár egy komplementálása segítségével. A ciklikus rang az algebrai gráfelmélet fogalmai szerint a gráf dimenziószáma, a 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 egyike. Megszámolja a gráf található füleket, a majdnem-fák alapját képezi, a 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. (hu)
- 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 -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ó: , ahol m az adott gráf éleinek száma, n a csúcsok száma, c pedig az összefüggő komponenseké. A köröket felbontó minimális méretű élhalmaz előállítható akár mohó algoritmus, akár egy komplementálása segítségével. A ciklikus rang az algebrai gráfelmélet fogalmai szerint a gráf dimenziószáma, a 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 egyike. Megszámolja a gráf található füleket, a majdnem-fák alapját képezi, a 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. (hu)
|
