Rank

ここでも話を有限(辺の数も頂点の数も)で連結(connected)なグラフに限りましょう。そのグラフについて辺を順に除いていって最後に木が残るとしましょう。なるべく少ない個数の辺を除いて木をつくります。この時除く辺の最小値をそのグラフのランク(Rank)といいます。
ランクはそのグラフの中にあるcycleの数でもあります。ただし8の字の形においてはcycleは3でなく2と考えます。あるいはランクはsimple cycleの数であるといってもよいでしょう。
ランクはグラフのひとつの特徴を表す量です。


前ページの眼鏡型のランクはなにか?

眼鏡の両端を除くと左図のようになりこれは木であるからランクは2。