- ベストアンサー
グラフの最長経路問題
グラフにおいて，最長経路を求める問題があります． 最*短*経路問題なら，「一番早くたどり着ける道順を探す」ということで理解できるのですが，最長の経路を求めて何かメリットがあるのでしょうか? 応用が分かりません． そこに何か利点があるのでしょうか? 理論的な興味だけなのでしょうか?
- magicoflove
- お礼率1% (11/757)
- 数学・算数
- 回答数3
- ありがとう数1
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
その他の回答 (2)
- graphaffine
- ベストアンサー率23% (55/232)
- BLUEPIXY
- ベストアンサー率50% (3003/5914)
関連するQ&A
- 最長経路探索
グラフの最長経路(クリティカルパス)を求めたいのですが、 ・閉路無し有向グラフ ・重み付きグラフ（辺ではなくノードの方に重みがある） ・スタートとゴールのノードが各々1つ与えられている ・スタートからどの経路を辿ってもゴールには辿り着く 以上のような条件の時に、どのようなアルゴリズムを用いれば良いのでしょうか？ 幅優先探索で求められそうな気がしたのですが、どうも上手くいきません。 言語はVBAで、そもそも詳しくないのですが、 考え方など教えて頂けないでしょうか。 お願い致します。
- ベストアンサー
- その他（プログラミング・開発）
- グラフ理論について発表する
グラフ理論をほとんど知らない人たちの前で、グラフ理論について発表することになりました。グラフ理論の紹介をしようと思うのですが、私自身もグラフ理論については少し学んだだけで、その歴史や特徴は詳しく知らないので、質問させていただきます。 １．現在、グラフ理論は生活のどのようなところに応用されていますか。また、これからどのように応用されると思いますか。 ２．グラフ理論を紹介する上で外せないと思うポイントがありましたら教えてください。
- ベストアンサー
- 数学・算数
- グラフ理論における最長パス
「連結グラフにおいて最長パスは必ず共通点を持つことを証明せよ」という問題を学校でだされたのですがどうしてもわかりません解き方をわかる方もしくはわかるサイトをお知りの方教えてください
- ベストアンサー
- 数学・算数
- 隠れ端末問題とグラフ理論の関係についての質問
現在、大学の理工学部の情報工学科に所属し、アドホックネットワークを研究している研究室に配属された者です。この研究室ではアドホックネットワークについて、「グラフ理論の応用」を基本的な方針としています。 私は卒研のテーマとして、アドホックネットワークにおける重要な問題である「隠れ端末問題」を研究することになりましたが、正直、どう研究を進めていって良いか全く分かりません。 「グラフ理論を用いて、隠れ端末問題を研究する」という、漠然とした方針は決まっているのですが、そもそも、隠れ端末問題とグラフ理論がどう関わっているのか、そして、何が問題となっていて、何を目的として研究をすれば良いのかが分かりません。 論文を検索するWebサイトで、「隠れ端末問題」や「グラフ理論」をキーワードにして色々と検索してみたのですが、隠れ端末問題の解決においてグラフ理論を利用している論文は全く見つかりませんし、論文を見ても、隠れ端末問題において現在何が問題となっていて、そして何を目標として研究するべきなのかが把握できません。 研究室の教授は放任主義で、こちらが質問をしてもはっきりとした答えが返ってきません。 もしこの分野にお詳しい方がいらっしゃいましたら、 ・隠れ端末問題とグラフ理論がどう関係しているのか ・隠れ端末問題において、現在何が問題なのか ・問題を解決するための研究の目的と流れ 以上の質問に答えて頂けると有り難いです。
- 締切済み
- 数学・算数
- 数論とグラフ理論との関係ってあるの？
以前、 数論と無関係な数学の分野、数学と無関係な科学の分野はありますか？ http://oshiete1.goo.ne.jp/qa5085683.html という質問をさせていただきました。 数論における問題を解くには、代数的手法のほかに、幾何的、解析的、組合せ的な手法があるのはわかります。 また、詳しくは知りませんが、確率的な手法があるというのも聞いたことがあります。 このようなさまざまなアプローチがあることはとても興味深いことで、数論は数学の中の数学だという信念を持っています。 ところで、数学の中でも名の知れたものにグラフ理論があります。 しかし、グラフ理論が数論に応用されたとかいう話は、まったく聞きません。 数論とグラフ理論とに何か関係があるようでしたら、どうか教えていただけないでしょうか。
- ベストアンサー
- 数学・算数
- オイラーグラフの十分条件について
グラフ理論についての質問です。よろしくお願いします。 「グラフGのすべての辺eについてeを含むサイクルが奇数個ならば、Gはオイラーグラフ」 を証明したいです。 「辺を含むサイクルの個数」という条件をどう活かすかが思いつかず、背理法で示そうとしましたが、そちらもうまくいきません。 （最長のトレイルPを定めて、「Pに含まれない辺を含むサイクル」を用いてPの最長性に矛盾させる方針で考えていました） また、そもそもGは連結という条件が必要だと思うのですが（非連結でもよいとすると各連結成分がサイクルであるグラフが反例になってしまうので）、問題文中にそのような記載は特にありませんでした。 非連結だとオイラーグラフにはなり得ないので、自明な前提として省略している可能性もあるとは思いますが、「Gは連結である」ということは暗に認めてしまっても良いものなのでしょうか？ 以上になります。ご教示いただければ幸いです。
- ベストアンサー
- 数学・算数
- 製品・サービス名: ぷらら（インターネット接続サービス）
- お困りの内容: サーバー未接続のメッセージが出てホームページの更新ができなくなった。
- お使いの環境: パソコンのOSはWindows10、接続は無線LANです。
