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

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

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

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

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

こんにちは、ももやまです。 そろそろ研究室を考えるようなシーズンになってきましたね。   そこで今回は研究室について色んな友達・先輩のアドバイスも踏まえながら「最高の研究室生活を送るための研究室選び」についてまとめてみました。     主に、 相性がいい研究室の見分け方（質問） 第1希望の研究室に入るコツ の2つについ...

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

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

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

こんにちは、ももやまです。 今回は正規表現についてまとめてみました。 ただ正規表現についてまとめただけでなく、正規表現を有限オートマトンの状態遷移図で表す方法についてもまとめているのでそちらもご覧ください！ （正規表現について知りたい人は2章を、正規表現をオートマトンに直す方法が知りたい人は3章をご覧ください） 前回の...