- ベストアンサー
最小全域木について
現在、最小全域木の問題はグラフ理論や遺伝的アルゴリズムの文献など様々な分野で解説されていますが、この「最小全域木」について気になることがあります。 最小全域木とは辺に対して一つの重みがあるものですが、この重みが多重化すること、つまり一つの辺に対して二つ以上の重みが存在する最小全域木とは存在しないのでしょうか？？ つまりは「二重の重みを持つグラフ」を対象とした研究とは世の中では行われていないのでしょうか？？ 厳密な解を求めるのが不可能など、様々な問題が生じてくるから不可能なのかなと思ったりしたのですが、、、違うのでしょうか？？ もし、この分野に詳しい方がいらっしゃったら返事をお願いしたいです。
- JETER
- お礼率51% (210/408)
- その他（プログラミング・開発）
- 回答数2
- ありがとう数0
- みんなの回答 （2）
- 専門家の回答
関連するQ&A
- 遺伝的アルゴリズムの遺伝子の長さについて
今、グラフ理論と遺伝的アルゴリズム（以下ＧＡ）の勉強をしています。 グラフ理論の最小全域木問題をＧＡを使って解こうと考えています。そこで、個体の遺伝子の長さをそのグラフの点の数Ｎにすればよいのではないかと考えました。 しかし、グラフが大きく、点の数Ｎが１００や１０００になった場合は、遺伝子の長さも非常に長くなってしまいます。これはＧＡとして問題があるかないかについて教えてください。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- ２点同士の距離の平均が最小となる木
グラフ理論に関してです。 ネットや手持ちのグラフ理論入門書で探しても見つけられなかったので質問させて下さい。 重みつき連結グラフにおいて, 入力が「グラフ上の複数(>=2)の節点」であり、出力が「節点同士の距離平均が最小であるような木」となるようなアルゴリズムはあるでしょうか。 もしくはそれに対する近似的なアルゴリズムでもかまいません。 言い直すと、入力された節点集合を U として ( Σ<iとjの距離> ) / |U| i,j∈U, i≠j が最小となるような木です。
- ベストアンサー
- 数学・算数
- Ｋ_nの全域木の数の証明
Ｋ_nはn点からなるグラフ（図形）で、ある任意の点は自分自身以外の点と辺で結ばれています。つまり各辺の次数がn-1のグラフです。 このグラフの全域木の数は一般的にn^(n-2)個であることが知られているそうなのですが、どう証明すればいいでしょうか。 全域木とは、全ての点を通る「木」のことです。つまり全ての点と点を結びつけつつも閉路が存在しないようなグラフのことをいいます。 どなたか分かる方、よろしくお願いします。
- ベストアンサー
- 数学・算数
- 最小全域木問題のC言語プログラム
次元制限のある最小全域木問題とはどういうことで、それについてC言語を使用してプログラミングを組みたいのですが・・・・。何から手をつければいいのかさっぱりわかりません。ヒープソートのプログラムを使用するなど考えてみたのですがしっくりきません。少しでも参考例を挙げてくれたら幸いです。どうかお願いしますm(__)m。
- 締切済み
- C・C++・C#
- 辺彩色のアルゴリズム
グラフ理論についての質問です。 平面グラフを辺彩色するのに必要な色の最小の数を求めるアルゴリズムがあるとききました。 しかし、調べてみましたがどのようなものかわかりません。 知っている方いましたら教えてください。
- 締切済み
- その他（プログラミング・開発）
- グラフ理論の問題について
Gをn個の頂点とM本の辺を含む、以下の条件を満たすグラフとします。 このグラフの全ての辺をk通りの異なる色に彩色したとき、そのうち任意のm個の異なる色が選ばれたとしても残りのk-m色のみで塗られた辺によって出来た部分グラフが連結であるような彩色の仕方が存在する。 ここでk,n,mをパラメーターとした時、「最小の」Mの値を求めたいのですが、m=1の時の解しか得られませんでした。どのようなグラフ理論的なテクニックを用いてこの問題を解くべきなのでしょうか？この種の問題は一般的にグラフ彩色の問題として分類されるのでしょうか？なにか一般解を得るためのヒントや手助けとなりそうなアイディアや論文などありましたらお教え願いたいです。
- ベストアンサー
- 数学・算数
- 最大カット問題と最小カット問題の違い
グラフ理論において辺に重みが付されているときに、最大カット問題あるいは最小カット問題というのが定義されると思うのですが、これらは学問的に別の意義を持つものなのでしょうか？ 重みの正負を逆にすれば同じ問題ではありますが、もし重みを非負としたら、最大カット問題はカットに含む辺の数が必然的にn/2に近づくので、グラフ分割問題と似た様相を呈することになるのかなーと考えています。 もし学問的に問題ごとに明確な定義が与えられているのなら是非知りたいです。 ご意見お待ちしております。
- ベストアンサー
- 数学・算数
- 数学１の問題です
数学の問題です。 超基礎の問題で申し訳ないのですが。 Xの二次関数ｙ＝ax^2-2a^2x+a^3+a^2-aが最大値６をとるとき。aの値を求めよ。 を解くのですが、「最大値が存在するから、グラフは上に凸である。a<0」 であるらしいのです。 頂点のy座標が６であるという条件だけで解いたのでaの値は二つでます。 解を一つにしぼるのにa<0を使いました。 次の問題（x^2-2ax+2a^2+2a-3の最小値は５であるとき、aの値を求めよ）では、解は二つ出ます。どうやら、それが答えのようです。 最大値だと解は一つで、最小値では解が二つになるわけではないのですよね・・・？ 一問目風にいうなら、二問目は「最小値が存在するから、グラフは下に凸である。a＞０」にはならないのですか？ どなたか教えてください！！
- ベストアンサー
- 数学・算数
- グラフ理論（木について）の証明
2点以上の点からなる木は、2部グラフであることを数学的帰納法を用いて証明するには、どのようにしたらよいのでしょうか？ ※使っても良い事実として、「2点以上の点からなる木では葉が存在する」というものがあります。 点の個数が2のときは明らかであることは分かるのですが、その後どのようにしたらよいのかが分かりません。 （もし、点の個数を使うときはn，辺の個数はeを用いて教えてください） よろしくお願いします。
- 締切済み
- 数学・算数
