« なぜ「動的計画法」というか？ | メイン | 期末試験 »
2010年07月19日
グラフ理論というといかめしいが
マル○で頂点、頂点どおしを線で結ぶと、グラフは直観点な図で表現できる。 情報の場合は、まずはデータ構造の表現だと思えばいい。 最短路を求める問題の場合は、線に辺（枝）の数値が記入されるから、数値の和が一番小さい経路（パス）が最短路になる。 ホントの長さで図を表現すると地図のようにぐじゃぐじゃになるので、数値が違ってもどれも等距離の辺の図で表現している。 これは難しく云うと「位相同型」という理論を使っているが、直観的に見やすくしてるから、と思ってもらえばいい。
プログラム演習の場合は、この数値はどの辺も１として扱った。 理由は数値を扱うと、どうしてもポインタが必要になり、100人の演習をTAなしでやるのはムリだし、こうなると離散数学でなく、プログラムの授業になってしまう。 そういう理由で辺の数値は１としていたが、期末演習は紙の上での演習なので、DPで解く場合は数値を入れている。 徳山さんのテキストもせっかくダイクストラ法に触れながら、図のグラフでは数値が入っていない。 （これではアルゴリズムの説明には向いていない。）
データ構造だけでなく、プログラム構造もグラフで表現できるが、離散数学ではとりあえず「データ構造」の表現にグラフが利用されている、という理解で十分。 ハフマン木も、頻度の違う記号相互の関係をグラフ表現したものと思えばいい。
投稿者 tadashi : 2010年07月19日 06:14