Constructive Algorithms and Observations.
Consider a grid of dimension R*C having either 0 or 1 at each position. We define associated graph as the graph formed by compressing all positions having same values which are adjacent to each other in all 8 directions, into 1 node, and connecting it to other nodes having the different value, which are adjacent to the current node in all eight directions.
Now, we are given a graph, and we have to find a grid whose associated graph will be isomorphic to the given graph. In case no such grid exists, print -1.
Two graphs are Isomorphic if one can be graph means a graph same in structure, and we can obtain the same graph just by renumbering the vertices of one graph.
- A valid grid exist if any only if the given graph is a tree.
- For any tree, We can make a grid of the following type.
For a graph with N = 3 and edges 1-2 and 1-3, one possible answer is
First of all, try to make a grid for which the associated Graph is cyclic. You will notice, that due to all 8 directions being considered adjacent, we cannot make the graph cyclic.
Consider the following grid.
Had the adjacent sides being considered, this would have resulted in a cyclic graph, but, since we have all 8 sides adjacent, both zeroes will be connected as well as both ones will be connected, resulting in a graph with two vertices connected with each other.
Also, the graph will be connected, as for any position, if the adjacent position has the same value, it will be merged, otherwise they will be connected by an edge, resulting in a connected graph. Also, the edges will be undirected.
A connected acyclic undirected graph is also called Tree.
Hence, if the input graph is not a tree, we can immediately report the answer as impossible.
Now, Let’s move toward construction of the grid for a given tree.
Since multiple solutions exist, being a constructive problem, I’ll be sharing the intended construction. Other constructions may exist, and please share, if you used any other construction.
Let’s define the construction respectively. Each node is assigned the bit which is the parity of its depth in the tree. I’ll explain the reason at the end.
Suppose, for every node, we define a valid grid for the subtree rooted at that node.
For a node u, each of its children has grid g1, g2, g3 … gk where node u has k children.
It is guaranteed, that parity of d[u] is always opposite to parity of any of its children. Hence, assume bit assigned to the current node is 0.
Make a row of a bit of current node, and in next row, make the graph as
0 g1 0 g2 0 g3 0 … gk 0
“current bit, grid for first child, current bit, the grid for second child, current bit, grid for third child followed by current bit.” and so on.
That is, the First row is fully filled with the bit assigned to the current node and in the second row, Surround each grid associated with each child by current bit in the second row.
For example, consider tree with N = 3 with edges 1-2 and 1-3. Following grid is generated by this construction.
0 0 0 0 0
0 1 0 1 0
Consider another tree with N = 3 with edges 1-2 and 2-3. Following the grid is generated.
0 0 0 0 0
0 1 1 1 0
0 1 0 1 0
See, we can always make the grid in a similar fashion.
The reason of assigning d[u]%2 as the bit to the current node is that each pair of connected vertices should have opposite bit at their corresponding positions in grid, which implies, no two adjacent nodes in tree can have same bit and depth of each pair of adjacent node differ in parity.
Number of cells in this grid
We can see, that we add a row for each depth level. Turns out this is the maximum number of rows needed by this method. The number of rows generated in the grid is actually the max depth of any node in the tree.
About Number of columns, we can see, that Number of columns will always be 2*N+1. The proof is left as an exercise.
So, in the worst case with a linear chain given, we will have N*(2*N+1) which is 20100 in the worst case for N = 100, far below 10^5.
Time complexity is O(N^2) per test case, O(N) for DFS, but O(depth*N) time for construction.
Feel free to Share your approach, If it differs. Suggestions are always welcomed.