---
# System prepended metadata

title: 2020-03-20 Fundamental Concept I + Bonus Questions
tags: [圖論]

---


# 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 <font color='#ff0000' > no </font>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$, <br/> denoted as $G\cong H$ 
    * 較大的圖中找小圖的isomorphic 是NPC的問題
    * 是一種equivalence 的關係
         1. 自己跟自己同構(reflexive)
         2. 滿足互為同構的關係(symmetric)
         3. 同構擁有遞移性(transitive)
         
    * Proof:
        :::info
        <font color=#000000>
        
        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$, <br/> 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)$ <br/> (bijective function 的特性)<br/>.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. <br/> $uv \in E(F) \Leftrightarrow f(u)f(v) \in E(G)$ <br/> $xy \in E(G) \Leftrightarrow g(x)g(y) \in E(H)$  <br/> since it's $isomorphism$, <br/>$\forall xy \in E(G),~ \exists uv \in E(F)$ s.t. $f(u)=x$, $f(v)=y$ <br/> thus yields $uv \in E(F) \Leftrightarrow g(f(u))g(f(v)) \in E(H)$ <br/> $F \cong G$, $G \cong H \rightarrow F \cong H$
        </font>
        :::
            

## 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)