随机算法 (Spring 2014)/Problem Set 4: Difference between revisions
Jump to navigation
Jump to search
imported>Etone (Created page with "== Problem 1 == A proper <math>q</math>-coloring of a graph <math>G(V,E)</math> is a mapping <math>f:V\to [q]</math> such that for any edge <math>uv\in E</math> we have <math>f(u…") |
imported>Etone |
||
Line 1: | Line 1: | ||
== Problem 1 == | == Problem 1 == | ||
A proper <math>q</math>-coloring of a graph <math>G(V,E)</math> is a mapping <math>f:V\to [q]</math> such that for any edge <math>uv\in E</math> we have <math>f(u)\neq f(v)</math>. | A proper <math>q</math>-coloring of a graph <math>G(V,E)</math> is a mapping <math>f:V\to [q]</math> such that for any edge <math>uv\in E</math> we have <math>f(u)\neq f(v)</math>. | ||
Consider the Markov chain of graph | |||
Consider the following Markov chain for proper <math>q</math>-colorings of a graph <math>G(V,E)</math>: | |||
{{Theorem|Markov Chain for Graph Coloring| | {{Theorem|Markov Chain for Graph Coloring| | ||
:Start with a proper coloring of <math>G(V,E)</math>. At each step: | :Start with a proper coloring of <math>G(V,E)</math>. At each step: |
Revision as of 07:38, 2 June 2014
Problem 1
A proper [math]\displaystyle{ q }[/math]-coloring of a graph [math]\displaystyle{ G(V,E) }[/math] is a mapping [math]\displaystyle{ f:V\to [q] }[/math] such that for any edge [math]\displaystyle{ uv\in E }[/math] we have [math]\displaystyle{ f(u)\neq f(v) }[/math].
Consider the following Markov chain for proper [math]\displaystyle{ q }[/math]-colorings of a graph [math]\displaystyle{ G(V,E) }[/math]:
Markov Chain for Graph Coloring - Start with a proper coloring of [math]\displaystyle{ G(V,E) }[/math]. At each step:
- Pick a vertex [math]\displaystyle{ v\in V }[/math] and a color [math]\displaystyle{ c\in[q] }[/math] uniformly at random.
- Change the color of [math]\displaystyle{ v }[/math] to [math]\displaystyle{ c }[/math] if the resulting coloring is proper; do nothing if otherwise.
Show that the Markov chain is:
- aperiodic;
- irreducible if [math]\displaystyle{ q\ge \Delta+2 }[/math];
- with uniform stationary distribution.