Trees and Distance: Basic Properties

• 參考書籍: Introduction to Graph Theory - Second edition

樹基本定義

acyclic

• A graph with no cycle

forest

• An acyclic graph

tree

• A connected acyclic graph

leaf

• A vertex of degree 1
• 又稱作 pendant vertex

spanning subgraph

• A spanning subgraph of $G$ is a subgraph with vertex set $V(G)$.

spanning tree

• A spanning tree is a spanning subgraph that is a tree.

Lemma 2.1.3

• Every tree with at least two vertices has at least two leaves. Deleting a leaf from an $n$-vertex tree produces a tree with $n-1$ vertices.

Proof

• 設 $G$ 是一個 tree，$v$ 是 $G$ 的一個leaf，且 $G'=G-v$
• 由於 $v$ 是一個 leaf，其 degree 為1
• 且每個 tree 的 leaf 必定為其上的 path 的終點
• 移除一個 leaf 後，path 上的剩餘點仍相連
• 因此 $G'$ 是一個具有具有 $n-1$ 個 vertices 的 tree

Theorem 2.1.4

For an $n$-vertex graph $G$ (with $n\geq 1$), the following are equivalent.

• (A) $G$ is connected and no cycles.
• (B) $G$ is connected and has $n-1$ edges.
• (C) $G$ has $n-1$ edges and no cycles.
• (D) $G$ has no loops and has, for exactly one $u-v$ path.

Proof: A推到{B,C}

By induction $n=1$: trivial $n>1$: Given an acyclic connected graph $G$, $\exists$ a leaf $v$ s.t. $G'=G-v$ is also acyclic and connected. By I.H., $e(G')=n-2\Rightarrow e(G)=n-1$

Proof: B推到{A,C}

• 如果 $G$ 有 cycle 的話，就破壞 edge，直到形成 B 的性質，設為 $G'$
• 此時 $G'$ 是 acyclic $\Rightarrow G'$ 是 connected，可推得 A
• $G'$ 是 connected $\Rightarrow e(G')=n-1=e(G)$，可推得 C

Proof: C推到{A,B}

• 設 $G$ 不 connected，且 $G_1, G_2, \dots, G_k$ 是 $G$ 的 components，每個 components $G_i$ 是 connected ($i=1, 2, \dots, k$)
• 因為每個 components $G_i$ 是 connected $\Rightarrow e(G_i)=n(G_i)-1$ $\Rightarrow e(G)=\sum_i[n(G_i)-1]=n-k$
• 由於 $e(G)=n-1\Rightarrow k=1\Rightarrow G$ 是 connected，可推得 A 和 B

Proof: A推到D

• 因為 $G$ 是 connected，則每對 vertices 只會有一條 path 相連，可推得 D
• 如果每對 vertices 有兩條 paths 相連，則會形成 cycle，矛盾

Proof: D推到A

• 顯然 $G$ 是 connected
• 如果 $G$ 有 cycle $C$ 連接 $u, v\in V(G)$，則會存在兩條 $u-v$ paths，矛盾
• 因此 G 是 acyclic，可推得 A

Corollary 2.1.5

(A) Every edge of a tree is a cut-edge. (B) Adding one edge to a tree forms exactly one cycle. (C) Every connected graph contains a spanning tree.

Proof

(A) 因為 tree 沒有 cycle (B) 因為 tree 中任兩點的連接都是 unique path (C)

• 設一 connected graph $G$ 的子圖為 $H$
• 即使 $H$ 中有 cycle，則將其 cycle 破壞之後一定可以得到 connected subgraph $\hat{H}$
• 此時 $\hat{H}$ 是 connected 且沒有 cycle，故是一個樹

Proposition 2.1.6

• If $T$ and $T'$ are spanning trees of a connected graph $G$ and $e\in E(T)-E(T')$,
• then there is an edge $e'\in E(T')-E(T)$ such that $T-e+e'$ is a spanning tree of $G$.

Proof

• 設 $U, U'$ 為 $T-e$ 的兩個 components
• 因為 $T'$ 是 connected，$T'$ 的 edge $e'$ 正好連接 $U, U'$ 的兩個端點
• 故 $T-e+e'$ 是 $G$ 的 spanning tree

Proposition 2.1.7

• If $T$ and $T'$ are spanning trees of a connected graph $G$ and $e\in E(T)-E(T')$,
• then there is an edge $e'\in E(T')-E(T)$ such that $T'+e-e'$ is a spanning tree of $G$.

Proof

• $T'+e$ 形成一個 unique cycle $C$
• 由於 $T$ 是 acyclic，移除 $T'+e$ 的 edge $e'$ 將破壞 cycle $C$
• 故 $T'+e-e'$ 是 $G$ 的 spanning tree

Definitions of Trees and Graphs

Theorem 2.1.11

• If $G$ is a simple graph, then $\textrm{diam}\space G\geq3\Rightarrow\textrm{diam}\space \bar{G}\leq3$

Proof

• 當 $\textrm{diam}\space G>2$ 時，存在非相鄰點 $u, v\in V(G)$，且 $u, v$ 沒有共鄰居
• 所以任意一個 $x\in V(G)-{u,v}$ 不相鄰於 $u$ 或不相鄰於 $v$
• 因此反過來，在 $\bar{G}$ 中，$x\in V(\bar{G})-{u,v}$ 至少與 ${u,v}$ 中至少 1 個點相鄰，如下圖所示：
• 故可以推得 $\textrm{diam}\space \bar{G}\leq3$

其他定義

center

• eccentricity 最小的 subgraph
• 任 2 點在原圖相鄰，在生成子圖也必定相鄰

Wiener index

• $G$ 中任 2 點 distances 的和
  • $D(G)=\sum_{u,v\in V(G)}d_G(u,v)$

Theorem 2.1.13

• The center of a tree is a vertex or an edge.

Proof

• 設有 1 個 tree $T$
• By induction
  • 當 $n(T)\leq2$ 時，center 是一整個樹
  • 當 $n(T)\geq2$ 時:
    • 刪去 $T$ 的每一個 leaf，得到 $T'$
    • 此時 $n(T')\geq 1$，且 $\varepsilon_{T'}(u)=\varepsilon_T(u)-1 ,\space \forall u\in V(T')$
    • 並且 $T$ 中的 leaf 的 eccentricity 大於 leaf 的鄰居 的 eccentricity
    • 由此可知，$T$ 和 $T'$ eccentricity 最小的 vertices 是一樣的
    • 故 center 如果不是一個點就是一個edge

Theorem 2.1.14

• Among trees with $n$ vertices, the Wiener index $D(T)=\sum_{u,v}d(u,v)$ is minimized by stars and maximized by paths, both uniquely.

Stars

證明最小值

• 一個樹有 $n-1$ 個 edges，每對點的連線至少為 distance 1，stars 的性質正好可以使 Wiener index 最小，故得證

證明獨特性 (Uniqueness)

• 考慮 leaf $x\in T$ 以及 $x$ 的鄰居 $v$
• 如果有其他點與 $x$ 的距離為 2，則該點與 $v$ 相鄰
• 此特性使 $T$ 屬於一個 star

求值

• $D(K_{1,n-1})=(n-1)+2(^{n-1}_2)=(n-1)^2$
  • $(n-1)$ 為中間點到其他點的距離
  • $2(^{n-1}_2)$ 每個 leaf 到其他點的距離

Paths

求值

• 令 $u$ 為一條 $n$-vertex path $P_n$ 的端點 (endpoint)
• $\sum_{v\in V(P_n)}d(u,v)=\sum^{n-1}_{i=0}i=C(^n_2)$
  • 從 $u$ 出發，不算 $u$ 的話有 $n-1$ 個點，$0+1+\dots+n-1$ 即為 $P_n$ 的長度，正好為 $C(^n_2)$
• 計算 $D(P_n)$: \begin{align*} D(P_n)&=D(P_{n-1})+C(^n_2) \\\
  &=D(P_{n-1})+D(P_{n-2})+C(^n_2) \\\
  &=D(P_{n-1})+D(P_{n-2})+\dots +D(P_3)+D(P_2)+D(P_1)+C(^n_2) \\\
  \end{align*}
• 其中根據 Pascal’s Formula: $$ C(^{n+1}k)=C(^n_k)+C(^n{k-1}) $$
• 因此 $D(P_3)+D(P_2)+D(P_1)$ 可以寫成: \begin{align*} D(P_3)+D(P_2)+D(P_1)&=C(^3_2)+C(^2_2)+0 \\\
  &=C(^3_2)+C(^3_3)+0 \\\
  &=C(^4_3) \end{align*}
• 故可以推導 $D(P_n)$: \begin{align*} D(P_n)&=D(P_{n-1})+C(^n_2) \\\
  &=D(P_{n-1})+D(P_{n-2})+C(^n_2) \\\
  &=C(^{n-1}_2)+C(^{n-1}_3)+C(^n_2) \\\
  &=C(^n_3)+C(^n_2) \\\
  &=C(^{n+1}_3) \end{align*}

證明獨特性 (Uniqueness)

• (Base) 當 $n=1$ 時，得證，因為此時的樹只有一個點，path 為 $P_1$
• (Induction step) 當 $n>1$ 時:
  • 設 $u$ 為一個 leaf
  • $\Rightarrow D(T)=D(T-u)+\sum_{v\in V(T)}d(u,v)$
  • By induction hypothesis:
    • $D(T-u)\leq D(P_{n-1})$
    • 等號成立時代表 $T-u$ 是一條 path

證明最大值

• 設點 $u$ 在一棵樹 $T$ 的一路徑 $P_n$ 中到其他點的距離為一集合 ${1,2,\dots,n-1}$
• 此集合包含了"與 $u$ 最近的點" 以及"與 $u$ 最遠的點"
• 若 $u$ 不是 $P_n$ 的端點，則 $u$ 到 $P_n$ 其他點的距離會縮短 $\Rightarrow \sum_{v\in V(T)}d(u,v)$ 會變小
• 故當 $u, v$ 構成 Path 時 $D(T)=\sum_{u,v}d(u,v)$ 會有最大值

Lemma 2.1.15

• If $H$ is a subgraph of $G$, then $d_G(u,v)\leq d_H(u,v)$

Proof

• $H$ 中的任一 path 也存在於 $G$ 中
• 因此 $G$ 中最短的 path 必定不會比 $H$ 的最短的 path 還長

Corollary 2.1.16

• If $G$ is a connected $n$-vertex graph, then $D(G)\leq D(P_n)$

Proof

• 設 $T$ 為 $G$ 的 spanning tree
• 則 $D(G)\leq D(T)$
  • based on Lemma 2.1.15
• 且 $D(Ｔ)\leq D(P_n)$
  • based on Theorem 2.1.14