Question

A company manufactures 10 chemicals x 1 , x 2 , x 3 , . . . . x 10 . Certain pairs of these chemicals are incompatible and would cause explosions if brought into contact with each other. Below graph shows the incompatibility of the chemicals, each vertex represents the chemical and each edge between a pair of chemicals represents that those two chemicals are incompatible. As a precautionary measure the company wishes to partition its warehouse into compartments, and store incompatible chemicals in different compartments. What is the least number of compartments into which the warehouse should be partitioned?

Answer 1

Given :   A company manufactures 10 chemicals x₁ , x₂, x₃ , . . . . x₁₀ .

Certain pairs of these chemicals are incompatible and would cause explosions if brought into contact with each other

To Find : the least number of compartments into which the warehouse should be partitioned

Solution:

x₄  and x₅  can not be stored  with x₁  

now x₇  can not be stored with x₄    and  x₈ can not be stored with x₅

also  x₇ and x₈ can not be stored  together

so if x₄  and x₅  are stored together in different  compartment from x₁

Then  x₇ and x₈ can not be stored in x₄  , x₅    compartment

and  x₇ and x₈ both can not be stored together with  x₁  

Hence atleast 3    compartments

or if x₄ and x₅ stored seperately then also three ware house

as x₁       x₄     x₅   so atleast 3  compartments

so one of  possible arrangement  in 3 compartments:

(x₁ ,  x₂ , x₇ , x₉ )  , (x₂ , x₄ , x₈ , x₁₀) ,  ( x₃ , x₅ , x₇)

least number of compartments are  3