2020-04-17 Directed Graph, Trees & Distance I

# 2020-04-17 Directed Graph, Trees & Distance I ###### tags: `圖論` [video](https://www.youtube.com/watch?v=cNXxtyS2t_0&list=PL8xY3250v6CSrLIsKMFLyrCfWonR1STtt&index=5) # Directed Graph(digraph) ## P.2,3 Definitions * V(G)、E(G)、function assigning each edge an ordered pair of vertices * An edge is from its *tail* to its *head*. * $UV$ ($u$ is tail , $v$ is head) NOTE: Head & Tail定義有不同版本這本書箭頭端是Head * Simple (不會有multiple edge, ~~最多一個loop~~) >[color=#00a000] > >沒有loop吧？ >ans: 一個點自己連自己 >[name=Omnom] ## P.4 Definitions (Conti.) * Path: 沿著箭頭的path 逆向的連接不算是path * Directed cycle: 沿著箭頭走可以走回到起點 * underlying graph: digraph把箭頭拿掉(no order,multiple edge 拿到剩一條edge) ## P.5 Definitions (Conti.) * Adjacency matrix $A(G)$: $A_{ij} = 1$ if $\exists$ edge from $v_i$ to $v_j$ * incidence matrix $M(G)$: (點邊關係) + $m_{i,j}=+1$ if $v_i$ is tail + $m_{i,j}=-1$ if $v_i$ is head ![](https://i.imgur.com/6dAvU5j.png) ## P.6 Definitions (Conti.) * **weakly connected**: underlying graph is connected * **strongly connected**: $\forall$ordered pair of u,v of vertices, $\exists$ a path from u to v + 單點在這本書視為strong connected * **strong components**: maximal strong subgraphs ## P.7 Definitions (Conti.) * $d^+(v)$ outdegree number of edges with tail $v$ * $d^-(v)$ indegree number of edges with head $v$ * out-neighborhood, successor set $N^+ (v) := \{x ∈V (G) : v → x\}$ * in-neighborhood or predecessor set $N^− (v) := \{x ∈V (G) : x → v\}$ * minimum indregree: $\delta^-(G)$ * maximum indregree: $\Delta^-(G)$ * minimum outdregree: $\delta^+(G)$ * maximum outdregree: $\Delta^+(G)$ ## P.8 一個head配一個tail，也等於edge的個數 ## P.9 Definitions (Conti.) Eulerian definition of Eulerian is the same on any king of graph ## P.10 $Lemma$: If $G$ is a digraph with $\delta^-(G) ≥ 1$ or $\delta^+(G) ≥ 1$, then $G$ contains a cycle. $proof:$ :::info 考慮out-degree 一條path，尾端的out-degree(箭頭)最後會指向path上其中一點，因此形成cycle in-degree證明的部分，只要將方向顛倒即可 ::: ## P.11 Definitions (Conti.) Orientation >[color=#00a000] > >a.k.a. 每個邊加箭頭 >[name=Omnom] * oriented graph: simple graph 加箭頭 * tournament: complete graph 加箭頭 ## P.12 King * $Def:$ vertex from which every vertex is reachable by a path of length at most two (從king到任一點可以2步內走到) * $Proposition:$ Every tournament has a king. - 補充: 必須要是tournament(simple graph 是complete graph)才會有此性質，因為每個vertex都會和其他vertex有連線，只是說看是A指向B還是B指向A * $proof:$ :::info 依下面的例子來講，假設a不是king，代表說至少會有一個node(假設b)的outdegree會比a大，因為那個node就是指向a，而且a的outdegree所指向的node也都不會指向b，也就是說b的outdegree也同時會指向這些node，同理可以再繼續驗證b，直到最後找不到有node的outdegree比最後一個找的還大，那這最後一個node一定是king。 如果某點不是king，那麼一定找得到outdegree更大的點$\Leftrightarrow$ 如果outdegree更大的點找不到，那麼某點一定是king$\Rightarrow$outdegree最大的點就是king e.g. a3才有可能不是king ```graphviz digraph { a1->b1 a1->c1 b1->c1 a2->c2 b2->a2 c2->b2 a3->c3 b3->a3 b3->c3 } ``` ::: # Trees & Distance I ## P.2 Definition * spanning subgraph >[color=#00a000] > >spanning的意涵就是**包含全部的vertex** >A subgraph S of a graph G is a graph whose set of vertices and set of edges are all subsets of G. (Since every set is a subset of itself, every graph is a subgraph of itself.) >[name=Omnom] ## P.3 Properties of Trees $Lemma.$ 形成tree至少要有2個點刪完leaf(degree=1)，它還是tree，只是變成n-1個點而已 ## P.4,5,6,7,8 Properties of Trees (Cont.) $Theorem.$ * 組成tree三大元素:{connected, acyclic, n-1 edges} * The following statements are equivalent: A. connected + no cycles B. connected + n-1 edges C. n-1 edges + no cycles D. $\forall u,v \in V(G)$, $\exists!~u,v$-path >[color=#00a000] > >附註：$\exists!$是「只存在一個」的意思 > >我看A是可以直接等於D了www >1. $\forall u,v \in V(G)$, $\exists$ $u,v$-path $\leftrightarrow$ connected >2. $\exists$ only 1 $u,v$-path $\leftrightarrow$ no cycle > >[name=Omnom] $proof.$ :::info $A \Rightarrow \{B,C\}$: (connected+no cycle 可以得到 n-1 edge) by $Strong ~ Induction$ $n=1$：明顯成立 Suppose $1<k<n$ 成立 for $k=n$，就是把node數是$n-1$時的點接回去(使用P.3 $lemma$)， (透過$lemma$知道可以刪除leaf，得到$n-1$ vertices數的tree，再透過$lemma$知道接回leaf時，只會增加一個edge) ::: :::info $B\Rightarrow\{A,C\}$ (connected+ $n-1$ edges得到no cycle) 假設connected+ $n-1$ edges得到有cycle，現在把cycle上的edge拿掉並不破壞connected，但由上面$A \Rightarrow \{B,C\}$得知acylic connected graph會有$n-1$ edges，但是這裡的條件是$G$本身就有$n-1$ edges，把cycle上的edge拿掉還是$n-1$ edges($\rightarrow \leftarrow$)，所以假設錯誤 $i.e.$ connected+ $n-1$ +cycle {$\Rightarrow$|remove edges} connected+ $n-k$ + no cycle $\Rightarrow\Leftarrow$ ($A \Rightarrow \{B,C\}$) ::: :::info $C\Rightarrow\{A,B\}$ ($n-1$ edges + no cycle得到connected) 假設no cycle+ $n-1$ edges得到有 no connected，假設現在有$k(k>1)$個component，每個vertex都只會出現在一個component，首先可以先讓每個component 符合 no cycle，也就是每個component都會有$n(G_i)-1$個edge，$k$個component共會有$n-k$個edge，由前面假設可得知G會有$n-1$個edge，i.e. $k=1$，與假設不符 [2020-03-27_P.20](https://hackmd.io/Q7zr3d6mQVmRv2VtWxrtcQ#P20) ::: ::: info 1. $A \Rightarrow D$ (connected+no cycle得到$\forall u,v \in V(G)$, $\exists ~exactly ~ one \ u,v$-path) 假設有2條路可以走，但是會有cylcle出現 ($\neg D \Rightarrow \neg A$) 2. $D \Rightarrow A$ 假設有cycle，那至少會有一組u,v會有2條路 ($\neg A \Rightarrow \neg D$) ::: ## P.9 Properties of Trees (Cont.) $Corollary.$ (a) every edge of a tree is cut-edge (b) adding one edge to tree forms exctly one cycle $c$ every connected graph contains spanning tree $proof$:(待補) :::info (a) tree has no cycle by [2020-04-10 P.24](https://hackmd.io/QIz8EtcKRqWANklnF4S-Fw#P24) Q.E.D. (b) [A & D](#P45678-Properties-of-Trees-Cont) $c$ ::: ## P.10 $Proposition$ sapnning trees $T,T' ⊆ G$ $G$: connected $T ≠ T'$ given $e \in E(T)-E(T')$, then $\exists e'\in E(T')-E(T)$ $s.t.~$ $T-e+e'$ is a spanning tree of $G$ 補充解釋: $e$ 只要是 $T$ 和 $T'$ 2個spanning tree不重複的edge，就永遠可以找到至少一條 $e'$ 在 $e$ 被移掉後可以不上去變spanning tree ## P.11 跟P.10條件一樣，只是換成$T'+e-e'$ * 從代數的角度來看像是扣掉自己的edge再加上其他edge，但是從幾何角度來看不太一樣，這邊是先加上edge再考慮後面的後果 T'+e的後果會變成cycle，不過刪掉e'也只會把cycle上的edge刪掉而已，變成acyclic ## P.12 * distance from u to v: the least length of u-v path * eccentricity: $\varepsilon(u)$, $max_{v \in V(G)} d(u,v)$ (u點到離他最遠的點的距離) * diameter: $diam(G)$ $max_{u,v \in V(G)} d(u,v)$, the greatest eccentricity * radius: $rad(G)$, $min_{u\in V(G)}\varepsilon(u)$, the smallest eccentricity 補充: * diameter: of G is the value of the greatest eccentricity. * center: the set of nodes v such that $ecc(v)=rad(G)$ >[color=#00a000] > >講義上是寫說subgraph induced by ... >[name=Omnom] ## P.13 Theorem 2.1.11 * If G is a simple graph, then diam G>=3 $\Rightarrow$ diam $\bar{G}<=3$ proof: diam G>2，there exist nonadjacent vertices u,v with no common neighbor. 由於原圖G 中的u,v不相連，所以首先$\bar{G}$中的u,v會相連，接著原圖G中沒有任何一點會同時和u,v連，因此$\bar{G}$中的點要嘛和u連、和v連、或和u,v都連，因此diam$\bar{G}$<=3