Modeling it as a Graph Theory Problem
Modeling The Drilling Problem As A Graph Theory Problem
It is clear that achieving both of our goals would require
constructing large independent sets.
It is easy to see that in our graph the largest independent
set is of size 7. This set is shown below; we will call it
.
Figure 27: The largest independent set.
The only independent set of size 7.
|
Even though we claim it is supposed to be easy, don't take our word for it.
Make sure it is really clear to you that this set
of 7 vertices is indeed the largest.
Problem
29:
Can you construct any independent sets of size 6?
Problem
30:
Are there any independent sets of size 6 that are disjoint from
?
|