Given the graphs in Figure, separate them into isomorphic groups.

Given the graph in Figure. Find the maximum DFS code for the graph, subject to the constraint that all extensions (whether forward or backward) are done only from the right most path.

For an edge labeled undirected graph G = (V,E), define its labeled adjacency matrix A as follows:

where L(vi)is the label for vertex vi and L(vi, vj) is the label for edge (vi, vj). In other words, the labeled adjacency matrix has the node labels on the main diagonal, and it has the label of the edge (vi, vj) in cell A(i, j). Finally, a 0 in cell A(i, j) means that there is no edge between vi and v_j.

Given a particular permutation of the vertices, a matrix code for the graph is obtained by concatenating the lower triangular submatrix of A row-by-row. For

example, one possible matrix corresponding to the default vertex permutation v₀v₁v₂v₃v₄v₅ for the graph in Figure is given as

The code for the matrix above is axb0yb0yyb00yyb0000za. Given the total ordering on the labels

0

find the maximum matrix code for the graph in Figure. That is, among all possible vertex permutations and the corresponding matrix codes, you have to choose the lexicographically largest code.