Hatena::ブログ(Diary)

やねうらお−ノーゲーム・ノーライフ このページをアンテナに追加 RSSフィード

tokutoku777 tokutoku777 ランキング
電王戦出場記念! 書籍化されたで! 監修したで!(`ω´) 絶版なってしもた Kindle版で復活!! 記事書いたで!
解析魔法少女美咲ちゃん マジカル・オープン!

YaneuLabs / やねうら王公式 / やねうらおにメール / twitter / プロフィール

 | 

2005-12-19 グラフ理論ならこれを読め!

[] グラフ理論ならこれを読め!  グラフ理論ならこれを読め!を含むブックマーク  グラフ理論ならこれを読め!のブックマークコメント

グラフ理論入門―平面グラフへの応用 (日評数学選書)うちの会社では「グラフ理論小学校のうちに学んでおかないから、そういうことになるんジャイ!(`ω´)」とか冗談とも本気とも取れないような会話が平気で行き交う。それほどグラフ理論は大切な分野なのにプログラマには見過ごされがちだ。ただ、グラフ理論にはいい本が少ない。そこで、グラフ理論ならこれを読め!という本を紹介する。まずは、入門書としては、左の本がお勧め

最適化とグラフ理論 (技術者のための高等数学)大学教科書としてよく採用されているのが左の「最適化グラフ理論 技術者のための高等数学」値段も手ごろだし、高校卒業程度の知識でも読めると思う。

グラフ理論 (Springer‐Verlag GTMシリーズ)グラフ同型性判定問題 (日本大学文理学部叢書)「そんな入門書ではなくて、もっと詳しい本は無いか?」とid:Ozyさんに聞かれて私が勧めたのは、シュプリンガー・フェアラーク東京シリーズの「グラフ理論」 このシリーズは黄色い表紙とお馬さんのマークが目印だ。
これより詳しい本となると日本語で読めるものは発売されていないと思う。「グラフ同型判定問題」(asin:4572999988)とセットで持っていればこれ最強。あとは、計算幾何学の学問領域と重複してたりするので、そちらも勉強するといいだろう。

計算幾何学入門―幾何アルゴリズムとその応用コンピュータ・ジオメトリ―計算幾何学:アルゴリズムと応用計算幾何学入門」は安価だし、計算幾何学の入門書として手ごろだと思う。もう少し専門的な内容については「コンピュータ・ジオメトリ」がいいだろう。

組合せ最適化-理論とアルゴリズムあるときには、「組み合わせ最適化」にもグラフ理論が顔を出す。「組み合わせ最適化」の学問領域は、線形計画法,整数計画法,全点木と有向木,最短パス,ネットワークフロー,最小費用フロー,最大マッチング,重み付きマッチング,b-マッチングとTジョイン,マトロイド,ナップサック問題,ビンパッキング問題,多品種フローと辺素パス,ネットワーク設計問題,巡回セールスマン問題,施設配置問題etc..。これらはグラフ理論の応用例として勉強すると効果的だと思う。「組み合わせ最適化」について最も詳しく載っている本は、同じくシュプリンガー・フェアラーク東京シリーズの左の本だと思う。

組合せ最適化アルゴリズムの最新手法―基礎から工学応用まであとは丸善の「組み合わせ最適化アルゴリズムの最新手法」も上の「組み合わせ最適化」と合わせて読みたい。

組合せ最適化の理論 (情報とシステムシリーズ)また、「組み合わせ最適化」の入門書としては、電子情報通信学会の「組み合わせ最適化理論」(asin:4885520304)が値段的にもお手ごろだろう。
近似アルゴリズム「近似アルゴリズム」は、高速に高品質の近似解を求める手法について解説されている。組み合わせアルゴリズム、LP(線形計画法)に基づくアルゴリズムが多数掲載されており、グラフ理論の実際的な応用としても価値が高い。R.M.Karp氏(1985年チューリング賞受賞)とL.Lovasz氏(1999年クヌース賞受賞)の両氏も絶賛。

yaneuraoyaneurao 2005/12/19 18:03 他にもいい本があれば教えてチョ。

mihael2mihael2 2005/12/19 18:09 IE6だとフォーマットが崩れて本文が半分以上読めねっす。

あっはーあっはー 2005/12/19 19:07 既出かもしれないけど、普通のプログラミングなら次の本のグラフアルゴリズムの章で十分でしょうけど、多分違いそうですね。
アルゴリズムC++(http://www.amazon.co.jp/exec/obidos/ASIN/4764902222/)
アルゴリズムとデータ構造(http://www.amazon.co.jp/exec/obidos/ASIN/4000103431/)
そう言えば少し前にネットワークの本がブームになってたけど、最近見かけない気がする。

yaneuraoyaneurao 2005/12/19 21:53 ↑*2 うちはIE6だけど読めてるんだけど..
でもbrタグでclear=”all”を書くと、ときどきおかしくなるのは何とかならんのかの..(´ω`)
↑*1 「アルゴリズムC++」はグラフ理論に関しては入門と中級の間ぐらいだと思う。

sisidotsisidot 2005/12/19 23:00 うちのIE6だと、一番上の段落の上の方でマウスを動かしていると、段落全体が消えますね。アルゴリズムC++は、大分前に買ったけど、グラフや幾何関連の部分はほとんど読む機会もなく本棚の奥に眠っていたりしてw

yaneuraoyaneurao 2005/12/19 23:09 もう、br clear=”all”使うのやめるよ!

「悲しいけど、これって現実なのよね。」

fkmfkm 2005/12/20 00:21 ウチの大学では近代科学社のグラフ理論入門(http://www.amazon.co.jp/exec/obidos/ASIN/4764902966/)使ってました。
…ってこれ入門ですねorz

アルゴリズムイントロダクションの2巻にもグラフ理論が少しあったような

ambeeambee 2005/12/20 02:00 わー、タイムリー。先週グラフ理論の本を買って復習し始めたばっか。やねさんお勧め本も読んでみよーっ。

OzyOzy 2005/12/20 17:23 (プログラマ向け)入門書としては、Alan Gibbonsの”Algorithmic Graph Theory”が個人的に大好きなんですけど、英語版しかないのが残念(´ω`)

AyanamiAyanami 2005/12/20 17:36 theSpokeユーザ向けのVS.NET2005Proの無償ダウンロードが開始されてようです。(`・ω・´)

wanpacwanpac 2005/12/20 18:29 始めまして。大学院で組合せ最適化みたいなことをしてます。近似ですが。ってことでhttp://www.amazon.co.jp/exec/obidos/ASIN/4431709916/qid=1135070920/sr=1-3/ref=sr_1_10_3/250-2498670-9673827
こんなのはどうでしょう?やはりグラフ理論はバンバン出てきますよ。グラフ理論が実際に役立つことがわかって嬉しいです。

yaneuraoyaneurao 2005/12/20 18:37 ああ、その本は、非常にいい本ですね。いずれ紹介しようと思ってたんですけど、今回追加しときます。

 | 

人気blogランキング tokutoku777
1900 | 01 |
2004 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2012 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2013 | 01 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2014 | 01 | 02 | 03 | 04 | 06 | 08 | 10 | 11 | 12 |
2015 | 01 | 02 |


Microsoft MVP
Microsoft MVP Visual C# 2006.07-2011.06