# 2020-04-24 Trees & Distance I (Cont.)

###### tags: `圖論`

[複習](https://hackmd.io/NDx_b8BxSyOIfg6sokUXXQ?both#P12)

[video](https://www.youtube.com/watch?v=HPABA5pL4Yo&list=PL8xY3250v6CSrLIsKMFLyrCfWonR1STtt&index=7)

## P.14 Theorem 2.1.13
* center: the set of nodes $v$ such that $\epsilon(v)=rad(G)$
* The center of a tree is a vertex or an edge
:::info
<font color=#000000>

$proof$:

By **Strong Induction**:
* Basic: $n(T)≤2$, the center is the entire tree.
* Induction step $n(T)>2$
$T': T \setminus \{leaves ~ of ~ T\}$
$\Rightarrow \epsilon_{T'}(u)=\epsilon_{T}(u)-1 ~~\forall u \in T'$
(把$T$的$leaf$全部砍掉就代表所有點的eccentricity都減1，也就代表center不變，然後不斷重複直到base case)
(砍掉leaf之後，依照induction，剩下的tree其center還是vertex或edge，不過center砍掉leaf之後不會變，$Q.E.D.$)
</font>
:::

## P.15 - P.18 Wiener index & $Theorem ~ 2.1.14$

* $Define$: Wiener index of $G$: $D(G)=\sum_{u,v\in V(G)}d_G(u,v)(distance)$
* Theorem : D(T) is minimized by stars and maximized by paths

:::info
<font color=#000000>

$proof$:

### Minimum(star):

在所有pair of vertices中，長度為1: $n-1$個
剩下的pair長度至少為2

就算假設他不是star，但是任一點到其他點的距離是2的話(neighbor除外)，代表有一個點是所有點的common neighbor ，那還是個star
$D(K_{1, n-1}) = (n-1) + 2C^{n-1}_2 = (n-1)^2$

(距離1$\times$取1條的取法數$+$距離2$\times$取2條的取法數)

### Maximum(path):

Basic: $n=1$, only one vertex $P_1$
Induction step:
$D(T) = D(T-u) + \sum_{v\in V(T)}d(u,v)$
$D(T-u)≤D(P_{n-1})$ by hypothesis
因為$D(T-u)==D(P_{n-1}) \iff T-u\text{ is a path}$
而要maximize $\sum_{v\in V(T)}d(u,v)$，則$u$必須是endpoint
所以$T$是path

endpoint $u$到其他點的距離：$\sum_{i=0}^{n-1}i$
$D(P_n) = D(P_{n-1}) + \sum_{i=0}^{n-1}i$

</font>
:::

## P.19

* $Lemma ~ 2.1.15$
If $H$ is a subgraph of $G$, then $d_G(u,v)\leq d_H(u,v)$

::: info
<font color=#000000>

$proof$:

$u,v-path$ in $H$ appears in $G$, but $u,v-path$ in G doesn't really appear in $H$.
(原本的路被拆了，所以只能繞路)

</font>
:::

* $Corollary ~ 2.1.16$
If $G$ is a connected $n$-vertex graph, then $D(G)\leq D(P_n)$

:::info
<font color=#000000>

$proof:$

by $Lemma ~ 2.1.15$
by [$Theorem ~ 2.1.14$](#P15---P18-Wiener-index-amp-Theorem--2114)

$D(G) \leq D(T) \leq D(P_n)$

</font>
:::

## P.20 P.21 Prüfer Code

* $Algorithm ~ 2.2.1$




## P.24 $Theorem ~ 2.2.3.$

Given Vertex set of size $n$, number of distinct tree is $n^{n-2}$

$proof:$

Prüfer code 種類數：從$n$種點選出$n-2$個排列，種類可重複