Given a graph G, verify all simple max paths that depart from vertex u necessarily pass 2 vertices associated with numbers of different parity

user_10878999 0
Viewed 133

Given a graph G, a vertex u, and an array VAL[] that associates every vertex v with a natural number(For each vertex v of V, VAL[v]=n, where n is a natural number).

A simple path in G is maximal if it can't be expanded anymore, maintaining the property to be simple.

Define an algorithm that verifies that all simple maximal paths, that depart from vertex u necessarily pass 2 vertices associated with numbers of different parity.

Is there an algorithm that can solve it in linear time on the dimensions of the graph?

Italian translation in this image: enter image description here

edited: my first solution.



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))
breadth-first-search depth-first-search algorithm
1 Answers

Run a BFS and for each node in the queue maintain the following state:

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

For every terminal node -- a node that has no neighbours that have not already been visited -- answer that question also considering its visited neighbours (even as we don't continue the BFS from it). A terminal node that at the end of the BFS answers yes to any of the state questions would invalidate the graph. It can answer yes if it has only one visited neighbour (the one we came from), or any combination of two.

Say we have the graph,

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

1 - 2
| \ |
3 - 5

u = 1

(for simplicity, each node's VAL is the same as its label). BFS elements represent (node, can_be_reached_even, can_be_reached_odd). Something like:

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]
}

When we reach 2, all its neighbours are visited so we consider that they are both odd and 2 is even and there's no way to keep one parity state by placing 2 in a path.

When we reach 3, all its neighbours have been visited so there's some path from u to them. We see that we can connect two of the neighbours (which are also all of them), 1 and 5, via 3, having reached them with odd parity. Since 3 is also odd, this would make an odd simple path, which would invalidate the graph and we can exit early.

The above describes the basic idea. It would need some work to check if it is sound and complete as is or may need some tweaking (or overhauling or discarding) for more complex scenarios.

user_20347870
Related