Red - Black Spanning Tree

Question

Good morning,

I came across the following question that deals with Graphs and was not able to come up with a correct solution. I would appreciate any possible help:

You are given a graph, some edges are black, some are red. Find a spanning tree with one restriction: if we take some node as root, every path from it to some leaf node must consist of alternating red-black-red-black edges. That is, no path from root to leaf must contain sequential black-black edges or red-red edges. You are guaranteed that such spanning tree exists.

Thanks.

Do all edges leaving the root have to be the same colour? Or can some be red and some black? — j_random_hacker
@j_random_hacker I think the edges leaving the root node do not necessarily have to of the same color. — user118837
The wording is a bit unclear. Does "if we take some node as root" mean "for any node being considered as root, the property holds", or just "there exists a node for which the property holds"? — Gassa

Gabriel Furstenheim Gabriel Furstenheim · Accepted Answer · 2018-08-21T19:22:45

This is probably not the most efficient solution and it would be quite cumbersome to write.

Consider a graph where each node is a tree that has the given root. There is a side from one node A to another B if B consists of A with one extra edge. We could traverse this hyper graph with a BFS and stop when we find a spanning tree. In fact, we could also work out the case when there is not such a tree.

Say that you are given a graph by (id, vertex, vertex, color) defined by (1, e1, e2, b),(2, e1, e3, r),(3, e1, e4, b) and the root node is e4.

First element of the iteration would be (-1, e4, nil) (-1 is id of edge to arrive to the node, nil represents the color with which you arrive from root) Next iteration we have [(-1, e4, nil), (3, e1, b)]. In the third, iteration, as we are arriving to e1 with blue, we can only add [(-1, e4, nil), (3, e1, b), (2, e3, r)]

In this example, there was only one possible edge addition. In general, we would need to keep track of all possible trees at a given point.

Note that the hypergraph of trees is a DAG (every side adds an edge, after n steps you arrive to a tree that has more edges that the one you started with).

Red - Black Spanning Tree

1 Answers