  We examine a search on a graph among a number of different kinds of objects
(vertices), one of which we want to find. In a standard graph search, all of
the vertices are the same, except for one, the marked vertex, and that is the
one we wish to find. We examine the case in which the unmarked vertices can be
of different types, so the background against which the search is done is not
uniform. We find that the search can still be successful, but the probability
of success is lower than in the uniform background case, and that probability
decreases with the number of types of unmarked vertices. We also show how the
graph searches can be rephrased as equivalent oracle problems.
