Struktur Diskrit : Pewarnaan Graph
Map Coloring
Determining the least number of colors that can be used to color a map so that adjacent regions never have the same color.
Graph Coloring
Maps and Dual Graphs
Each map in the plane can be represented by a graph (Dual Graph).
Vertex: Region
Edge: Region A and B have a common border. Dual Graph is planar graph
Example
Graph Coloring
The problem of coloring the regions of a maps is equivalent to the problem of coloring the vertices of the dual graph so that no two adjacent vertices in the graph have the same color. The least number of colors needed for a coloring graph is given by chromatic number which denoted by χ (G).
The Chromatic number for planar graph is not greater that 4.
Example
Exercise
What are the chromatic numbers of the graphs G and H shown below?
Application: Scheduling Final Exams
How can the final exams at UMP be scheduled so that no student has two exams at the same time? Suppose that, 7 finals to be scheduled and the following pairs of course have common students.
1&2, 1&3, 1&4, 1&7, 2&3, 2&4, 2&5, 2&7, 3&4, 3&6, 3&7, 4&5, 4&6, 5&6, 5&7, and 6&7
Example
Welsh Powell Algorithm
Step 1 : All vertices are sorted according to the decreasing value of their degree in a list V.
Step 2 : Colors are ordered in a list C.
Step 3 : The first non colored vertex v in V is colored with the first available color in C. available means a color that was not previously used by the algorithm.
Step 4 : The remaining part of the ordered list V is traversed and the same color is allocated to every vertex for which no adjacent vertex has the same color.
Step 5 : Steps 3 and 4 are applied iteratively until all the vertices have been colored.
Exercise
Color this graph by using the Welsh Powell algorithm!
Edge Coloring
An edge coloring of a graph is an assignment of colors to edges so that edges incident with a common vertex are assigned different colors. The edge chromatic number of a graph is the smallest number of colors that can be used in an edge coloring of the graph. The edge chromatic number of a graph G is denoted by c’(G).
Example
Posting Komentar