内周 (グラフ理論)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/27 01:49 UTC 版)
数学のグラフ理論の分野における内周（ないしゅう、英: girth）とは、グラフに含まれる最小の閉路の長さのことを言う[1]。もしもグラフが閉路を含まないなら（すなわち、無閉路グラフであるなら）、その内周は無限大と定義される[2]。例えば、（平方）4-閉路グラフの内周は4である。格子グラフの内周も4である。三角形メッシュの内周は3である。内周が4以上のグラフは、トライアングルフリーである。
- ^ R. Diestel, Graph Theory, p.8. 3rd Edition, Springer-Verlag, 2005
- ^ Girth -- Wolfram MathWorld
- ^ Brouwer, Andries E., Cages. Electronic supplement to the book Distance-Regular Graphs (Brouwer, Cohen, and Neumaier 1989, Springer-Verlag).
- ^ Erdős, Paul (1959), “Graph theory and probability”, Canadian Journal of Mathematics 11: 34–38, doi:10.4153/CJM-1959-003-9.
[続きの解説]
「内周 (グラフ理論)」の続きの解説一覧
- 1 内周 (グラフ理論)とは
- 2 内周 (グラフ理論)の概要
- 内周_(グラフ理論)のページへのリンク
