2004年度に工学部情報工学科3年生を対象にして開講された講義「グラフ理論」の講義ノートです。前提とする数学的な知識を必要とぜずに理解できるように作成しました。多くの例題、練習問題を含み、それらの解答を出来る限り平易に説明してあります。なお、当講義は新カリキュラムに移行する2007年度以降は開講されませんが、アルゴリズムの計算量評価や最適化問題と絡んだ場合の数の数え上げ等の問題にグラフ理論を用いたい場合、グラフ理論の基本的な部分を手早く学びたい際には有用なのではないかと期待しています。
グラフ理論(グラフりろん、英: Graph theory)は、ノード(節点・頂点、点)の集合とエッジ(枝・辺、線)の集合で構成されるグラフに関する数学の理論である。 グラフ(データ構造)などの応用がある。 グラフによって、様々なものの関連を表すことができる。 6つの節点と7つの辺から成るグラフの一例 例えば、鉄道や路線バス等の路線図を考える際には、駅(節点)がどのように路線(辺)で結ばれているかが問題となる一方、線路が具体的にどのような曲線を描いているかは本質的な問題とならないことが多い。 したがって、路線図では駅間の距離や微妙な配置、路線の形状などがしばしば地理上の実際とは異なって描かれている。つまり、路線図の利用者にとっては、駅と駅の「つながり方」が主に重要な情報なのである。 このように、「つながり方」に着目して抽象化された「点とそれらをむすぶ線」の概念がグラフであり[1]、グラフがも
■補数って? 10、100,1000……から、ある数を引いた残りの数のことを(基数の)補数というが、今回の主役は、 それよりも1少ない、いわゆる減基数の補数(注)である。 10進数だと、ぶっちゃけ足して(各桁が)9になる数(の組)だ。 具体例を出すと「9-1=8」だから、8は1の補数である。いうまでもないが、1は8の補数である。 ■まずは「おつり算」 日常生活で最も多い計算は「おつりを計算すること」だろう。 これは補数を使った計算の第一歩にちょうどいい。 速算に 10000-3452=? を計算することは、3452の基数の補数をもとめることだけれど、 まず減基数の補数を求めちゃえばいい。そしてこれは次の方法で反射的にできる。 減基数の補数は基数の補数よりも1だけ少ないということを心に留めておくと、 次の表を覚えておく(というより反射的に出るようにしておく)だけで、 「繰り下がり」なんかに希
Author:くるぶし(読書猿) twitter:@kurubushi_rm カテゴリ別記事一覧 新しい本が出ました。 読書猿『独学大全』ダイヤモンド社 2020/9/29書籍版刊行、電子書籍10/21配信。 ISBN-13 : 978-4478108536 2021/06/02 11刷決定 累計200,000部(紙+電子) 2022/10/26 14刷決定 累計260,000部(紙+電子) 紀伊國屋じんぶん大賞2021 第3位 アンダー29.5人文書大賞2021 新刊部門 第1位 第2の著作です。 2017/11/20刊行、4刷まで来ました。 読書猿 (著) 『問題解決大全』 ISBN:978-4894517806 2017/12/18 電書出ました。 Kindle版・楽天Kobo版・iBooks版 韓国語版 『문제해결 대전』、繁体字版『線性VS環狀思考』も出ています。 こちらは10刷
■編集元:ニュース速報板より「あらゆる数学分野の中で一番意味不明なのは「確率」」 1 落とし蓋(アラバマ州) :2010/03/04(木) 15:38:09.90 ID:oTT5I7/Y ?PLT(12000) ポイント特典 確率の話をしたついでに、ちょっとひとこと。 スポーツ新聞の見出しなどで、「ディープインパクト、90%の確率で勝てる!」といった表現を見掛けますが、この使い方はちょっと微妙です。 18頭が出走するレースなら、そのうちの1頭が勝つ確率は、あくまで18分の1にすぎません。「降水確率」というのも、変な表現です。 雨は「降る」か「降らない」かのどちらかですから、その確率は0%か100%でなければなりません。 このような場面は「確率」ではなく「期待度」のことを言っているんだから…… と、文句を言いたくなりますが、 広辞苑の第3版(83年)には確率という言葉に「期待度
ヒッチン方程式とその周辺 教授・望月 拓郎 ヒッチン方程式はリーマン面上で定義される非線形な微分方程式です。もともとは物理学で重要なヤン - ミルズ方程式を簡単にしたものとして導入されたのですが、むしろ数学的に興味深い方程式であり、微分幾 何・代数幾何・トポロジーなど様々な分野を結びつける役割を果たし、その影響は代数解析や数論といった かなり離れた分野にまで及んでいます。この講座では、ヒッチン方程式に関連する数学的対象について説明 し、ヒッチン方程式に触発されて発展した研究の一端を紹介する予定です。また、ヒッチン方程式を例とし て、非線形微分方程式の解析の難しさと面白さなどについても触れたいと考えています。 二重指数関数型数値積分公式の理論と発展 助教・大浦 拓哉 二重指数関数型数値積分公式(DE 公式)は高橋秀俊・森正武により1974年に提案された定積分の値を数 値的に求める手法です。現
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く