Cirkvita rango

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo

La cirkvita rango de grafeo G estas la minimuma kvanto m de lateroj kiuj necesas forpreni por ke la grafeo estu sencikla. Ĝi povas esti kalkulita kiel

r = m - n + c

kie m estas la kvanto de lateroj en G

n estas la kvanto de verticoj en G
c estas la kvanto de koneksaj komponantoj de G

Arbo kaj arbaro havas cirkvitan rangon 0.