# 2020-03-27 Fundamental Concept II
###### tags: `圖論`
[影片](https://www.youtube.com/watch?v=G35ucJP3YoA&list=PL8xY3250v6CSrLIsKMFLyrCfWonR1STtt&index=4)

## 講義: fundamental_concept_1_2020

### P.2 Complete Graph
* $Def$: A simple graph whose vertices are pairwise adjacent.
* $K_n$ : Complete graph of $n$-vertices
* $K_{r,s}$: Complete bipartite graph(or biclique)
* c.f. Clique: A set of pairwise adjacent vertices 兩兩有連線(不限定simple graph)

$C_n$是cycle n vertices
$P_n$是path n vertices = n-1 edge

Complete bipartite = biclique $\neq$complete grph
$K_5$中找出$C_3$有幾種isomorphism 的subgraph = $C^5_3$
$K_{2,3}\in K_{2+3}$的subgraph

補充：[complete k-partite](https://mathworld.wolfram.com/Completek-PartiteGraph.html)

### P.3
Isomorphic: $G_1、G_2、G_4$
Complement Graph: 2 disjoint $K_3$
***方法：***
isomorphism找出bijection Function 先找出adjacent matrix 在判斷出有沒有這種function

$G_1,G_2,G_4$ 是isomorphic(補圖也是isomorphic), 皆為$K_{3,3}$ 而complement 是$C_3$ disjoint的graph
$G_3$有兩個$K_3$的subgraph(非bipartite), complement graph 為$C_6$ connected graph

### P.4

* Self Complementary
- Definition: $G$ and $\bar G$ are isomorphic

* Decomposition of a graph $G$
- a list of subgraphs $\{G_i \}$, $G_i=\{V_i, E_i\}$
- $\bigcup_{i}{G_i}= G$
- 一條 edge 只會出現在一個subgraph裡
- $E_i \cap E_j= \emptyset , \forall i ≠ j$

* An $n$-vertex graph $H$ is self-complementary $\Leftrightarrow K_n$ has a decomposition consisting of two copies of $H$.

$K_5$可拆成兩個 $C_5$的self-complementary graph

$K_4$可拆成三個$P_3$ subgraph

$K_7$有$C_2^7=21個edges$可以decompose成7個$K_3$

$K_6$ 可以解構成 5個$P_4$

>[color=#00a000]
>
>$\Rightarrow$
>$H$ $\cong$ $\bar H$
>$\bar H = K_n - H$ $\Rightarrow K_n\ decompose\ to \ 2\ H$
>
>$\Leftarrow$ ( 直接證明)
>
>[name=Omnom]

### P.5


claw: $K_{1,3}$
paw: $claw\ + 1\ edge$
kite: $K_4-1\ edge$

**1.1 exercise 6,7,8,32,34,35,36,37
有可能變成考試的題目**
### P.6 Petersen Graph

* Definition:
- **Simple graph** whose **vertices are the 2-element subsets** of a 5-element set and whose edges are the pairs of disjoint 2-element subsets.( 12 = 21 編碼相同、 一個點最大3 degree)
- i.e.
+ each vertex is encoded with 2 elements from given 5 elements
+ any two adjacent vextices contain different elements (disjoint)
+ 5 elements must be used at least once

* girth(周長): A graph with a cycle is the length of its shortest cycle.
- 可能不只1個
- no cycle has infinite girth

### P.7 Property of Petersen graph

在PG裡兩個不相鄰的點 $\Rightarrow$ exactly a common neighbor

$pf.$
:::info

<font color=#000000>

1. Nonadjacent vertices are 2-sets sharing one element; their union S has 3.

2. A vertex adjacent to both is a 2-set disjoint from both.

3. Since the 2-sets are chosen from {1, 2, 3, 4, 5}, there exactly one 2-set disjoint from S.

</font>
:::

proof 補充:
1. 2個不相鄰的點會share一個element

### P.8 Property of Petersen graph(Conti)

* Peterson graph has girth 5

proof補充:

1. 不會有1 cycle、2 cycle(simple graph)

2. 不會有3 cycle(沒辦法用5個element編完)

3. 不會有4 cycle(違反proposition，PG只會有一個common neighbor，4 cycle會有2個common neighber)

補充：
[Petersen Graph](https://mathworld.wolfram.com/PetersenGraph.html)
[Generalized Petersen Graph](https://en.wikipedia.org/wiki/Generalized_Petersen_graph)

>[color=#00a000]
>
>我還是對girth = 5感到疑惑
>[name=Omnom]

### P.9 Automorphism of $G$
* Definition: **isomorphism** from $G$ to $G$
- Usage: 對稱性
- 可以透過對稱軸找automorphic [name=Omnom]

vertex-transitive: for every parir $u,v\in V(G)$存在轉換的函數 ;
identity permutation(點跟自己換是不是isomorphism)
>[color=#00a000]
>
>自己和自己互換感覺很trival
>討論上應該是沒意義的
>[name=Omnom]

$1\leftrightarrow 4,2\leftrightarrow 3$ is isomorphism
$1\leftrightarrow 2$ is not isomorphism

### P.10 P.11
Automorphism of G 是排列組合的函數$P$
$V(G)\to V(G)\ s.t. P(u)P(v) \in E(G)\ iff\ u,v \in E(G)$

matrix 第一行是原始的點，第二行是交換過的點

Automorphism: 旋轉、對稱
$\epsilon:identity/ \alpha : reflection/\ r: rotation$
### P.12 Path, Cycle, Trail

* Walk
- a list of vertices and edges($v_0,e_1,v_1,...,e_k,v_k$)
- each edge is between 2 vertices
- 意思就是把所有走過的路記錄下來
* Trail
- **No repeated edge 點可重複**
- 七橋問題就是找trail
- 邊跟點都記
* Path
- **No repeated vertices**
- 只記點

### P.13 Path, Cycle, Trail (Cont.)

* $u,v$-walk ($u,v$-trail)
- direction : $u \rightarrow v$
* $u,v$-path
- $degree : \left\{ \begin{array}{**lr**}{1:u,v \\ \text{otherwise} : \text{internal vertices}} \end{array}\right.$

* length of walk, trail, path, cycle
- number of edges
* closed (w.r.t walk and trail)
- endpoints are the same
- 補充:
+ path 不管他有沒有close，因為只記點

### P.14,15 Path, Cycle, Trail (Cont.) Example

### P.16 Strong Principle of Induction

* a statement $P(n)$ with interger parameter $n$
* $P(1)$ is true
* $\forall n > 1$ , $P(k)$ is true for $1 ≤ k < n \rightarrow P(n)$ is true

### P.17 Lemma: Every $u,v$-walk contains a $u,v$-path

$pf.$ use **Strong Principle of Induction**

* Basis step: l=0.
- W contains a single vertex (a length-0 path).
* Induction step: l≥1.
- Case 1. No repeated vertex.
- Case 2. W has a repeated vertex w.(把多走的路拿掉)

### P.18 Connected graph G
* Connected
- Def: $\forall u,v \in V(G),\ \exists u,v-path$
- 探討的是**點**的關係
- **ordered pairs (u,v)**: 描述這兩點是connected
+ 可以(u,u)
+ (u,v)和(v,u)不同
* Connected component
- Def: **maximal connected** subgraph

- 
- connected 關係滿足 equivalence relation
- Equivalence classes : {1,2,3,4,5}, {6,7}

### P.19 Connected Component
* component = maximal connected subgraph
* Trival component: has no edges
* Isolated vertex: vertex of degree 0

### P.20

$Proposition$: graph with $n$ vertices and $k$ edges has **at least** $n-k$ components
* $pf.$ each edge reduces at most 1 component
- edge從0條開始，每次多加一個edge進去，最多只會減少一個component
* 最少加n-1 個邊(ex: tree) $\to$ connected graph

### P.21 cut-edge, cut vertex

* $Def$ : an edge or vertex whose deletion increases the number of components.

### P.22 Induced Subgraph $G[T]$

* $T\subseteq V(G)$
* $G[T]=\{T,E_T\}$
* $E_T=\{u,v\in E(G):u\in T,v\in T \} \\ (T點之間的所有的edge都要留著)$
### P.23 Biconditional statements
三種 $P\Rightarrow Q$的等價表示
Note: Truth table