Project Links Logo Artwork
Graph Theory: Industrial Drilling
Home > Graph Theory: Industrial Drilling > Solving the Drilling Problem > Modeling it as a Graph Theory Problem
Crib Sheet
Library
Help
Map
Problem List
Module Home
Links Home


conceptsdiscoverapplycollaboratepractice
 
 
go backgo forward
go backgo forward

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 .

The largest independent set.

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 ?

 
 
go backgo forward
go backgo forward