Home /
Expert Answers /
Computer Science /
problem-11-2-consider-the-following-problem-called-connections-input-a-set-x-of-m-elements-a-col-pa275
(Solved): Problem 11.2: Consider the following problem called Connections: Input: a set x of M elements, a col ...
Problem 11.2: Consider the following problem called Connections:
Input: a set x of M elements, a collection of N subsets Y_(1),dots,Y_(N)subex, and
numbers A and B with AB=M.
Output: true iff there exists a partition of x into A disjoint subsets Z_(1),dots,Z_(A)
each of size exactly B, such that for each iin{1,dots,A}, the subset Z_(i) is contained
in Y_(j_(i)) for some j_(i)in{1,dots,N}j_(i) 's need not be distinctx={1,2,3,4,5,6,7,8,9}, subsets {1,4,7,8},{2,3,5,7,9},{2,5,7,8},
{1,2,5,6,7}, and A=B=3{1,4,8},{3,5,9},
{2,6,7} Y_(i) corresponds to a potential category, and
we want to form A groups of B words, such that each group fits in a common category; in
the game, A=B=4 and M=16, but the subset(s)/(c)ategories are not given explicitly...A groups...G=(V,E) and a number K, and the output is true iff there exists a subset SsubeV of
K vertices such that each edge uvinE has uinS or vinS.
Hint: let the elements of x correspond to the edges of the given graph; also add some
number of extra "dummy" elements. For each vertex v, create a subset containing all
edges incident to v together with all the dummy elements...