Graph Coloring | Set 1 (Introduction and Applications) - GeeksforGeeks
3) Suduku: Suduku is also a variation of Graph coloring problem where every cell represents a vertex. There is an edge between two vertices if they are in same row or same column or same block.
4) Register Allocation: In compiler optimization, register allocation is the process of assigning a large number of target program variables onto a small number of CPU registers. This problem is also a graph coloring problem.
5) Bipartite Graphs: We can check if a graph is Bipartite or not by colowing the graph using two colors. If a given graph is 2-colorable, then it is Bipartite, otherwise not. See this for more details.
6) Map Coloring: Geographical maps of countries or states where no two adjacent cities cannot be assigned same color. Four colors are sufficient to color any map (See Four Color Theorem)
Read full article from Graph Coloring | Set 1 (Introduction and Applications) - GeeksforGeeks
No comments:
Post a Comment