Answer Happy

After you distributed the tools to your
developers, you are faced with a new problem
SKILL[1]. You are tasked with
allocating your developers to cities across the country. Each city
can have only one developer. Furthermore, a city can either be
directly adjacent to another city or non-adjacent. Each developer
possesses exactly one of three different possible skills
S1, S2, and
S3. Your goal to allocate
n developers to n cities
such that no city has a developer with the same skill as another
developer in an adjacent city (assume that, for each skill
Si, you have as many as n developers
possessing that skill). For example, suppose you want to allocate
developers to cities K1,
K2, K3, and
K4 where:
K1 is adjacent to
K2
K2 is adjacent to
K3
K1 is adjacent to
K4
K4 is adjacent to
K3
Then one solution is to have a
developer with skill S1 go to city
K1, developer with skill S2
go to K2, developer with skill
S3 go to K3, and developer
with skill S2 go to K4.
That way, each city has a developer with a skill different than the
skills of developers in adjacent cities. Notice that, if all cities
were adjacent to each other then there is no solution.
Prove that SKILL is
NP-complete by answering the following (note that
you need to do so with respect to ANY arbitrary number of
n cities with any number of adjacent connections):
[1] At this point you start to wonder
why is it that you are getting all these hard problems.
Prove
that SKILL is NP-complete
by answering the following (note that you need to do so with
respect to ANY arbitrary number of n cities with
any number of adjacent connections):
[1] At this point you start to wonder why is it that you are
getting all these hard problems.