This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | Next revision Both sides next revision | ||
|
en:dydaktyka:csp:lab1 [2017/07/17 10:08] 127.0.0.1 external edit |
en:dydaktyka:csp:lab1 [2018/03/11 20:09] msl [Graph Coloring] |
||
|---|---|---|---|
| Line 48: | Line 48: | ||
| ==== Graph Coloring ==== | ==== Graph Coloring ==== | ||
| - | * Definition: assign colors the vertices in a graph in the way that no adjacent vertices have the same colors. In case of the planar graph you will require only four colors (why? there is a very famous [[http://en.wikipedia.org/wiki/Four_color_theorem|proof of this fact]]). Otherwise you can require even as many colors as there are vertices. More on the [[http://en.wikipedia.org/wiki/Graph_coloring#Vertex_coloring|wikipedia page]]. | + | * Definition: assign colors to the vertices in a graph in the way that no adjacent vertices have the same color. In case of the planar graph you will require only four colors (why? there is a very famous [[http://en.wikipedia.org/wiki/Four_color_theorem|proof of this fact]]). Otherwise you may need even as many colors as there are vertices. More on the [[http://en.wikipedia.org/wiki/Graph_coloring#Vertex_coloring|wikipedia page]]. |
| * Assign: | * Assign: | ||
| - Fill missing elements in the model shown below ({{:en:dydaktyka:csp:csp_coloring_data.dzn.zip|example data files}}): | - Fill missing elements in the model shown below ({{:en:dydaktyka:csp:csp_coloring_data.dzn.zip|example data files}}): | ||
