たく
卒業研究の題材である「グラフ理論」について自分なりにまとめてみました。
みなさん、こんにちは。 今回は四色問題について紹介していきたいと思います。 【１】四色問題とは何か？まずは四色問題について紹介します。 地図を色分けしていくとき、私たちはごく自然に、隣り合う国々を違う色で塗り分けていきます。なぜなら、その方が区別しやすいからです。 下の図は、アメリカの州を隣り合う州を違った色になるように4色で塗り分けられています。 どんな地図でも、このようにたった4色で塗り分けることができるでしょうか？ 一見すると、地図が複雑になればなるほど、も
みなさん、こんにちは。 今回はパーティにおける問題を紹介し、その問題からラムゼーの定理を導いていきたいと思います。 【１】パーティ問題とは？この問題(命題)を証明する道具として、完全グラフをつかいます。 今回は6人ですので、K₆をつかいたいと思います。 【２】パーティ問題の証明のための準備まず、6人をそれぞれ、Aさん、Bさん、Cさん、Dさん、Eさん、Fさんとします。K₆のグラフの頂点に、それぞれAさんからFさんまでを対応させて考えていきたいと思います。 次に、A～F
みなさん、こんにちは。 今回はオイラーの多面体定理について紹介していきたいと思います。 オイラーの多面体定理は高校1年生の教科書で出てくる定理です。 しかし、大学入試ではほとんど出題されることがないため、影が薄い定理であると私は感じています。 ということで、今回はこのオイラーの多面体定理を主役に記事を書いていこうと思います。 【１】オイラーの多面体定理とは？まずは、オイラーの多面体定理について紹介します。 V、E、F は頂点(vertex)、辺(edge)、面(fa
みなさん、こんにちは。 今回はケーニヒスベルクの７つの橋の問題と一筆書きの定理について紹介していきたいと思います。 【１】ケーニヒスベルクの7つの橋の問題とは？ 18世紀ごろ、プロイセン王国の東部にケーニヒスベルク(現ロシア連邦カリーニングラード)という町がありました。この町の中央にはプレーゲル川という大きな川が流れており、７つの橋が架けられていました。 あるとき、町の人が言いました。 「このプレーゲル川に架かっている７つの橋を2度通らずに、全て渡って帰ってくること
みなさん、こんにちは。 今回はグラフ理論とは何かについて例を用いて中学生や高校生にもわかりやすく紹介していきたいと思います。 基礎レベルから応用レベルまで紹介できたらなと思っています。 【１】グラフ理論とは何かグラフという言葉は聞きなれた人も多いとは思います。統計を用いるときの円グラフや棒グラフ、中学校の数学の授業で出てきた比例のグラフなどを想像した人も多いのではないでしょうか。 しかし、グラフ理論における「グラフ」というのはそれらとは全く異なるものなのです。 では
