Graph coloring using adjacency matrix — Discrete Math Problem
This problem was one of the machine problems in our subject Discrete Mathematics 2 during my 2nd-year Computer Science journey at Adamson University-Manila.
“ Given an input.txt file that contains the adjacency matrix representation of a graph, output the colors of each vertex where no two adjacent vertices should have the same color. You are free to use any sequence of colors. ”
What is Graph Coloring?
Graph coloring problem is just one in a large class of intractable problems called NP-complete problems, all of which take at least exponential time to solve. In practice are solved using algorithms that yield an approximate solution (for instance, one that is suboptimal) in a reasonable time. Such an algorithm is called a heuristic. For the graph coloring problem, the following heuristic produces a legal, though not necessarily optimal, coloring.
Each vertex must have a different color from the adjacent vertices that are connected. If {a, b} ∈ V, then a and b or the adjacent vertex to V are different colors. The coloring must be the minimal or optimal solution. The smallest number or optimal coloring number needed in the graph is called the chromatic number.
Example 1:
The chromatic number is 4.
Example 2:
The chromatic number is 2.
What is Undirected Graph G(V, E)?
An undirected graph is a graph in which edges are represented by an unordered pair (i, j) for and vertices i and j in V.
G = a graph
E = edge in G
V = vertex in G
In an undirected graph:
- (i, j) and (j, i) are the same edge or in short, symmetric.
- No self-loops in each element
- The vertices i and j be distinct
What is Adjacency Matrix?
The Adjacency matrix is a simple and straightforward way of representing a graph G= (V, E) on n = |V| vertices, labeled 1, 2, …., n, is by using an n by n matrix.
Elements of an undirected graph are defined by:
Example:
Graph Coloring Algorithm
- Find all the symmetric edges in one representation of (i, j) and (j, i).
- Give each vertex one color for initialization.
- For coloring, visit each vertex and check each adjacent vertice connected on that vertex if the color is the same as the current vertex and adjacent vertex. If the colors are the same, then change the color.
The script generates the solution, <name>.txt:
