|
グラフ理論におけるケーニヒの補題はデネス・ケーニヒ〔Note that, although Kőnig's name is properly spelled with a double acute accent, the lemma named after him is customarily spelled with an umlaut.〕 (1936)によって示された定理で、 無限グラフが無限長の道をもつための十分条件を与える。 この定理のcomputability aspectsは数理論理学の計算可能性理論の研究者によって調べられてきている。 この定理は構成的数学や証明論においても重要な役割をもつ。 ==定理の内容== ''G''を無限個の点からなる連結グラフで全ての点の次数は有限（すなわちどの点も他の有限個の点としか接続していない）とする。 このとき、''G''は無限長の単純道（同じ点を2度通らない道）を持つ。 木に対して制限したバージョンがこの定理の特殊な例としてよく知られている。 次数は有限である必要があるが有界である必要はないことに注意。すなわち各点の次数が10,100,1000…という増加列を構成していてもよい。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ケーニヒの補題」の詳細全文を読む スポンサード リンク
|