Rang kola

U matematičkoj teoriji grafova, rang kola, broj ciklusa,ništa od neusmerenog grafa $G(x)$ je minimalan broj $r(x)$ uklonjenih grana iz $G(x)$ do uklonjenih svih ciklusa, koji čine drvo. Za razliku od problema povratnog luka kod usmerenih grafova, lako ih je prebrojiti koristeći formulu:

$r=m-n+c$,

gde je $m$ broj grana u $G$, $n$ je broj čvorova i $c$ je broj povezanih komponenti.

Slični koncepti

Strujno kolo je korang grafičkog matroida $G$, iz kog se vidi da pohlepni algoritam uklanja jednu po jednu granu, u svakom koraku uklanja granu koja prirada jednom ciklusu preostalog grafa, tražeći uklonjene grane grane $r$ iz grafa $G$. S druge strane (alternativno), to može biti dopuna grafa $G$. Broj ciklusa je takođe dimenzija prostora ciklusa $G$. Topološki, $G$ se može posmatrati kao primer jednodimenzionog uprošćenog kompleksa i njen cyclomatic broj je rang prvog (ceo broj) homogena grupa ovog kompleksa,

$r=\mathrm{rank}[H_1(G,\mathbb{Z})].$

Strujno kolo kontroliše broj ulaznih grana i razlaganje grafa: u povezanom grafu strujno kolo ranga $r$ svaka grana ima tačno $r$ potomka.

Skoro drveće

Graf sa $r$ brojem ciklusa se zove r-skoro-drvo, zato što jedino $r$ grane treba da budu uklonjene da bi se napravilo drvo ili stablo. 1-skoro-drvo je skoro-drvo: povezano skoro-drvo je pseudodrvo ciklus sa (moguće trivijalno) drvo ukorenjeno u svaki čvor. Neki autori su proučavali parametrizovanu složenost grafova algoritma na r-skoro-drvo, parametrizovanog po $r$.