概率论 (Summer 2013)/Problem Set 3: Difference between revisions
Jump to navigation
Jump to search
imported>Zhangchihao (Created page with "== Problem 1 == A set of vertices <math>D\subseteq V</math> of graph <math>G(V,E)</math> is a <i>dominating set</i> if for every <math>v\in V</math>, either <math>v\in D</math> …") |
imported>Zhangchihao |
||
| Line 1: | Line 1: | ||
== Problem 1 == | == Problem 1 == | ||
A set of vertices <math>D\subseteq V</math> of graph <math>G(V,E)</math> is a <i>dominating set</i> if for every <math>v\in V</math>, either <math>v\in D</math> or <math> | A set of vertices <math>D\subseteq V</math> of graph <math>G(V,E)</math> is a <i>dominating set</i> if for every <math>v\in V</math>, either <math>v\in D</math> or one of its neighbour is in <math>D</math>. The problem of computing minimum dominating set is NP-hard. Prove that for every <math>d</math>-regular graph with <math>n</math> vertices, there exists a dominating set with size at most <math>\frac{n(1+\ln(d+1))}{d+1}</math>. | ||
== Problem 2 == | == Problem 2 == | ||
Revision as of 07:39, 18 July 2013
Problem 1
A set of vertices [math]\displaystyle{ D\subseteq V }[/math] of graph [math]\displaystyle{ G(V,E) }[/math] is a dominating set if for every [math]\displaystyle{ v\in V }[/math], either [math]\displaystyle{ v\in D }[/math] or one of its neighbour is in [math]\displaystyle{ D }[/math]. The problem of computing minimum dominating set is NP-hard. Prove that for every [math]\displaystyle{ d }[/math]-regular graph with [math]\displaystyle{ n }[/math] vertices, there exists a dominating set with size at most [math]\displaystyle{ \frac{n(1+\ln(d+1))}{d+1} }[/math].