１．１計算の基礎理論(3)

１．１．３グラフ理論　（图论）

俺晕！这一个小节就是俺们大学里的一门课啊。这区区1页纸，说了这点儿皮毛，到底让俺掌握到哪种深度呢？
图论，在大学都没学好——当时教课的老师都不会。

---

グラフ：辺の集合と点の集合からなる図形である。
木：閉路のないグラフである。(閉路＝loop自分自身に戻ってくるパス)
ｎ進木：ノードが高々ｎ個の子を持つ木をｎ進木或いはｎ分木と言う。
順序木(ordered tree)：ノード間に順序がある木。
探索木：各ノードに要素を格納している木。
2分探索木：各ノードに値を持ち、左の子の値≦自ノードの値≦右の子の値となっている2分木を2分探索木と言う。
ヒープ(heap)：ノードの値と子の値の間に大小関係が成立している2分木である。関係は自ノードの値≦子ノードの値と自ノードの値≧子ノードの値と二種類がある。
AVL木：どのノードにおいても、左右の部分木の高さが高々１しか違わない2分木である。考案したAdelson-Velskii-Landisの頭文字からAVL木と呼ばれる。
B木：m≧3。葉以外の各節点の子供の数の最大はmである。子供の数の最小は≧m/2の最小整数。根の子供の数のは最小で2である。根から葉までの深さはどの葉についても同じである。