algorithm - 给定一个图 G，验证所有离开顶点 u 的简单最大路径必然经过与不同奇偶校验数相关的 2 个顶点

Question

给定一个图 G、一个顶点 u 和一个将每个顶点 v 与一个自然数关联的数组 VAL[](对于 V 的每个顶点 v，VAL[v]=n，其中 n 是自然数)。

G 中的简单路径如果不能再扩展，则为最大，同时保持属性简单。

定义一个算法，验证所有离开顶点 u 的简单最大路径必须通过与不同奇偶校验数相关的 2 个顶点。

是否有一种算法可以在图的维度上以线性时间求解？

此图片中的意大利语翻译:

编辑: 我的第一个解决方案。

class color(Enum):
    white = "white"
    grey = "grey"
    black = "black"

class Node(object):

    def __init__(self, name, adjacency=[],
                 visited=False, predecessor=None):
        self.name = name
        self.adjacency = adjacency
        self.visited = visited
        self.predecessor = predecessor

    def __repr__(self) -> str:
        return f'''{self.name}'''

    def append(self, vertex):
        self.adjacency.append(vertex)


def dfs(start: Node, VAL: dict):
    start.visited == color.grey
    parity = VAL[start.name] % 2
    for v in start.adjacenciesList:
        if v.visited == color.white:
            if parity != (VAL[v.name] % 2):
                return True
            if dfs(v):
                return True
    start.visited == color.black
    return False


if __name__ == "__main__":
    node1 = Node("A")
    node2 = Node("B")
    node3 = Node("C")
    node4 = Node("D")

    node1.append(node2)
    node1.append(node3)
    node2.append(node3)
    node2.append(node4)
    node3.append(node4)
    VAL = {"A": 1, "B": 3, "C": 4, "D": 5}
    print(dfs(node1, VAL))

Answer 1

运行 BFS 并为队列中的每个节点维护以下状态:

Can be reached visiting only odd parity on the way
Can be reached visiting only even parity on the way

对于每个终端节点(没有尚未访问过的邻居的节点)，回答该问题时也要考虑其访问过的邻居(即使我们不从它继续 BFS)。在 BFS 结束时对任何状态问题回答"is"的终端节点将使图无效。如果它只有一个访问过的邻居(我们来自的那个)，或者两者的任意组合，它可以回答"is"。

假设我们有图表，

[(1, 2), (1, 3), (1, 5), (2, 5), (3, 5)]

1 - 2
| \ |
3 - 5

u = 1

(为简单起见，每个节点的 VAL 与其标签相同)。 BFS 元素表示(node, can_be_reached_even, can_be_reached_odd)。像这样的东西:

queue: [(1, False, True)]
visited: {
  1: [False, True]
}

queue: [(2, False, False), (3, False, True), (5, False, True)]
visited: {
  1: [False, True],
  2: [False, False],
  3: [False, True],
  5: [False, True]
}

当我们达到 2 时，它的所有邻居都被访问，因此我们认为它们都是奇数，2 是偶数，并且无法通过将 2 放置在路径中来保持奇偶校验状态。

当我们到达 3 时，它的所有邻居都已被访问过，因此有一条从 u 到它们的路径。我们看到我们可以通过 3 连接两个邻居(也是所有邻居)1 和 5，并以奇校验到达它们。由于 3 也是奇数，这将形成一条奇怪的简单路径，这将使图表无效，我们可以提前退出。

上面描述了基本思想。需要一些工作来检查它是否健全且完整，或者可能需要针对更复杂的场景进行一些调整(或彻底修改或丢弃)。