0

平面グラフ生成用のアルゴリズムを構築しようとしています。私はこの主題に関する多くの資料を読みましたが、ここにいくつかの結果があります:

public Graph graph;
...

public Level(int numPoints, int numEdges, int levelID, int timeLim) 
{
        this.graph = new Graph(numPoints, numEdges);
    this.graph.GeneratePlanarGraph();
        ...
}

ここでは、平面グラフを作成する関数をいくつか書きました...

public void GeneratePlanarGraph() {
    if(this.edges_num < this.vertices_num) {
        System.out.println("erroe: number of edges mast be\n "+
                    "bigger than number of vertices\n");
        return;
    }
        
    int edges = 0;
        
    // add vertices to graph
    for(int i = 0 ; i < this.vertices_num ; i++) 
            this.AddVertex(i+1);
        
    // connect all vertices to circular list 
    // ( from each vertex 2 connections )       
    for(int i = 1 ; i <= this.vertices_num ; i++) {
        if(i < this.vertices_num) this.AddEdge(i, i+1);
        else this.AddEdge(i, 1);
        edges++;
    }
        
    //connect other edges if its exist
    int step = 2;
    while(edges < this.edges_num) {
        for(int i = 1 ; i <= this.vertices_num ; i++) {
            if(i + step <= this.vertices_num) {
                this.AddEdge(i, i + step);
                edges++;
                if(edges == this.edges_num) break;
            }
            else {
                this.AddEdge(i, (i + step) - this.vertices_num);
                edges++;
                break;
            }
        }
        step++;
    }
}

プログラムを開始すると、次のように多数の平面グラフが生成されます。

for(int i = 0 ; i < 100 ; i++)
{
    levels[i] = new Level(numPoints, numEdges,  levelID,  timeLim);
}

これらのコードはすべて機能しますが、テスト中にグラフ (レベル) 24、36、... が平面ではないことがわかりました。

オイラーの公式について知っているので、オイラーの公式で頂点/エッジを生成しようとしましたが、ご覧のとおり、実際には機能していません。

4

1 に答える 1

2

まず安心してください、オイラーの公式はまだ成り立っています。

あなたのアルゴリズムにはいくつかの問題があります（スタイルは別として）：

  • 奇数の V (頂点の数) と十分に高い E (エッジの数) では機能しません。より正確には: V = 2k+1 および E >= 2V の場合、結果のグラフは平面ではありません。
  • E > 2V では期待どおりに動作しません。何をするかに応じてAddEdge、同じ頂点間のエッジが多いマルチグラフが生成されるか、必要以上にエッジが少ないグラフが生成されます。
  • それは (それが機能する場合に) 平面グラフの非常に特別なクラスを生成するだけであり、私の意見では、あまり興味深いクラスではありません。
于 2013-01-18T22:03:05.480 に答える