Exercise 15

A pharmaceutical manufacturer is building a new warehouse to store its supply of $10$ chemicals it uses in production. However, some of the chemicals cannot be stored in the same room due to undesirable reactions that will occur. The matrix below has a $1$ in position $(i,j)$ if and only if chemical $i$ and chemical $j$ cannot be stored in the same room. Develop an appropriate graph theoretic model and determine the smallest number of rooms into which they can divide their warehouse so that they can safely store all $10$ chemicals in the warehouse. $$\begin{bmatrix}0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0\\ 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1\\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{bmatrix}$$