1

我想知道是否有任何算法或一些简单的程序来生成区间图？
我需要生成带有n节点的区间图，其中n从 1 变为 10000。
如果可能的话，我需要图的关联矩阵表示。
另一个限制是不要让所有这些图表都完整。

提前谢谢大家！

==添加==

这是Java中的一个实现：

public Object generate(int numberOfNodes) {
    int listCapacity = numberOfNodes * 2;
    List<Integer> arr = new ArrayList<Integer>();
    int[][] adjacencyMatrix = new int[numberOfNodes][numberOfNodes];
    Integer nodeNumber = 0;
    for (int i = 0; i < listCapacity; i = i + 2) {
        arr.add(nodeNumber);
        arr.add(nodeNumber);
        nodeNumber++;
    }

    Collections.shuffle(arr);

    for (int i = 0; i < numberOfNodes; i++) {
        for (int j = arr.indexOf(i); j < arr.lastIndexOf(i); j++) {
            adjacencyMatrix[i][arr.get(j)] = 1;
            adjacencyMatrix[arr.get(j)][i] = 1;
        }
        adjacencyMatrix[i][i] = 0;
    }

    return new Graph(adjacencyMatrix);
}

但是，在某些情况下，它无法生成区间图。

4

1 回答 1

3

生成具有 N 个节点的区间图的一种可能方法：

  • 创建一个数组 [1, 1, 2, 2, ... n, n]
  • 打乱数组
  • 创建图表：
    • 每个节点v_i对应i于洗牌数组中出现的一对
    • 两个节点v_i并v_j与一条边 iff 连接i并j在数组中交错。那是i j i jor i j j i，但不是i i j j。换句话说，区间i和j相交。

这个图保证是一个区间图（每个节点都是原始数组中的一个区间），每个图都可以这样创建。

于 2013-05-03T13:25:04.247 回答