Such physical matters were nice, yet, to him, intelligence and passion born of living, the ability to move and be moved by subtleties of the mind and spirit, were what really counted.

# # 图的连通分量

$\sum_{u\in A}\frac{1}{n_u}=\sum_{u\in A}\frac{1}{|A|}=1$

$\sum_{u\in V}\frac{1}{n_u}=\sum_{A\subseteq V}\sum_{u\in A}\frac{1}{n_u}=\sum_{A\subseteq V}1=c$

\begin{aligned} &\widehat{n_u}=\min(n_u,\frac{2}{\varepsilon})\\ &\widehat{c}=\sum_{u\in V}\frac{1}{\widehat{n_u}} \end{aligned}

• $n_u<\frac{2}{\varepsilon}$，则$\widehat{n_u}=n_u$，误差为 0。

• 否则，就有：

$0<\frac{1}{n_u}\leq\frac{\varepsilon}{2}=\frac{1}{\widehat{n_u}}$

$\frac{1}{n_u}$$\frac{1}{\widehat{n_u}}$ 都在$(0,\frac{\varepsilon}{2}]$ 中，误差也不会超过这个上限。$\square$.

$\tilde{c}=n\cdot\left (\frac{1}{r}\sum_{i=1}^r\frac{1}{\widehat{n_{u_i}}}\right )$

Theorem(Chernoff Bound)：令$\delta\in[0,1]$。若$X_1,..,X_r$$[0,1]$ 上的独立同分布的随机变量，令$\mathbb{E}[X_1]=...=\mathbb{E}[X_r]=p$$S=\frac{1}{r}\sum_{i=1}^rX_i$，那么：

$\text{Pr}[|S-p|\geq\delta p]\leq e^{-\Omega(rp\delta^2)}$

$p=\mathbb{E}[X_i]=\sum_{u\in V}\frac{1}{n}\cdot\frac{1}{\widehat{n_u}}=\frac{\widehat{c}}{n}$

$\delta=\frac{\varepsilon}{2}$$S=\frac{1}{r}\sum_{i=1}^r\frac{1}{\widehat{n_{u_i}}}$$\tilde{c}=n\cdot S$。因为$\frac{\varepsilon}{2}\leq\frac{1}{\widehat{n_u}}\leq 1$，所以：

$\frac{\varepsilon n}{2}\leq\widehat{c}\leq n\Rightarrow \frac{\varepsilon}{2}\leq\frac{\widehat{c}}{n}=0\leq 1$

\begin{aligned} \text{Pr}\left [ |\tilde{c}-\widehat{c}|\geq \frac{\varepsilon\widehat{c}}{2}\right ] &=\text{Pr}\left [ \left |\frac{\tilde{c}}{n}-\frac{\widehat{c}}{n}\right |\geq \frac{\varepsilon\widehat{c}}{2n}\right ]\\ &=\text{Pr}\left [ \left |\frac{\tilde{c}}{n}-\frac{\widehat{c}}{n}\right |\geq \delta p\right ]\\ &\leq \text{exp}\left ( -\Omega\left(\frac{b}{\varepsilon^3}p\delta^2\right)\right )\\ &=\text{exp}\left(-\Omega\left(\frac{b}{\varepsilon^3}\cdot\frac{\widehat{c}}{n}\cdot\left(\frac{\varepsilon}{2}\right)^2\right)\right)\\ &\leq\text{exp}\left(-\Omega\left(\frac{b}{\varepsilon^3}\cdot\frac{\varepsilon}{2}\cdot\left(\frac{\varepsilon}{2}\right)^2\right)\right)\\ &=\text{exp}\left(-\Omega\left(\frac{b}{8}\right)\right) \end{aligned}

\begin{aligned} |\tilde{c}-c|&\leq|\tilde{c}-\hat{c}|+|\hat{c}-c|\\ &\leq\frac{\varepsilon\hat{c}}{2}+\frac{\varepsilon n}{2}\\ &\leq \varepsilon n \end{aligned}

$G=(V,E)$ 是一个图，它的顶点中最大的度数为$d$。令$\varepsilon,\beta\in(0,1)$ 是参数。令$C(G)$ 表示$G$ 的连通分量个数，那么存在一个随机算法可以以$1-\beta$ 的概率输出一个$\widehat{C}(G)$ 满足：

$C(G)-\varepsilon|V|\leq\widehat{C}(G)\leq C(G)+\varepsilon|V|$