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

Now that we have covered the fundamentals of graph theory, let us return to the drilling problem. In order to use what we have learned about graph theory, we will reformulate the problem as a graph theory problem as shown below:

Recall the pattern that was to be drilled into the workpiece by the gang drill:

The Final Product:
The Final Product

Figure 26: The Final Product

The pattern of holes that had to be drilled into the workpiece with a gang drill.



The set of 91 points on the plane is viewed as a set of vertices in a graph . There are exactly 91 vertices. Each of them corresponds to a point; different vertices correspond to different points.

The set of edges in the graph is the set of pairs of vertices whose corresponding vertices are less than 35 units apart.

Any set of points that can be drilled in one pass corresponds to vertices in that form an independent set.

The sequence of passes that would yield all points drilled corresponds to a set of independent sets that cover the whole graph. Such a set of independent sets is a vertex coloring of the graph.

Conclusion

The drilling problem is identical to the problem of coloring the graph using the smallest possible number of colors. Recall that this number is called the chromatic number of the graph.

We have two objectives:

  1. Construct a coloring of the graph; and
  2. Prove that the number of colors used is minimum.
 
 
go backgo forward
go backgo forward