グラフ理論を学びたいと思います。学部上級から院レベルで何か良い書籍は無いでしょうか?  あまり数学的formalismを追求し過ぎない物がよいのですが。
もちろん、洋書(英語)でもぜんぜんかまいません。物理とかの本になってしまってもかまいません。グラフ理論が出て来て学べるのであれば、そういうわけでよろしくお願いします

このQ&Aに関連する最新のQ&A

A 回答 (1件)

1.本格的な教科書(読んでいて辛い)。



グラフ理論
R. ディーステル (著) (2000/10/01)
シュプリンガー・フェアラーク東京

グラフ理論入門 数理科学ライブラリ (2)
N.ハーツフィールド, (1992/06/01) サイエンス社


2.わりと柔らかめの教科書(面白い)。

組合せ論・グラフ理論(現代応用数学の基礎)
野崎 昭弘 (著) (1994/04/01) 日本評論社

3.一般向けのわかりやすい読み物(軽すぎる)。

グラフ理論3段階 アウト・オブ・コース〈2〉
根上 生也 (著) (1990/07/01) 遊星社
    • good
    • 0
この回答へのお礼

ありがとうございます

お礼日時:2002/03/28 02:51

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Qグラフ理論について発表する

 グラフ理論をほとんど知らない人たちの前で、グラフ理論について発表することになりました。グラフ理論の紹介をしようと思うのですが、私自身もグラフ理論については少し学んだだけで、その歴史や特徴は詳しく知らないので、質問させていただきます。
 1.現在、グラフ理論は生活のどのようなところに応用されていますか。また、これからどのように応用されると思いますか。
 2.グラフ理論を紹介する上で外せないと思うポイントがありましたら教えてください。

Aベストアンサー

こんにちは。一応私なりの回答を書きたいと思います。グラフはさまざまな場所での応用が聞きます。実際確実につかわれているかと言われればあまり使われてはいませんが・・・・・
(1) Treeはグラフ理論の中でも重要なトピックの一つだと思いますが、例えば、ゲームソフトのチェスや将棋なんかで相手がどう動いたらコンピューターはこう動くというプログラムがかけますし。これは将棋のプロの人が頭の中で考えることをグラフにしたものに応用できます。
(2)matchingの場合は、例えばパーティや、結婚式で席を決める時、中の悪い人同士を同じテーブルにならないようにするためにはどういう席の決め方をするべきかかんがえる時に役に立ちます。
そのほか、グラフ理論ではスチュワーデスの勤務状況を満遍なく割り当てる方法にも応用されます。
必要ないでしょうが、ハンガリーの数学者は特にグラフ理論に強い人が多いという、私的な感想も持っています。

Q続・グラフ理論

Gを頂点数n、変数mの単純グラフとし、PG(k)をGの彩色多項式をし、PG(k)のk^n-1の係数が-mであることを示せ。という問題で

・任意の辺 e に対し P(G, k) = P(G-e, k) - P(G/e, k)
・n頂点のグラフ G に対し, P(G, k) は k に関する整数係数 n次多項式かつ k^n の係数は 1
・P(empty graph, k) = k^n
まで出来たんですがk^n-1の係数が-mであることをどうやって示せばいいのでしょうか?
再度すみません

Aベストアンサー

辺の本数に関する帰納法が一番単純だと思う.

Qグラフ理論の本

グラフ理論を学びたいと思います。学部上級から院レベルで何か良い書籍は無いでしょうか?  あまり数学的formalismを追求し過ぎない物がよいのですが。
もちろん、洋書(英語)でもぜんぜんかまいません。物理とかの本になってしまってもかまいません。グラフ理論が出て来て学べるのであれば、そういうわけでよろしくお願いします

Aベストアンサー

1.本格的な教科書(読んでいて辛い)。

グラフ理論
R. ディーステル (著) (2000/10/01)
シュプリンガー・フェアラーク東京

グラフ理論入門 数理科学ライブラリ (2)
N.ハーツフィールド, (1992/06/01) サイエンス社


2.わりと柔らかめの教科書(面白い)。

組合せ論・グラフ理論(現代応用数学の基礎)
野崎 昭弘 (著) (1994/04/01) 日本評論社

3.一般向けのわかりやすい読み物(軽すぎる)。

グラフ理論3段階 アウト・オブ・コース〈2〉
根上 生也 (著) (1990/07/01) 遊星社

Qグラフ理論

Gを頂点数n、変数mの単純グラフとし、PG(k)をGの彩色多項式をし、PG(k)のk^n-1の係数が-mであることを示せ。
という証明問題なんですが、なんで-mになるのかがわかりません。
すみませんが教えてください。

Aベストアンサー

無駄があるかもしれませんが:
まず, G を n頂点の空グラフ (辺を持たないグラフ) とすると, P(G, k) = k^n です. 定義から計算してください.
で, 次に n頂点のグラフG に対し P(G, k) が k に関する n次多項式で k^n の係数が 1になることを (頂点数と辺の数に関する) 帰納法で示します.
辺 e に対し P(G, k) = P(G-e, k) - P(G/e, k) ですが, 右辺に出てくる G-e, G/e はどちらも G より小さいグラフです. G-e は G と頂点数は同じで, 辺は 1本減っています. また, G/e は G より頂点が 1個少なく, また辺も少なくとも 1本は減っています. だから右辺には帰納法が適用できて P(G-e, k) = k^n + o(k^n), P(G/e, k) = k^(n-1) + o(k^(n-1)) です. つまり P(G, k) も k^n + o(k^n) です.
これだけ用意すれば, あとは辺の本数に関する帰納法がまわります.

Q数論とグラフ理論との関係ってあるの?

以前、
数論と無関係な数学の分野、数学と無関係な科学の分野はありますか?
http://oshiete1.goo.ne.jp/qa5085683.html
という質問をさせていただきました。

数論における問題を解くには、代数的手法のほかに、幾何的、解析的、組合せ的な手法があるのはわかります。
また、詳しくは知りませんが、確率的な手法があるというのも聞いたことがあります。

このようなさまざまなアプローチがあることはとても興味深いことで、数論は数学の中の数学だという信念を持っています。

ところで、数学の中でも名の知れたものにグラフ理論があります。
しかし、グラフ理論が数論に応用されたとかいう話は、まったく聞きません。
数論とグラフ理論とに何か関係があるようでしたら、どうか教えていただけないでしょうか。

Aベストアンサー

数論に明るくないのでなんとも言えないですが、グラフ理論の中にマッチングという概念があります。
そのマッチング枝に重みをつけて最適化(最小化でも最大化でも)を考えるときは、
それを線形計画問題として扱い、最後にInteger Rounding(整数丸めとか訳すのかな?)という操作を行い、
整数制約を守るようにするなんてことをしたりします。

整数計画問題(もちろん線形計画問題も)とグラフの最適化は結構密接に関係しているので、
これはグラフ理論と数論に関係あるのかなと思えなくもないです。

Qグラフ理論

添付ファイルの問題でいう,最小カットと最大フローとは何を示すのですか?

Aベストアンサー

フローは普通「物資の流れ」で説明するかな.
A点から B点まで物資を輸送することを考えます. このとき,
・A点と B点以外では物資の増減はない
・どの辺も指定された容量を越えて物資を送ることはできない
という制約を与えます. この制約を満たす「物資の送り方」はいろいろあるわけですが, これらを「フロー」と呼びます. 数学的には各辺に対して輸送量を定める関数として定義するのが普通.
で, カットのうち「カットに含まれる辺の容量の和が最小のもの」を「最小カット」と呼び, フローのうち「輸送する物資の量が最大となるもの」を「最大フロー」と呼びます.

Q洋書(グラフ理論)の読破

現在, 大学2回生です

興味のある分野を読み進めていくうちに洋書を読んだほうがより高い知識を得られると考え, 洋書の購入を考えています。

興味のある分野は「グラフ理論(大きくみれば離散数学)」なんですが

洋書ってどうも苦手意識があるというか・・・

要領よく読み進めていくにはなにかコツのようなものはあるのでしょうか?

あと、出来ればグラフ理論の良書も教えてください

Aベストアンサー

良い参考書については、教授に聞くのが良い。
そのために大学に在籍していると言っても過言ではない。
さらに大学には図書館もあるので購入する必要も多分ない。

誰がグラフ理論について詳しいかわからないという場合には、
誰でもいいから掴まえて、知っていそうな人を紹介してもらって下さい。

>洋書ってどうも苦手意識があるというか・・・
今まで何冊くらい洋書を読みましたか?何十冊と読んでそれでも苦手ですか?

専門書の英文は文学作品などと比較すると、格段に読み易いと思います。
語彙も少ないし、数学の場合は話が飛躍することもないし。

慣れれば普通の日本語の書籍と同じように読めるようになります。
(ドイツ語やフランス語だったらゴメン)

Qグラフ理論の問題

この問題がどうしても解けません。
(a) どんな単純グラフにも次数が同じ点が2個以上あることを示せ。
どうかお願いいたします。

Aベストアンサー

帰納法を使います。

頂点数が2の時(a)は成り立つ。
頂点数が2以上k以下の時(a)が成り立つと仮定すると、
頂点数がk+1の時、

1)グラフに辺が一本も無いとき、明らか。

2)グラフが非連結で辺が一本以上あるとき、
このグラフは頂点数2以上k以下の連結成分を持つ。
この連結成分は帰納法の仮定より同じ次数の頂点を持つ。
よってこのグラフも同じ次数の頂点を持つ。

3)グラフが連結であるとき、
各頂点の次数は1以上k以下のk種類である。頂点はk+1個あるので
鳩の巣原理より、同じ次数の頂点が存在する。

以上より(a)は成り立つ。


もうちょっとうまいやり方がありそうなものですが、
ちと思い付きませんでした。

Q幾何学?トポロジー?それともグラフ理論?

折り紙の中にハエを閉じこめるには、3回折ればいいですよね。

こういう数学はどういう分野なのでしょうか?
幾何学?トポロジー?それともグラフ理論?

Aベストアンサー

下の回答で「三つの平面を組み合わせて閉曲面を作ることができる…単体σ4 の表面なので4つの平面が必要」というところは「4つの平面を組み合わせて閉曲面を作ることができる…単体σ4 の表面なので五つの(超)平面が必要」に訂正させて下さい

Qグラフ理論における最長パス

「連結グラフにおいて最長パスは必ず共通点を持つことを証明せよ」という問題を学校でだされたのですがどうしてもわかりません解き方をわかる方もしくはわかるサイトをお知りの方教えてください

Aベストアンサー

下記に証明があります。
(2章の9.を見てください)

http://coolee.at.infoseek.co.jp/graph_ensyuu_sol.html


人気Q&Aランキング

おすすめ情報