Discrete Math Notes

# SUBGRAPHS

• There is a problem whose name is Instant Insanity (in course book, p.524, example 11.7).
• Testing bipartiteness by BFS Coloring Algorithm:

1. Choose a vertex s and color it red 2. Color neighbors of s blue 3. Color neighbors of these nodes red 4. … and so on until all nodes are colored 5. There is a valid coloring if the graph is bipartite, otherwise not.

In wikipedia [http://en.wikipedia.org/wiki/Instant_Insanity] :

This problem has a graph-theoretic solution in which a graph with four vertices labeled B, G, R, W (for blue, green, red, and white) can be used to represent each cube; there is an edge between two vertices if the two colors are on the opposite sides of the cube, and a loop at a vertex if the opposite sides have the same color. Trial and error is a slow way to solve this problem, as there are 41,472 arrangements of the four cubes only two of which are solutions.

And this can be interesting about algorithms :

A generalized version of the puzzle with more than four cubes is NP-complete.

# ISOMORPHISM

• However, there is no simple, foolproof method — especially when we are confronted with larger graphs about two graphs are isomorphic or not.

# QUESTIONS

• What is the mathematical definition of a directed multigraph? Give an example involving 4 vertices and 5 edges (not a drawing!)
page revision: 4, last edited: 25 Sep 2008 14:08