グラフ理論
-
五色定理とグラフ理論①―握手補題の証明―
和からの数学講師の岡本です。今回は前回に引き続き、「塗り絵」に関する問題を、数学的に取り扱うことについて簡単にまとめていこうと思います。 １．色分けとグラフ理論 色分けを数学的に取り扱うために、グラフ理論を利用します。以前グラフ理論について簡単にまとめた記事があるので、そちらも併せてご覧ください。 https://wa…
2022年7月4日
-
必見！？ホールの結婚定理！～結婚できるとは言っていない～
和からの数学講師の岡本です。今回は「ホールの結婚定理」という、ものすごい名前の定理をご紹介しようと思います。この定理はグラフ理論、組み合わせ理論に関する有名な定理であり、イギリスの数学者フィリップ・ホールに由来します。グラフ理論に関する話題は以前マスログでいくつかご紹介しました。 https://wakara.co.j…
2021年9月2日
-
水平思考ゲーム後編～グラフのスープ～
頂点や辺の数などのヒントを手がかりに、質問を重ねてグラフの形を当てる「グラフのスープ」。ウミガメのスープをグラフ理論版にアレンジした岡本オリジナルのゲームを、ループ・多重辺・連結・同型といった基本用語とあわせて仮想対戦で紹介します。
2020年11月15日
-
路線・ネットワークの数学～グラフ理論への誘い（後編）～
5つの街を交差点なしで互いに道路で結べるかという問題を、グラフ理論で解決する後編です。オイラーの多面体定理から平面グラフが満たす不等式を導き、背理法で5次完全グラフK5が平面グラフでないことを示します。
2020年11月1日
-
路線・ネットワークの数学～グラフ理論への誘い（前編）～
和からの数学講師の岡本です。今回は「路線設計」の問題をグラフ理論の言葉で置き換える話をします。以前「グラフ理論」に関連する記事を書いたので、こちらも併せてご覧ください。 https://wakara.co.jp/mathlog/20200701 https://wakara.co.jp/mathlog/20201002…
2020年10月30日
-
一筆書きの数学からモノクロデザインへ
「田」の字は一筆書きできるのか。ケーニヒスベルクの橋の問題を出発点に、奇頂点が0個か2個なら一筆書きできるというオイラーの定理と、一筆書きのループで描いた模様は白黒2色で塗り分けられる性質を、切り絵のデザインとあわせて紹介します。
2020年7月1日
