Project Links Logo Artwork
Graph Theory: Industrial Drilling
Home > Graph Theory: Industrial Drilling > Solving the Drilling Problem > The Inside View
Crib Sheet
Library
Help
Map
Problem List
Module Home
Links Home


conceptsdiscoverapplycollaboratepractice
 
 
go backgo forward
go backgo forward

The Inside View

The "Inside View"

How far did you get?

You probably found this approach to be quite difficult.

Let's try the problem from the other "end", and see if we have more success.

Let's look at the points in the middle of the figure. It is clear that these points are "close" to one another, and therefore form a clique. The size of this clique is a lower bound for the chromatic number.

Let us try to find as large a clique as possible.

The Largest Clique

Figure 28: The Largest Clique

The 24 vertices inside the yellow-shaded area comprise a clique. This is the largest clique of the graph. Corollary: Any drilling tool that satisfies the given constraints must use at least 24 passes.



Thus, 24 is our new lower bound!

 
 
go backgo forward
go backgo forward