生成区间图的算法

Question

我想知道是否有任何算法或一些简单的过程来生成interval graph？
我需要生成带有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); 
} 

虽然，在某些情况下，它不能产生区间图。

Answer 1

一种可能的方式来生成的间隔图形用N个节点：

• 创建阵列[1，1，2，2，... N，N-]
• 洗牌阵列
• 创建一个图：
  • 每个节点v_i对应的混洗阵列中的对i OCCURENCES的
  • 两个节点v_i和v_j用边连接，如果i和j在数组中交织。这是i j i j或i j j i，但不是i i j j。换句话说，间隔i和j相交。

此图被保证是一个间隔图形（每个节点是原始阵列中的间隔），和每一个图形是可能创造这样。