- ベストアンサー
グラフを分割する
無向グラフを適当に分割する方法に、2連結成分に分割する、という方法があることを知ったのですが、何か実現できるプログラムはあるでしょうか? よろしくお願いいたします。
- furio
- お礼率25% (1/4)
- その他(プログラミング・開発)
- 回答数4
- ありがとう数1
- みんなの回答 (4)
- 専門家の回答
質問者が選んだベストアンサー
補足ありがとうございます。 私が「2連結成分」という語を知らないために、不適当な補足要求をしてしまったことに気付きました。失礼しました。 英語ですが、比較的平易に書かれているので、以下の PDF ファイルがグラフの2連結成分ヘの分割のためのアルゴリズムを理解するうえで、私が検索したなかでは、最も参考になりました。 http://csci.biola.edu/csci480spring03/biconnectedcomponents.pdf また、アルゴリズム自体を簡潔に書いているサイト、本もあるかと思います。(検索キーワードは、例えば、biconnected component algorithm などが適当かと思います。) ご自分でアルゴリズムをお書かきにならないのでしたら、CPAN の Graph module (参考URL) をインストールし、perl で入出力部だけお書かきになってもよいかと思います。 他言語によるこのアルゴリズムの実装もあると思うのですが、恐らく入出力はご自分でお書かきにならなければならないかもしれないと思いました。
その他の回答 (3)
- graphaffine
- ベストアンサー率23% (55/232)
あるかどうかという質問ならば、あるでしょうというのが回答です。どこにあるかはわかりませんがそんなに難しい話ではありませんし、きっとあるでしょう。 私も作ろうと思えば作れますし。
- bender
- ベストアンサー率45% (108/236)
> 「無向グラフを適当に分割する方法に、2連結成分に分割する、という方法が...」 というのは、おおよそ、「『ひとつながり』のグラフが与えられたとき、(グラフの頂点を結ぶ辺をいくつか除くことで、)グラフを2つの『ひとつながり』のグラフに分割する」というような意味でよいのでしょうか? その場合、まず、与えられたグラフが『ひとつながり』であるか確認しなければならないのでしょうか? いずれにしても、「適当に」の部分があいまいであるように思います。例えば、分割後の2つのグラフの頂点の数が(ほぼ)同じであるのか、あるいは、2つのグラフの辺の数が(ほぼ)同じであるのか、あるいは、分割する時に除く辺の数が最小であるのか、などです。 補足をお願いします。
補足
不要な「適当に」を書いてしまって、余計な誤解をうんでしまったようで、すいません。 「無向グラフの2連結成分をみつける方法」でいいでしょうか? 2連結成分を数え上げる(という言葉も誤解を生む?)ことなので、分割後の2つのグラフの頂点とか辺の数が同じであることは気にする必要はない…と思っています。
- seasoning
- ベストアンサー率25% (182/713)
ちょっと質問がアバウトすぎて回答に困りますね。 求めている「言語」、「入力」、「出力」ぐらいの 情報はないと、皆さんも回答できないと思いますよ。 >何か実現できるプログラムはあるでしょうか? 数学的な考え方ができるのであれば、プログラムで 実現するのは可能だと思います。
補足
す、すいません。 入力は、どの頂点とどの頂点が結ばれているか各行に書かれているテキストがあって、それで無向グラフを表現していたとすると、計算後に各成分ごとの頂点名を出力してくれる、といったイメージです。 言語は…CとかPerlとか、Linuxで動くものでお願いします。 専門外なのでとんちんかんなことを書いているかもしれません。プログラムは不得意ですのでもしも親切な方で教えて頂けたらうれしいです。
関連するQ&A
- グラフの証明を教えてください
背理法の証明で 連結で、全ての頂点次数が偶数であり、オイラーツアーを持たないグラフがあるとするときの そのうち最も辺の少ないグラフをGとします Gの中のツアーで中で、最も辺の数が多いものをCとします。 そのときGからCの辺をすべて取り除いたグラフの連結成分Hがあるとしたとき Hの各頂点の次数は偶数である。 この証明を教えてください。
- 締切済み
- 数学・算数
- 分割されているゲームファイル
ファイルが分割されているゲームがあるのですが、どのようにすれば使用出来ますか? テキトウに連結ソフトを使ってみたのですがうまくいきませんでした。
- ベストアンサー
- その他(インターネット・Webサービス)
- オイラーグラフの十分条件について
グラフ理論についての質問です。よろしくお願いします。 「グラフGのすべての辺eについてeを含むサイクルが奇数個ならば、Gはオイラーグラフ」 を証明したいです。 「辺を含むサイクルの個数」という条件をどう活かすかが思いつかず、背理法で示そうとしましたが、そちらもうまくいきません。 (最長のトレイルPを定めて、「Pに含まれない辺を含むサイクル」を用いてPの最長性に矛盾させる方針で考えていました) また、そもそもGは連結という条件が必要だと思うのですが(非連結でもよいとすると各連結成分がサイクルであるグラフが反例になってしまうので)、問題文中にそのような記載は特にありませんでした。 非連結だとオイラーグラフにはなり得ないので、自明な前提として省略している可能性もあるとは思いますが、「Gは連結である」ということは暗に認めてしまっても良いものなのでしょうか? 以上になります。ご教示いただければ幸いです。
- ベストアンサー
- 数学・算数
- グラフ理論の問題についての質問です
大学のグラフ理論の問題でわからないものがあったので質問させていただきます。 ****************** 問題: グラフGが位数|V(G)|=nでk個の連結成分を持つグラフの時、辺数|E(G)|が n-k≦|E(G)|≦1/2(n-k+1)(n-k) をみたすことを示しなさい。 ******************* 以上の問題を帰納法をつかって証明しようとしたのですが、詰まってしまいました。 よろしければこの問題の証明方法を教えてください。 よろしくお願いします。
- 締切済み
- 数学・算数
- エクセルのグラフで突出したデータを分割表示できますか?
エクセルで棒グラフを描いていますが、1つだけ突出したデータがある場合、他のデータが小さくなってしまいますよね。 そこで、よく使われるのが、長いグラフの途中を波線などで分割して、目盛も分割して、小さいデータを大きく見せますけど、エクセルで同じような事は可能でしょうか??
- ベストアンサー
- オフィス系ソフト
- 分割円グラフ・・・グループ別に作成するには?
分割円グラフ・・・グループ別に作成するには? いつもアドバイスを参考にさせて頂いています。分割(3D)円グラフを使って グループ別に作成中です。 例えば、アンケートデータを「関心がある」「少し関心がある」を隙間が空かないようにつけて、 「少し関心がない」と「関心がない」を隙間が空かないようにくっつけるようにしたいのですが、 どうすれば作成できますか?よろしくお願いします。
- ベストアンサー
- その他MS Office製品
- Access97のグラフについて
Access97のグラフウィザードで棒グラフを作成しましたが,1ページ分しか作成されません。それらしき設定も探せませんでした。対象データを全て出力させるにはどうしたら良いでしょうか?VBAを用いないで実現する方法を教えて下さい。宜しくお願いします。
- ベストアンサー
- オフィス系ソフト
お礼
ありがとうございます! CPANをインストールして解決できました。 いやー聞いてみてよかったぁ。 大助かりです!!