Answer to Question #269051 in Discrete Mathematics for thuy

Question

Determine the minimum number of separate racks needed to store the chemicals given in the table

(1st column) by considering their incompatibility u

sing graph coloring technique. Clearly state you

steps and graphs used.

Chemical: Incompatible with

Ammonia (anhydrous): Mercury, chlorine, calcium hypochlorite, iodine, bromine,

hydrofluoric acid (anhydrous)

Chlorine: Ammonia, acetylene, butadiene, butane, methane, propane,

hydrogen, sodium carbide, benzene, finely divided metals,

turpentine

Iodine: Acetylene, ammonia (aqueous or anhydrous), hydrogen

Silver: Acetylene, oxalic acid, tartaric acid, ammonium compounds,

pulmonic acid

Iodine: Acetylene, ammonia (aqueous or anhydrous), hydrogen

Mercury: Acetylene, pulmonic acid, ammonia

Fluorine: All other chemicals

Answer 1

Step 1. We assign chemical 1 (Ammonia), the first vertex and the first color (blue).

Step 2. Now we analyze the compatibility with chemical 2 (Chlorine). We note that they are incompatible, therefore, chemical 2 must be placed in another rack (placed at vertex 2, red color).

Step 3. We evaluate the compatibility of chemical 3 (Iodine) with chemical 1 (Ammonia), and we see that they are incompatible. Now we analyze the compatibility of chemical 3 (iodine), with chemical 2 (chlorine), and we see that both are compatible, therefore, they can be placed in the same rack (chemical 3 is placed, at vertex 2, color Red).

Step 4. We evaluate the compatibility of chemical 4 (Silver), with chemical 1 (Ammonia), we see that both are compatible, therefore, they can be placed in the same rack (chemical 4 is placed, at vertex 1, color blue).

Note: Note that Silver is also compatible with Chlorine and Iodine, therefore, it can also be located at vertex 2 (red color), without affecting the result.

Step 5. We evaluate the compatibility of chemical 5 (Iodine). In this case, we noticed that we had previously labeled this chemical (chemical 3), and it was placed in vertex 2, red.

Step 6. We evaluate the compatibility of the chemical 6 (Mercury), We check that it is incompatible with the chemical 1 (Ammonia), but it is compatible with the chemicals located in vertex 2, therefore, it is placed in the vertex 2, red color.

Step 7. We evaluate the compatibility of chemical 7 (Fluorine), we see that it is incompatible with all other chemicals, therefore, we place it in a new vertex: vertex 3, green color.

In this way we get the answer: a minimum of 3 separate racks to store the chemicals are needed. This is the minimum number of colors, that are needed to color the vertices of the graph, and is known as a chromatic number.