2004年度 グラフ理論講義ノート : HUSCAP2004年度に工学部情報工学科3年生を対象にして開講された講義「グラフ理論」の講義ノートです。前提とする数学的な知識を必要とぜずに理解できるように作成しました。多くの例題、練習問題を含み、それらの解答を出来る限り平易に説明してあります。なお、当講義は新カリキュラムに移行する2007年度以降は開講されませんが、アルゴリズムの計算量評価や最適化問題と絡んだ場合の数の数え上げ等の問題にグラフ理論を用いたい場合、グラフ理論の基本的な部分を手早く学びたい際には有用なのではないかと期待しています。
グラフ理論
グラフ理論における「グラフ」というのはいくつかの点をいくつかの線でつないだモノである。 普通はどの点とどの点が結ばれてるかのみに着目しどのように結ばれているかは問わないことが多いが、幾何学的グラフ理論では点集合としての（位相的）図形として結ばれ方も重視する。 この２つの見方 ― 「システム」としての見方と「図形」としての見方 ― が可能なことからグラフは一見単純ではあるが奥深い数学的な対象となっている。 グラフ理論は身近に存在する。 たとえば我々はいたるところで「植木算」のお世話になっているが、植木算の中にグラフ理論の主要な考えの発端が見られる。 この講義ではグラフ理論の応用数学的な側面よりも純粋数学的な側面に焦点を絞った。 形式的な記述でわかりにくい部分も図を見ればわかってしまうことが多いように図をたくさん入れておいた。 予備知識はほとんど不要であるが、ベクトル空間やポセッ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
