[B! グラフ理論] n_knuuのブックマーク

日本の中心はどの県だ？グラフ理論（ネットワーク）の基本的な諸概念 - アジマティクス

Ｑ：これは何の構造を表しているでしょう？グラフ理論上の構造のように、頂点（ノードともいいます）の集まりと、２つの頂点をつなぐ辺（エッジともいいます）の集まりでできたもののことを「グラフ」あるいは「ネットワーク」と呼び*1、このような構造を研究する分野こそが「グラフ理論（Graph theory）」です。今回はそんなグラフを使うと、身近なものの新たな側面が見えてくる話。（余談ですが「グラフ」という用語は、数学だと関数のグラフとか円グラフみたいなやつもあって検索精度が悪いです。グラフ理論に関してわからないことがあった場合に「グラフ　○○」や「グラフ理論　○○」とググるよりも、「ネットワーク　○○」とググったほうが得たい情報にリーチしやすいというライフハックが知られています）さて、冒頭のグラフです。グラフ理論の知識なんかひとつもなくても、このグラフから読み取れることはいくつもあります。例

n_knuu 2018/01/30

グラフ理論

リンク

グラフ理論の問題 - OKWAVE

帰納法を使います。頂点数が2の時(a)は成り立つ。頂点数が2以上k以下の時(a)が成り立つと仮定すると、頂点数がk+1の時、 1)グラフに辺が一本も無いとき、明らか。 2)グラフが非連結で辺が一本以上あるとき、このグラフは頂点数2以上k以下の連結成分を持つ。この連結成分は帰納法の仮定より同じ次数の頂点を持つ。よってこのグラフも同じ次数の頂点を持つ。 3)グラフが連結であるとき、各頂点の次数は1以上k以下のk種類である。頂点はk+1個あるので鳩の巣原理より、同じ次数の頂点が存在する。以上より(a)は成り立つ。もうちょっとうまいやり方がありそうなものですが、ちと思い付きませんでした。