11

GraphViz でのサブクラスターのオーバーラップについて尋ねたところ、次のような回答がありました。

申し訳ありません。一般的なサブグラフは、サブセットの包含を意味することなくノードを共有できますが、クラスタは共有できません。問題は図面にあります。クラスターが任意にオーバーラップできる場合、それらを描画することは、適切なアルゴリズムがないベン図を描画する際の問題になります。

「ベン図の描画の問題」の正式な定義または例は何ですか? また、なぜそれが難しいのですか (NP 完全/ハードだと思います) ? (おまけ: 有名な NP 完全問題への縮約をスケッチしてください)

4

2 に答える 2

5

N 個の点とその上に二項関係 R があり、すべてのノードがユークリッド平面上の円で表されるように関係をグラフィカルに表現する必要があります。 n R n' を保持します。

于 2012-04-29T20:11:11.940 に答える
3

ベン図そのものの代わりに、多くの場合、セットの交点のブール格子である双対グラフを使用して、同じ目的で GraphViz を使用できます。各ノードは、含めるセットと除外するセットの一意の選択を表します。1 つのセットの包含/除外のみが異なるノードが接続されます。

セットの数が増えると、もちろん、一般に非常に多くのノードとエッジが存在します。しかし、多くの実際の設定では、まったく交差しないセットが多数存在するため、それらの交差ノードとそれらから他のノードへのエッジは省略される場合があります。この方法により、ノードとエッジの数を実用的な数に減らすことができます。

結果のグラフをレイアウトするときは、GraphViz アルゴリズム「neato」を選択し、ノードのオーバーラップを避けるように依頼するのが最善の場合があります。これらの設定を行う 1 つの方法は、グラフの左中括弧内にlayout=neato,overlap=prism; .

于 2012-11-14T16:03:45.073 に答える