graph

Problem 1: (15 points)
a. An automorphism of a graph G=(V,E) is any permutation f of V such that if (x,y) is an edge of
G, then (f(x), f(y)) is an edge in G. Write a backtracking algorithm that generates all
automorphisms of a given input graph G.
b. Let A[1:n,1:n] be a square matrix and C a given constant. A row-column selection of matrix
A is any subset of numbers such that no two numbers come from the same row or the same
column. A C-bound row-column selection is a row-column selection where the sum of its
elements is ≤ C. Write a backtracking algorithm that generates all C-bound row-column
selections of a given input matrix A[1:n,1:n], where C is a given input constant.

Leave a Reply

Your email address will not be published. Required fields are marked *