全域木

日本情報オリンピックのためのトレーニング合宿で使用されたらしいスライド。

様々な全域木問題:前原貴憲

閲覧用のURLはこちら
http://www.slideshare.net/tmaehara/ss-17402143


全域木(英語表記は Spanning tree、「極大木」とも呼ばれる)は、グラフ理論の分野で用いられる用語で、すべての点を閉路無しで結ぶグラフのこと。
上位のスライドでは、この全域木に関する諸問題の解説がされている。

ちなみに日本情報オリンピックは、オフィシャルサイトで次のように紹介されている。

日本の高校生以下の生徒の中から情報科学的な能力の豊かな生徒を見出し、その才能の育成を助けるとともに、国際情報オリンピック(International Olympiad in Informatics, IOI)に日本代表選手として派遣するために、特定非営利活動法人 情報オリンピック日本委員会(略称:IOI日本委員会)が主催している事業です。

http://www.ioi-jp.org/joi/index.html

高校生以下を対象としているにしては、とても高度な内容だ。
日本情報オリンピックの過去の問題と解答が、次のURLで公開されている。
http://www.ioi-jp.org/joi/index.html


前原貴憲氏による「各種アルゴリズムC++ による実装」
http://www.prefield.com/index.html

グラフ理論入門 (数理科学ライブラリ (2))

グラフ理論入門 (数理科学ライブラリ (2))