[グラフ理論] タグが付いた質問
ノードの集合とエッジの集合で構成されるグラフの数理についての理論である、情報科学の一分野。1736年、「ケーニヒスベルクの問題」に対してオイラーが解法を示したのが起源とされる。
13
質問
2
票
1
回答
170
閲覧数
ラベル無し連結単純無向グラフの型の列挙は?
例えば頂点が3個のグラフの場合、それが単純で無向グラフでラベル無しで連結となると2通りだと直ぐに分かる。でも4個となるとイメージしても厄介だし5個だと紙と鉛筆を使っても怪しい。そこでプログラミングで列挙してみたいと思ったのだけどコレが厄介。連結の判断は兎も角、同型の判別が大変。接続行列だと頂点5個でも単純に2^10通りある。連結だからもう少しは減らせるとしても。...
1
票
2
回答
233
閲覧数
自由度の高いフローチャートと、テキストの相互変換
エクセルにより、以下のようなフローチャートを作成しました。
矢印の方向はもちろん、オブジェクトの位置やテキストボックスの枠線のタイプにも意味があります。
このフローチャートはエクセルなのでGUIで作成していますが、テキストベースでエクスポート(表現)する方法はあるでしょうか?
0
票
2
回答
423
閲覧数
ダイクストラ法で最短経路を見つけるときに負の値を持つ辺があると経路は正しくても誤ったコストが出力される
ダイクストラ法のコード(python)を参考に以下のプログラムを実行しました。
出力として最短ルートは'A->C->B->D'と求められましたが、コストは「5+(-4)+1=2」になるところ、'A->B->D'の「3+1=4」が出力されました。原因がわからないです。
グラフ部分はコードのrouteにあたります。
出力
$ python dijkstra.py
visited to A.
...
1
票
1
回答
383
閲覧数
レーベンシュタイン距離(編集距離/エディットグラフ)の出力とグラフにおける最短経路に関して
レーベンシュタイン距離(編集距離)を計算して、2単語間の最小編集コストを求めようとしています。
以下のように、python-Levenshteinというライブラリを使って簡単に実行できますが、グラフを書いて同数の最短ルートが求められずに困っています。
「kitten」を「sitting」に変形する場合には、3回の処理が必要で手で文字を入れ替え・削除処理をする場合や、レーベンシュタイン距離(...
5
票
0
回答
135
閲覧数
グラフ構造の探索に対応するデータ構造には法則があるのでしょうか?
グラフ構造、たとえばツリー構造を探索することを考えます。
ツリー構造の場合は、探索の例は幅優先探索や、深さ優先探索があります。
この時、
幅優先探索はしばしばキューを用いて
深さ優先探索はしばしばスタックを用いて
それぞれ実装されます。
これはちょうど、
各ノードを訪問した時に、そこから見えるまだ未探索のノードについて適当な順序で push() を行う
次のノードを pop() ...
0
票
1
回答
101
閲覧数
pandasデータへ変換する方法を教えて下さい。
pythonのループの仕方を教えて下さい。
よろしくお願いします。
(参考)無向グラフと有向グラフ>無向グラフの隣接行列(adjacency matrix)
http://www.dais.is.tohoku.ac.jp/~shioura/teaching/ad11/ad11-09.pdf#page=5
import pandas as pd
# input : 線分a [0,1]
# ...
2
票
2
回答
877
閲覧数
線分群から、閉図形の数を数える方法を教えて下さい。
仕様1:2次元
仕様2:線分と線分の交差は、気にしません。
目的:輪(環)がいくつあるか知りたい。
例1
input : 線分1 [ 0, 0], [10, 0]
線分2 [10, 0], [ 0,10]
線分3 [ 0,10], [ 0, 0]
線分4 [-5, 0], [-5,10]
output : 閉図形の数=1
: ...
0
票
3
回答
3,225
閲覧数
幅優先探索を、キューを使わずに再帰関数を使って実装することはできるのでしょうか?
質問
グラフ構造に対して幅優先探索を再帰関数を使って実装することはできるのでしょうか?
深さ優先探索の場合、スタックか再帰関数を使って実装ができます。
一方で深さ優先探索の場合、キューを使って実装することはできたのですが、キューを使わずに再帰関数で実装することができずに困っています。
参考までに、キューを使った実装を下にのせておきました。幅優先探索するためのヒントもしくは、...
4
票
1
回答
582
閲覧数
どのような多面体かを知るコード
多面体を作る方法について
PythonでもCでもMatlabでも言語は問いません。
例えば正20面体に関する以下のようなデータがあるとします。
このデータは正20面体の各頂点0から11に関してどの3点でひとつの三角形、つまり正20面体のひとつの面を作っているかを示します。
この画像のように頂点をつなげていくことができます
データ1
6 4 0
4 9 0
9 3 0
3 11 0
...
4
票
1
回答
709
閲覧数
グラフ理論について、三次元空間における位置関係の情報をinvariantに保持する表現を計算したい
グラフ理論に関する質問です。
頂点(ノード)間の位置関係をinvariantに保持する方法・表現を考えたいです。
具体的な例として、ある化合物の分子を考えます。
ここで、その分子内の原子(グラフにおける頂点)たちと、
各原子の三次元座標(3次元ベクトル)が与えられています。
この三次元座標を用いて、頂点間の距離(グラフにおける辺の長さ)などが計算できます。
ここで、化合物内のある原子(...
3
票
2
回答
1,240
閲覧数
DOT言語の有向グラフが木構造か木構造でないかの判定方法を教えて下さい。
①有向グラフが木構造か木構造でないかの判定方法を教えて下さい。
②rootは入力ですか
よろしくお願いします。
(参考)DOT言語
https://ja.wikipedia.org/wiki/DOT%E8%A8%80%E8%AA%9E
(参考)WebGraphviz is Graphviz in the Browser
http://www.webgraphviz.com/
(判定)
...
8
票
2
回答
339
閲覧数
2部グラフ(V1, V2, E)で、V2からいくつか頂点を削除し、すべてのv∈V1が、1本のみの枝をもつようにするには?
2部グラフ(V1, V2, E)があります。
V2から点をいくつか削除し、それら点に紐付いていた枝を削除することで、すべてのv∈V1が1本のみの枝を持つ部分グラフ(V1, V', E')を作りたいのですが、
そのようなV'の存在の有無を判定し、また、その条件を満たすV'を少なくとも1つ得るには、どうすればいいでしょうか。
図のように、V2からいくつか点を削除したV'を得たいです。
このようなV'...
4
票
1
回答
2,020
閲覧数
安定結婚問題の「絶望の定理」の証明
グラフ理論において、安定結婚問題があります。
ある2部グラフの特定の安定マッチングにおいて、ペアを作れなかった人(たとえば男性数>女性数でのマッチングで存在)は、どのような安定マッチングにおいてもペアが作れないことを、安定結婚問題における「絶望の定理」と呼ぶらしいのですが、この定理の証明を見つけられずにいます。
証明自体、もしくは証明のソースをご存知の方はいらっしゃいますでしょうか。