問題タブ [planar-graph]

頂点の重みがW（V）の無向循環平面グラフG（V、E）、E（G）を埋め込んだ固定平面、および2つのノードsとtが与えられた場合、2つの連結成分に分割するGの分割を見つける必要があります。 S（G）とT（G）。sはS（G）にあり、tはT（G）にあります。頂点sとtは両方とも、埋め込みE（G）の外面に属します。

パーティションのバランスをうまく取りたいのですが、頂点の重みの合計がほぼ等しい必要があります。

良いアルゴリズムのアイデアはありますか？

プロジェクトの 1 つにnetworkx (python グラフ描画パッケージ) http://networkx.lanl.gov/index.htmlを使用しています。networkx はかなりクールですが、クロス エッジの数が原因で、表示機能が最悪です。グラフの交差エッジを最小限に抑える方法はありますか? 交差エッジが最小化されるような方法でノードをソートできるアルゴリズムを意味しますか?

星形グラフのみで構成されるグラフGがあります。スター グラフは、他のすべてのノードへのエッジを持つ 1 つの中央ノードで構成されます。H ₁、H 2 _、 …、H _nを、 Gに存在するさまざまなサイズのさまざまな星形グラフとします。任意のスター グラフの中心であるすべてのノードのセットをRと呼びます。

ここで、これらのスター グラフが他のスター グラフにエッジを構築し、Rのどのノード間にもエッジが発生しないとします。次に、グラフが平面のままである場合、RのノードとRにないノードの間に最大でいくつのエッジが存在しますか?

そのようなエッジの数の上限が必要です。私が念頭に置いている上限の 1 つは、 Rが頂点の 1 つのセットであり、残りの頂点が別のセットAを形成する 2 部平面グラフと見なすことです。これらのセット ( RとA ) の間のエッジに関心があります。これは平面の 2 部であるため、このようなエッジの数はGのノード数の 2 倍に制限されます。

私が感じているのは、おそらくAのノードの 2 倍にRのノード数を加えた、より良い境界があるということです。

私の直感を反証していただけるなら、それもいいですね。うまくいけば、あなたの何人かが、いくつかの関連する議論とともに適切な境界を思いつくことができます.

私はホームタスクを持っています：

平面グラフの埋め込みのビジュアライザーを作成する（または、このプロセスの正しい単語がわからない）。

平面グラフは平面グラフと同形であり、平面グラフはエッジが交差しない平面上に描かれたグラフです。

これを行うにはアルゴリズムが必要です。ロシア語の記事が1つあり、「ガンマアルゴリズム」という名前のアルゴリズムがそこに記述されていますが、さらに情報を見つけたいのですが、「ガンマアルゴリズム」については何も見つかりませんでした。英語、それは別の名前を持っているようです）、または英語の他のアルゴリズムについても。

誰かがアルゴリズムの名前とそれらの説明へのリンクを提案できますか？

私の英語が下手ならごめんなさい:)

2D 空間でランダムな点を生成したいのですが、この点は平面グラフのノードになります (ガブリエル グラフアルゴリズムまたは RNG を使用して構築されます)。

これを行うためにJavaコードを書きましたが、解決するのが難しい問題が2つあります。

1) グラフのすべてのエッジが特定のしきい値より長くないことが必要です

2）グラフの面を知りたい後、面はエッジで接続されたノードの集まりです。面には他のノードは含まれません。下の画像では、顔はラベル (F1、F2...) によって署名されています。

これら2つのことを行う方法は？いくつかのアルゴリズム？すでに知られている方法はありますか？

以下に、作成する必要があるグラフの例を示します

http://imageshack.us/photo/my-images/688/immagineps.png/

グラフ問題として定式化できる多くの問題に遭遇しました。一般にNP困難ですが、グラフが平面であることが証明される場合があります。したがって、これらの問題とアルゴリズムを学ぶことに興味があります。

私が知る限り：

1. 平面グラフの最大カット
2. 平面グラフの 4 色
3. 立方平面グラフの最大独立集合

誰かがこのリストを完成させてくれることを願っています。

私は以下に説明するJavaの小さなプロジェクトに取り組んでいます：

入力：有向グラフのオブジェクトのリスト。（エッジの種類が異なるノード：継承、内部クラス、フレンドクラスなど。）出力：クラス図、可能な限り平面。

私の問題は次のとおりです。サードパーティのソフトウェアでそれを実行できるか、少なくともグラフをできるだけ平面に保つためにノードとエッジを選択するアルゴリズムが必要です。

編集：私は私が望むものを明確に書いていなかったかもしれません...私はそのファイルでJavaプロジェクトに基づいてクラス図を生成したくありませんが、私はC ++ファイルを解析して、上記の入力で説明されたリストから取得します。次に、そのリストの関数を呼び出して、ダイアグラムを取得します。JGraphまたはJGraphTを使用しようとしましたが、残念ながら、要件に合ったグラフ理論機能が見つかりませんでした。

よろしく、ダニエル

Processing を使用して、複雑なデータとプロセスのナビゲーション システムを開発しています。その一環として、私はグラフ レイアウトにかなり深く入り込みました。それはすべて楽しいものであり、レイアウトアルゴリズムに関する私の意見は次のとおりです。強制指向は弱虫向けです（スケールを見てください...笑）、固有ベクトル投影はクールです、杉山レイヤーは見栄えがしますが、グラフィーグラフでは速く失敗します。これまでの固有ベクトルでは、エッジの交差を最小限に抑えて、実際にデータのポイントに到達する必要があります。私は知っています、私はNP完全などを知っています。

xyボクシングを適用し、杉山のような順列を使用して、行と列をまたがるエッジの交差を減らすことで、ある程度の成功を収めたことを付け加えておきます。Viz: グラフ (|V|=90,avg degree log|V|) は、交差を減らすために行と列の置換を交互に行うことにより、11000 の交差 -> 1500 (箱入りの固有ベクトルによる) -> 300 に進むことができます。

しかし、極小値は... それが何であれ、このマークの周りに留まり、結果は可能な限り明確ではありません. 光に関する私の研究は、VLSI で使用されているような平坦化アルゴリズムを本当に使用したいことを示唆しています。

1. BFS などを使用して、最大平面サブグラフ 1.a を作成します。平面サブグラフをナイスライクにレイアウトする
2. 卓越したエッジを巧みに追加して元のグラフを復元する

最速の平坦化アルゴリズムについての考えを返信してください。よく知っている特定の最適化について詳しく説明してください。

本当にありがとう！

ですから、最近、グラフ理論と結び目理論の関係についての論文を読んでいて、それで結び目をコードで表現することを考えました。

この問題に関する私の現在の直感は、結び目を本質的に平面グラフとして扱い、各頂点が任意の交差点に配置されていることです。次に、特定の頂点に対して交差がどのように方向付けられたかも保存します。

これはほとんどそれが行われている方法ですか、それともそこにもっと良い方法がありますか？

ありがとう！