グラフ理論

大学で習うグラフ理論の内容がたったの3時間で復習できる記事の後編です。前編では、グラフ理論で重要な単元を浅く広く確認するための知識チェックをするための問題を3問用意しております。...

大学で習うグラフ理論の内容がたったの3時間で復習できる記事の後編です。後編では、グラフ理論で重要な単元をより深く実践的に問題演習することができます。...

こんにちは、ももやまです。 今回はグラフの彩色問題や、彩色問題を応用して下のような地図を塗り分ける方法などについてまとめています。     前回の離散数学（グラフ理論）の記事はこちら！ 平面グラフ・平面的グラフについてです。 www.momoyama-usagi.com   ０．はじめに 彩色問題は点彩色（頂点を塗り分...

こんにちは、ももやまです。 今回は平面グラフ・平面的グラフについてまとめていきたいと思います。 前回の記事はこちら！（第17羽） www.momoyama-usagi.com マッチングについてです！　「2人組をうまく組めるのか」などを離散数学（グラフ理論）の力で解いていく方法などの解説しているので興味がある人はぜひご...

こんにちは、ももやまです。   今回は離散数学・グラフ理論におけるマッチングについてまとめていきたいと思います。   マッチングを使うことで例えばこのような問題を解くことができます。 A君〜F君はとある授業で2人組を組むことになった。 A君〜F君の友達関係は下のようになっている。 A君とB君は仲良し A君とE君は仲良し...

こんにちは、ももやまです。 今回はグラフの点、辺に関する連結度についてまとめていきたいと思います。     前回の離散数学（第15羽）の記事はこちら！ www.momoyama-usagi.com 最大フロー、最小カットを求める方法についてまとめています！   ０．復習（グラフの連結とは） どの2点の間にも道が存在する...

こんにちは、ももやまです。 今回は最大フロー・最小カットの求め方をメインにまとめていきたいと思います。 前回の記事（第14羽）はこちら！ ダイクストラ法を用いた最短経路の出し方ついてです！ www.momoyama-usagi.com １．フロー・最大フローとは まず最初に最大フローの「フロー」とはなにかを簡単にですが...

※修正（2020/01/12）＼( v_6 ＼) の距離が10ではなく13になっていたのを修正しています。   こんにちは、ももやまです。 乗り換え案内アプリやカーナビってすぐに最短経路を計算してくれてすごい便利ですよね。路線が複雑な東京都内であってもあっという間に最短経路を計算してくれますよね。   ↓こんな感じに一...

こんにちは、ももやまです。 今回は最小全域木の求め方についてまとめていきたいと思います！     １．全域木とは 全域木とは、もとのグラフのすべての点を含み、さらに選んだ辺が木となっているようなグラフを表します。 （全域部分グラフが木となっているものを全域木と呼びます）   例えば、つぎのグラフの全域木を1つ考えてみま...

こんにちは、ももやまです。 今回はグラフをコンピュータ上で探索する方法のうち、よく使われる幅優先探索と深さ優先探索について説明していきたいと思います。     前回の記事 www.momoyama-usagi.com   １．探索とは 例えば、図の ＼( s ＼) から ＼( v_7 ＼) までの辺のたどる方法を考えて...