離散数学

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

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

こんにちは、ももやまです。 今回はちょっと特殊なグラフである木についてまとめています。 前回の記事（第10羽）はこちら！ オイラーグラフ・ハミルトングラフについてです。 www.momoyama-usagi.com １．木・森 (1) 木とは 閉路を持たないような連結なグラフのことを木と呼びます。 下の図を例にすると、...

こんにちは、ももやまです。   突然ですが問題です！ つぎの①〜⑤の中から一筆書きできるものを2つ選んでみましょう。 引用元：パズル算数クイズ  （解答は２の例題2の解説に書いています。）   今回は一筆書きができるかどうかの判定方法をメインにまとめていきたいと思います。  （一筆書きの判定法は2章にまとめています。）...

こんにちは、ももやまです。 今回もグラフ理論における基本用語をまとめていきたいと思います。     前回の離散数学（グラフ理論）第8羽はこちら！  www.momoyama-usagi.com グラフの基礎1はこちらから！ www.momoyama-usagi.com   １．グラフの連結性・連結グラフ まずは連結グラ...

こんにちは、ももやまです。 今回も離散数学（グラフ理論）の基礎について説明したいと思います。 今回はグラフをたどり方に関する歩道、小道、道、回路、閉路についてです。 前回の離散数学（グラフ理論）の記事はこちら！ www.momoyama-usagi.com 「グラフってなんだっけ？」と思ったひとはこちらの記事で復習しま...

こんにちは、ももやまです。 久しぶりに離散数学の内容を書いてみようかと思います。 今回からしばらくは離散数学の中でもグラフ理論のお話になります。 グラフ理論の参考書もかなり難しい言葉で書いているものが多かったのでこの記事ではうさぎでもわかるようにかみ砕いた言葉でなるべく説明しています。 １．グラフ理論のグラフってなに？...

こんにちは、ももやまです！ 今回は、多くの人が苦手としている2変数以上の述語論理の読み方の練習問題をもってきました！ １．基本的な述語論理読み方のルール ＼( ＼forall x ＼ P(x) ＼) は、範囲内すべての ＼( x ＼) で成立すれば ＼( P(x) ＼) が真 ＼( ＼exists x ＼ P(x) ＼...

こんにちは、ももやまです。今日は離散数学で大切な数え上げについてまとめました。 今回は離散数学で習った様々な知識を使って様々な条件を満たすものの個数を求めていく練習問題方式となっています。   １．部分集合、直積集合 わからない場合は、こちらのページで復習をしましょう。 問題1 ＼( n ＼geqq 2 ＼) の自然数...

こんにちは！　ももやまです！ 前回に引き続き、差分方程式（漸化式）についてです。 前回説明した隣接３項間や隣接４項間の差分方程式は = 0 の形になっていました。 今回は = 0 のパターンではない右辺に残骸があるパターンについて説明していきたいとおもいます。 なお、「= 0」のパターンはもっと簡単に解くことができます...