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 回答