2020-03-20 Fundamental Concept I + Bonus Questions

# 2020-03-20 Fundamental Concept I + Bonus Questions ###### tags: `圖論` [TOC] {%youtube 8XbaPEGTOvM %} ## 講義: fundamental_concept_0_2020 ### **Definition** * $V(G)$ : set of vertices * $E(G)$ : set of edges >[color=#00ff00] > > $E(G) ⊆ V(G) \times V(G)$ >[name=MathematiKai ] #### 2. relation 裡面的兩個元素是parrallize relation 是兩個集合之間cross product 的結果 map 到 0 或1 ex: 如果點集合是 $v_1,v_2 ..~ v_5$ 跟自己crossproduct 最多有25個情況 map 到 codomain 的值就只有 1 或 0, 有邊就是 1 反之亦然 graph 在定義並沒有限制 mutiple edge 的發生所實際上要表示出這三種關係點的編號邊的編號和點點之間的關係式(只記下有關係 codomain = 1 的點) Graph 的兩個集合中若是有mutiledge的存在，在edge的編號上做改變，在relation的edge集合中才會看出，相同element $(V_1,V_2)(V_1,V_2)$是指向不同的邊無向圖 list 的 order 不重要 adjacent 是討論兩個點之間的關係有連線的兩個端點是neighbor 專業講法是 adjacent ### Rooted tree vs. Unrooted tree Root: 點跟點之間，有 parent 和 child 關係 Unrooted: 反之亦然 Tree 是 bipartite 用著色的方法可以很直觀的證明也可以用到root 的距離是奇數還是偶數去分出兩個independent set Tree 有四種不同的定義(前三項任兩個合併就是tree) 1. connected + no cycles 2. connected + n-1 edges 3. n-1 edges + no cycles 4. no loops + exactly one path between vertex * **Path** : $<v_0,v_1...,v_k>$ a distinct adjacent vertices sequence * **Loop** : **an edge** whose endpoint are equal * **Cycle**: $<v_0,v_1...,v_k,v_0>$ $v_0\ ... v_k$ distinct sequence of adjacent vertices * **Multiple edges** : edges having the same pair of endpoints --- * **Simple graph** : graph having no loops or multiple edges * **Multigraph** : graph having loops or multiple edges * **Finite Graph** : $V(G)$ and $E(G)$ are finite sets * **Null Graph** : $V(G)$ and $E(G)$ are empty * **Complement Graph** : vertex Set: V(G) $\\uv \in E(\bar G)\Leftrightarrow uv \notin E(G)$ * **Subgraph :** $V(H) \subseteq V(G) \\ E(H) \subseteq E(G) \\點邊的關係相同\\Denoted \ as:H \subseteq G$ * **Connected graph :** G is connected $\Rightarrow$ each pair of vertices in G belong to a path --- * **Clique (點集合的子集)** : * **Definition**: a set of pairwise *adjacent* vertices * *Complete* (sub)graph * pairwise: 兩兩相聯都有邊，單一一個點也算pairwise $\Rightarrow$ 1個點是clique * clique size 的最大size 是NP complete 問題 * **Independent set (stable set)** : * **Definition**: a set of pairwise *nonadjacent* vertices * Duel problem: $\text{finding Max clique in } (G) \Leftrightarrow \text{finding Max independent set in }(\bar G)$ ![](https://i.imgur.com/MOR70Gf.png =50%x) --- **為了方便記錄、去操作graph，需要用matrix的方式去紀錄圖** * **Adjancency Matrix(A)** : $a_{ij}$ is number of edges between $v_i, v_j$ (vertice-to-vertice) * **Incident Matrix(M)** : $m_{ij}$ is boolean of "$v_{i}$ is endpoint of $e_{j}$" (vertice-to-edge) - incident: 點為邊的端點的這種relation的專業講法, incident edges = degree of vertex ![](https://i.imgur.com/0C0uG4V.png =80%x) ### Königberg 7-Bridge Problem * 七橋問題是圖論的起源 * Situation: 每個edge都必須並只能走過1次 1. 每個點的degree都是偶數: 可從任意點開始，並全部走過且回到原點. 2. 只有2個點的degree是奇數: 例點A和點B, 那可以從其中一點(A或B)出發, 走到另一點(B或A). 3. 其餘無解 ### Partite * Independent set * Multipartite - union of independent sets + **Bipartite ⟺ No odd length cycle** + [證明P.28](https://hackmd.io/QIz8EtcKRqWANklnF4S-Fw?both) + k-partite: k $\geq3$ * Detect k of k-partite Graph - Color the Vertices * Complete k-partite graph $K_{n_1,n_2,...,n_k}$ * every vertex is connected with those in different partite ### Chromatic number $\chi(G)$ * Minimum number of color s.t. adjacent vertices' color are different. 一種把點做label的方式，adjacent vertex 不同顏色來著色，所需最少需要的顏色數 * $\chi (tree) =2$ $\\\chi(bipartite) \leq 2$ * $\chi$一定存在，但是如果用最少的color 去著色是無法決定難度的問題(harder than NP-C?) >[color=#00ff00] > > Chromatic number 有針對 vertex 與 edge 兩種 > 此處$\chi(G)$是針對vertex > > 找出$\chi(G)$等同找尋「k-partite的最小的k值」 > 應該是NP-C的問題 >[name=MathematiKai ] ### Isomorphism (圖跟圖之間的關係) * **Isomorphism** (General desciption) - set $X$ with a binary relation $R$ - set $Y$ with a binary relation $S$ - isomorphism from $X$ to $Y$ is a **bijective** function $f: X → Y$ such that $R(u,v) \Leftrightarrow S(f(u),f(v))$ * 圖論定義: * From a simple graph G to a simple graph H is a **bijective** function$f : V(G) \rightarrow V(H) \text{ such that } uv \in E(G) \Leftrightarrow f(u)f(v) \in E(H)$ where $u,v \in G$, denoted as $G\cong H$ * 較大的圖中找小圖的isomorphic 是NPC的問題 * 是一種equivalence 的關係 1. 自己跟自己同構(reflexive) 2. 滿足互為同構的關係(symmetric) 3. 同構擁有遞移性(transitive) * Proof: :::info 1. The identity permutation on $V(G)$ is an isomorphism from $G$ to itself. Thus $G \cong G$ 2. If $f : V(G) \rightarrow V(H)$ is $isomorphism$ from $G$ to $H$, by definition , $\exists f^{-1} : V(H) \rightarrow V(G)$ s.t. $uv \in E(H) \Leftrightarrow f^{-1}(u)f^{-1}(v) \in E(G)$ (bijective function 的特性) .Thus $G \cong H \rightarrow H \cong G$ 4. Suppose $f : V(F) \rightarrow V(G)$ and $g: V(G) \rightarrow V(H)$ are $isomorphisms$ s.t. $uv \in E(F) \Leftrightarrow f(u)f(v) \in E(G)$ $xy \in E(G) \Leftrightarrow g(x)g(y) \in E(H)$ since it's $isomorphism$, $\forall xy \in E(G),~ \exists uv \in E(F)$ s.t. $f(u)=x$, $f(v)=y$ thus yields $uv \in E(F) \Leftrightarrow g(f(u))g(f(v)) \in E(H)$ $F \cong G$, $G \cong H \rightarrow F \cong H$ ::: ## Bonus Quetions 1. Prove "graph containing odd cycle" $\Leftrightarrow$ "graph is not bipartite" **Sol:** 提示 pigeon hole? 用著色的方式解好像挺容易的(? [name=Neko] 話說這題目有辦法從右邊到左邊? [name=Neko] $P \Leftarrow Q$ is $\neg P \Rightarrow \neg Q$ [name=Omnom] 3/27講義的第28頁 [ref1](https://proofwiki.org/wiki/Graph_is_Bipartite_iff_No_Odd_Cycles) 2. Define isomorphism of multiple graph **Sol:** [ref1](https://math.stackexchange.com/questions/3201645/expanding-definition-of-simple-graph-isomorphism-to-include-multigraphs)