随机算法 (Fall 2011)/Electrical Network: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>Zhangchihao
Created page with "An undirected graph <math>G=(V,E)</math> is called an '''electrical network''', if # Every edge <math>e=\{u,v\}</math> is associated with resistance <math>R_{uv}</math>. # The f…"
 
imported>Zhangchihao
mNo edit summary
 
(One intermediate revision by the same user not shown)
Line 5: Line 5:
In the following, we use <math>C_{uv}</math> to denote the current flow from <math>u</math> to <math>v</math>, <math>V_u</math> to denote the voltage at vertex <math>u</math>, <math>\phi_{uv}</math> to denote the difference of voltage between <math>u</math> and <math>v</math>, i.e. <math>\phi_{uv}=V_u-V_v</math>.
In the following, we use <math>C_{uv}</math> to denote the current flow from <math>u</math> to <math>v</math>, <math>V_u</math> to denote the voltage at vertex <math>u</math>, <math>\phi_{uv}</math> to denote the difference of voltage between <math>u</math> and <math>v</math>, i.e. <math>\phi_{uv}=V_u-V_v</math>.


* '''Kirchhoff's Law:''' for every vertex <math>v</math>, the sum of currents entering <math>v</math> is equal to the the sum of currents leaving <math>v</math>.
* '''Kirchhoff's Law:''' For every vertex <math>v</math>, the sum of currents entering <math>v</math> is equal to the the sum of currents leaving <math>v</math>.
* ''' Ohm's Law:''' for every edge <math>e=\{u,v\}</math> in the graph, the currents across <math>e</math> is equal to the difference of voltage between <math>u</math> and <math>v</math> over the resistance of <math>e</math>, i.e. <math>C_{uv}=\frac{\phi_{uv}}{R_{uv}}</math>.
* ''' Ohm's Law:''' For every edge <math>e=\{u,v\}</math> in the graph, the currents across <math>e</math> is equal to the difference of voltage between <math>u</math> and <math>v</math> over the resistance of <math>e</math>, i.e. <math>C_{uv}=\frac{\phi_{uv}}{R_{uv}}</math>.


{{Theorem
{{Theorem
Line 13: Line 13:
}}
}}


Now we use the idea of electrical network to analyse the cover time of random walk. Consider an undirected graph <math>G=(V,E)</math>, we construct an electrical network whose underlying graph is <math>G</math> and <math>R_e=1</math> for every <math>e\in E</math>. If we inject <math>d(w)</math> units of currents into each vertex <math>w\in V</math> and remove all the <math>2|E|</math> units of currents from <math>v</math>, where <math>d_w</math> is the degree of <math>w</math> in <math>G</math>, then  
Now we use the idea of electrical network to analyze the cover time of random walk. Consider an undirected graph <math>G=(V,E)</math>, we construct an electrical network whose underlying graph is <math>G</math> and <math>R_e=1</math> for every <math>e\in E</math>. If we inject <math>d(w)</math> units of currents into each vertex <math>w\in V</math> and remove all the <math>2|E|</math> units of currents from <math>v</math>, where <math>d(w)</math> is the degree of <math>w</math> in <math>G</math>, then  


{{Theorem
{{Theorem
Line 21: Line 21:
   \phi_{uv}=H_{uv}
   \phi_{uv}=H_{uv}
</math>
</math>
:where <math>\phi_{uv}</math> is the difference of voltage between <math>u</math> and <math>v</math>.
}}
}}


Line 28: Line 27:
:<math>
:<math>
   \begin{align}
   \begin{align}
     H_{uv}&=\sum_{xu\in E}\frac{1}{d_u}(1+H_{xv})\\
     H_{uv}&=\sum_{\{x,u\}\in E}\frac{1}{d(u)}(1+H_{xv})\\
         &=1+\frac{1}{d_u}\sum_{xu\in E}H_{xv} \qquad(*)
         &=1+\frac{1}{d(u)}\sum_{\{x,u\}\in E}H_{xv} \qquad(*)
   \end{align}
   \end{align}
   </math>
   </math>
Line 46: Line 45:
Thus
Thus
:<math>
:<math>
   \phi_{uv}=1+\frac{1}{d_u}\sum_{\{u,x\}\in E}\phi_{xv} \qquad(**)
   \phi_{uv}=1+\frac{1}{d(u)}\sum_{\{u,x\}\in E}\phi_{xv} \qquad(**)
</math>
</math>


Line 69: Line 68:
Now we change the direction of all the currents in <math>B</math>, that is, <math>2|E|</math> units of currents are injected into <math>u</math> and <math>d(w)</math> units of currents are removed from every vertex <math>w</math>. In this electrical network <math>C</math>, <math>H_{vu}=\phi_{uv}^C</math>.
Now we change the direction of all the currents in <math>B</math>, that is, <math>2|E|</math> units of currents are injected into <math>u</math> and <math>d(w)</math> units of currents are removed from every vertex <math>w</math>. In this electrical network <math>C</math>, <math>H_{vu}=\phi_{uv}^C</math>.


Since electrical networks are linear system, we can super-pose <math>A</math> and <math>C</math> (summing up the voltage and currents on corresponding vertices and edges) and let the resulting electrical network be <math>D</math>. Then <math>D</math> is the electrical network such that <math>2|E|</math> units of currents are injected into <math>u</math> and <math>2|E|</math> units of currents are removed form <math>v</math>. Furthermore, <math>H_{uv}+H_{vu}=\phi_{uv}^D</math> and thus by Ohm's law, <math>H_{uv}+H_{vu}=2|E|\cdot R(u,v)</math>.
Since electrical networks are linear system, we can super-pose <math>A</math> and <math>C</math> (summing up the voltage and currents on corresponding vertices and edges) and let the resulting electrical network be <math>D</math>. Then <math>D</math> is an electrical network such that <math>2|E|</math> units of currents are injected into <math>u</math> and <math>2|E|</math> units of currents are removed form <math>v</math>. Furthermore, <math>H_{uv}+H_{vu}=\phi_{uv}^D</math> and thus by Ohm's law, <math>H_{uv}+H_{vu}=2|E|\cdot R(u,v)</math>.
}}
}}


Armed with this theorem, we can now give a better estimation of the cover time of random walk. Let <math>T</math> be a spanning tree of <math>G</math>, and <math>u=v_{1}\to v_{2}\to\ldots\to v_{2n}=u</math> be an Euler tour of <math>T</math>, then
Armed with this theorem, we can now give a better estimation of the cover time of random walk. Let <math>T</math> be a spanning tree of <math>G</math>, and <math>u=v_{1}\to v_{2}\to\ldots\to v_{2n}=u</math> be an Euler tour of <math>T</math>, then
:<math>
:<math>
C_u\le \sum_{i=1}^{2n}H_{v_i v_{i+1}}=\sum_{\{u,v\}\in T}(H_{uv}+H_{vu})\le 2mn
C_u\le \sum_{i=1}^{2n-1}H_{v_i v_{i+1}}=\sum_{\{u,v\}\in T}(H_{uv}+H_{vu})\le 2mn
</math>
</math>

Latest revision as of 14:03, 24 December 2011

An undirected graph [math]\displaystyle{ G=(V,E) }[/math] is called an electrical network, if

  1. Every edge [math]\displaystyle{ e=\{u,v\} }[/math] is associated with resistance [math]\displaystyle{ R_{uv} }[/math].
  2. The flow of current and the voltage at each vertex in the network follows Kirchhoff's Law and Ohm's Law.

In the following, we use [math]\displaystyle{ C_{uv} }[/math] to denote the current flow from [math]\displaystyle{ u }[/math] to [math]\displaystyle{ v }[/math], [math]\displaystyle{ V_u }[/math] to denote the voltage at vertex [math]\displaystyle{ u }[/math], [math]\displaystyle{ \phi_{uv} }[/math] to denote the difference of voltage between [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math], i.e. [math]\displaystyle{ \phi_{uv}=V_u-V_v }[/math].

  • Kirchhoff's Law: For every vertex [math]\displaystyle{ v }[/math], the sum of currents entering [math]\displaystyle{ v }[/math] is equal to the the sum of currents leaving [math]\displaystyle{ v }[/math].
  • Ohm's Law: For every edge [math]\displaystyle{ e=\{u,v\} }[/math] in the graph, the currents across [math]\displaystyle{ e }[/math] is equal to the difference of voltage between [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] over the resistance of [math]\displaystyle{ e }[/math], i.e. [math]\displaystyle{ C_{uv}=\frac{\phi_{uv}}{R_{uv}} }[/math].
Definition (Effective Resistance)
Let [math]\displaystyle{ u,v\in V }[/math], the effective resistance [math]\displaystyle{ R(u,v) }[/math] between [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] is defined to be the voltage difference between [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] while one unit current is injected into [math]\displaystyle{ u }[/math] and removed from [math]\displaystyle{ v }[/math].

Now we use the idea of electrical network to analyze the cover time of random walk. Consider an undirected graph [math]\displaystyle{ G=(V,E) }[/math], we construct an electrical network whose underlying graph is [math]\displaystyle{ G }[/math] and [math]\displaystyle{ R_e=1 }[/math] for every [math]\displaystyle{ e\in E }[/math]. If we inject [math]\displaystyle{ d(w) }[/math] units of currents into each vertex [math]\displaystyle{ w\in V }[/math] and remove all the [math]\displaystyle{ 2|E| }[/math] units of currents from [math]\displaystyle{ v }[/math], where [math]\displaystyle{ d(w) }[/math] is the degree of [math]\displaystyle{ w }[/math] in [math]\displaystyle{ G }[/math], then

Lemma
For every [math]\displaystyle{ u,v\in V }[/math]
[math]\displaystyle{ \phi_{uv}=H_{uv} }[/math]
Proof.

We first compute [math]\displaystyle{ H_{uv} }[/math], consider one step of random walk, we have

[math]\displaystyle{ \begin{align} H_{uv}&=\sum_{\{x,u\}\in E}\frac{1}{d(u)}(1+H_{xv})\\ &=1+\frac{1}{d(u)}\sum_{\{x,u\}\in E}H_{xv} \qquad(*) \end{align} }[/math]

On the other hand,

[math]\displaystyle{ \begin{align} d(u)&=\sum_{\{u,x\}\in E}C_{ux}\\ &=\sum_{\{u,x\}\in E}\phi_{ux}\\ &=\sum_{\{u,x\}\in E}(\phi_{uv}-\phi_{xv})\\ &=d(u)\phi_{uv}-\sum_{\{u,x\}\in E}\phi_{xv} \end{align} }[/math]

The first and third equality follows from Kirchhoff's law and the second equality follows from Ohm's law.

Thus

[math]\displaystyle{ \phi_{uv}=1+\frac{1}{d(u)}\sum_{\{u,x\}\in E}\phi_{xv} \qquad(**) }[/math]

The Equation (*) and Equation (**) are both linear systems with unique solution, thus [math]\displaystyle{ H_{uv}=\phi_{uv} }[/math].

[math]\displaystyle{ \square }[/math]
Theorem (Chandra-Raghavan-Ruzzo-Smolensky-Tiwari 1989)
Let [math]\displaystyle{ u,v\in V }[/math], then
[math]\displaystyle{ H_{uv}+H_{vu}=2|E|\cdot R(u,v) }[/math]
Proof.

We now construct four electrical networks [math]\displaystyle{ A,B,C,D }[/math] with underlying graph [math]\displaystyle{ G }[/math].

First, we inject [math]\displaystyle{ d(w) }[/math] units of currents into each vertex [math]\displaystyle{ w }[/math] and remove [math]\displaystyle{ 2|E| }[/math] units of currents from [math]\displaystyle{ v }[/math]. Let [math]\displaystyle{ A }[/math] denote this electrical network, then by the above lemma, we have [math]\displaystyle{ H_{uv}=\phi_{uv}^A }[/math].

Similarly, if we inject [math]\displaystyle{ d(w) }[/math] units of currents into every vertex [math]\displaystyle{ w }[/math], remove [math]\displaystyle{ 2|E| }[/math] units of currents from [math]\displaystyle{ u }[/math] and denote this electrical network by [math]\displaystyle{ B }[/math], then [math]\displaystyle{ H_{vu}=\phi_{vu}^B }[/math].

Now we change the direction of all the currents in [math]\displaystyle{ B }[/math], that is, [math]\displaystyle{ 2|E| }[/math] units of currents are injected into [math]\displaystyle{ u }[/math] and [math]\displaystyle{ d(w) }[/math] units of currents are removed from every vertex [math]\displaystyle{ w }[/math]. In this electrical network [math]\displaystyle{ C }[/math], [math]\displaystyle{ H_{vu}=\phi_{uv}^C }[/math].

Since electrical networks are linear system, we can super-pose [math]\displaystyle{ A }[/math] and [math]\displaystyle{ C }[/math] (summing up the voltage and currents on corresponding vertices and edges) and let the resulting electrical network be [math]\displaystyle{ D }[/math]. Then [math]\displaystyle{ D }[/math] is an electrical network such that [math]\displaystyle{ 2|E| }[/math] units of currents are injected into [math]\displaystyle{ u }[/math] and [math]\displaystyle{ 2|E| }[/math] units of currents are removed form [math]\displaystyle{ v }[/math]. Furthermore, [math]\displaystyle{ H_{uv}+H_{vu}=\phi_{uv}^D }[/math] and thus by Ohm's law, [math]\displaystyle{ H_{uv}+H_{vu}=2|E|\cdot R(u,v) }[/math].

[math]\displaystyle{ \square }[/math]

Armed with this theorem, we can now give a better estimation of the cover time of random walk. Let [math]\displaystyle{ T }[/math] be a spanning tree of [math]\displaystyle{ G }[/math], and [math]\displaystyle{ u=v_{1}\to v_{2}\to\ldots\to v_{2n}=u }[/math] be an Euler tour of [math]\displaystyle{ T }[/math], then

[math]\displaystyle{ C_u\le \sum_{i=1}^{2n-1}H_{v_i v_{i+1}}=\sum_{\{u,v\}\in T}(H_{uv}+H_{vu})\le 2mn }[/math]