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

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

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

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

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

No.1 ベストアンサー 回答者： yskfr 回答日時： 2009/12/30 18:27

数論に明るくないのでなんとも言えないですが、グラフ理論の中にマッチングという概念があります。

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

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

この回答へのお礼

マッチングはよく知りませんが、ありがとうございます。

お礼日時：2010/05/22 23:59