我已经实现了 MC Golumbic 的“算法图论和完美图”一书中的可比图识别算法。Fekete、Schepers 和 van der Veen 的“Exact Algorithm for Higher-Dimensional Orthogonal Packing”论文中暗示，可以修改该算法，以便在给定否定识别结果的情况下，您可以获得两个无弦循环。但是没有解释它是如何完成的，我对图论的了解也没什么特别的。

我目前的直觉是，如果识别算法在级别失败$k$那么必须在不可能传递方向的情况下创建了一个循环。这意味着在水平故障点的边缘集$k$会产生一个包含我正在寻找的循环的子图，然后我只需要修剪掉与创建的循环无关的边缘。

我的问题：我的直觉是否正确，如果不正确，Fekete、Schepers 和 van der Veen 的“易于修改”提示是什么意思？

我这样做是为了提高效率，我想通过一次算法搜索获得两个结果。

import networkx as nx

def comparability(G):
  classification = dict()
  k = 0 
  def explore(i, j): 
    # k and classification from outer function
    adjacent_I = set(G.neighbors(i))
    adjacent_J = set(G.neighbors(j))
    classtest = lambda e: e in classification and abs(classification[e]) != k
    for m in adjacent_I:
      if m not in adjacent_J or classtest((j, m)):
        if (i, m) not in classification:
          classification[(i, m)] = k 
          classification[(m, i)] = -k
          if not explore(i, m): 
            return False
        elif (i, m) in classification and classification[(i, m)] == -k: 
          return False
    for m in adjacent_J:
      if m not in adjacent_I or classtest((i, m)):
        if (m, j) not in classification:
          classification[(m, j)] = k 
          classification[(j, m)] = -k
          if not explore(m, j): 
            return False
        elif (m, j) in classification and classification[(m, j)] == -k: 
          return False
    return True
  for i, j in G.edges():
    if (i, j) not in classification:
      k += 1
      classification[(i, j)] = k 
      classification[(j, i)] = -k
      if not explore(i, j): 
        return False, classification
  return True, classification

G = nx.Graph()
G.add_nodes_from([1,2,3,4])
G.add_edges_from([(1,2),(1,3),(1,4),(3,4)])
print comparability(G) # True

G = nx.Graph()
G.add_nodes_from([1,2,3,4,5,6])
G.add_edges_from([(1,2),(2,3),(2,4),(3,4),(3,5),(4,6)])
print comparability(G) # False