グラフを分割する

質問

無向グラフを適当に分割する方法に、２連結成分に分割する、という方法があることを知ったのですが、何か実現できるプログラムはあるでしょうか？
よろしくお願いいたします。

回答No.3

bender · ベストアンサー

補足ありがとうございます。

私が「２連結成分」という語を知らないために、不適当な補足要求をしてしまったことに気付きました。失礼しました。

英語ですが、比較的平易に書かれているので、以下の PDF ファイルがグラフの２連結成分ヘの分割のためのアルゴリズムを理解するうえで、私が検索したなかでは、最も参考になりました。
http://csci.biola.edu/csci480spring03/biconnectedcomponents.pdf

また、アルゴリズム自体を簡潔に書いているサイト、本もあるかと思います。(検索キーワードは、例えば、biconnected component algorithm などが適当かと思います。)

ご自分でアルゴリズムをお書かきにならないのでしたら、CPAN の Graph module (参考URL) をインストールし、perl で入出力部だけお書かきになってもよいかと思います。

他言語によるこのアルゴリズムの実装もあると思うのですが、恐らく入出力はご自分でお書かきにならなければならないかもしれないと思いました。

参考URL：

http://search.cpan.org/~jhi/Graph-0.58/lib/Graph.pod

お礼

ありがとうございます！
CPANをインストールして解決できました。
いやー聞いてみてよかったぁ。
大助かりです！！

回答No.4

graphaffine

あるかどうかという質問ならば、あるでしょうというのが回答です。どこにあるかはわかりませんがそんなに難しい話ではありませんし、きっとあるでしょう。
私も作ろうと思えば作れますし。

回答No.2

bender

> 「無向グラフを適当に分割する方法に、２連結成分に分割する、という方法が...」

というのは、おおよそ、「『ひとつながり』のグラフが与えられたとき、(グラフの頂点を結ぶ辺をいくつか除くことで、)グラフを２つの『ひとつながり』のグラフに分割する」というような意味でよいのでしょうか？

その場合、まず、与えられたグラフが『ひとつながり』であるか確認しなければならないのでしょうか？

いずれにしても、「適当に」の部分があいまいであるように思います。例えば、分割後の２つのグラフの頂点の数が(ほぼ)同じであるのか、あるいは、２つのグラフの辺の数が(ほぼ)同じであるのか、あるいは、分割する時に除く辺の数が最小であるのか、などです。

補足をお願いします。

補足

不要な「適当に」を書いてしまって、余計な誤解をうんでしまったようで、すいません。
「無向グラフの2連結成分をみつける方法」でいいでしょうか？
2連結成分を数え上げる（という言葉も誤解を生む？）ことなので、分割後の2つのグラフの頂点とか辺の数が同じであることは気にする必要はない…と思っています。

回答No.1

seasoning

ちょっと質問がアバウトすぎて回答に困りますね。

求めている「言語」、「入力」、「出力」ぐらいの
情報はないと、皆さんも回答できないと思いますよ。

>何か実現できるプログラムはあるでしょうか？
数学的な考え方ができるのであれば、プログラムで
実現するのは可能だと思います。

補足

す、すいません。
入力は、どの頂点とどの頂点が結ばれているか各行に書かれているテキストがあって、それで無向グラフを表現していたとすると、計算後に各成分ごとの頂点名を出力してくれる、といったイメージです。

言語は…CとかPerlとか、Linuxで動くものでお願いします。

専門外なのでとんちんかんなことを書いているかもしれません。プログラムは不得意ですのでもしも親切な方で教えて頂けたらうれしいです。