---
tags: 數讀
---
# 圖論part1
> [name=W_Ice_Tri] [time=Sun, Mrch 7, 2021] [color=#1f1e33]
## 0. 前言
這裡只有名詞解釋＋小性質＋上課不想講的東西(自己證明啦)

不保證內容皆實用

只保證內容合法不毒瘤

當作常識來讀會輕鬆一點，基本上這些名詞都很直觀
:::spoiler 常見畫圖工具
https://csacademy.com/app/graph_editor/
https://graphonline.ru/en/
:::
## 1. 無向圖
- 點：另稱頂點,節點，為構成圖的基本單位(可以命名)
- 邊：兩個點之間的關係，一條邊一定連接兩個點，以$(v_1,v_2)$代表連結兩點$v_1,v_2$的邊，若有數條邊連結兩個點，則稱之重邊，若重邊的頂點一樣，稱之自環
- $G(V,E)$代表一種圖，其中$G,V,E$分別代表圖的名稱,點與邊的集合
- 簡單圖：1.沒有兩條邊，它們所關聯的兩個點都相同(無重邊),2.每條邊所關聯的是兩個不同的點(無自環)
- 完全圖：每對點恰有一邊(塞滿邊的簡單圖)，通常以$K_n$表示$n$階完全圖
- 度：一個點的度是指與該點相關聯的總邊數，通常以$d(v)$表示點v的度，對於圖$G$中最小度與最大度，通常以$\delta(G),\Delta(G)$表示，另外度=1的點稱之葉子，度=0的點稱之孤點
- 正則圖：即每個頂點的度相同的圖
- 同構：若兩張圖$G=(V,E),H(V',E')$同構，表示存在$V\to V'$的一一對應，且在$G$中的點有連邊若且唯若$H$中對應到的點有連邊，此時記做$G\simeq H$。同構時圖論上不會去區分它們。
- 子圖：跟子集合的概念相同
- 路徑：通常以一個序列表示($a,e_0,v_1,e_1,v_2,e_2...v_k,e_k,b$)為從點$a$到點$b$的道路(walk)，若$a=b$稱之封閉道路，反之稱開放道路，若$e_1,e_2...e_k$兩兩不同，則稱之行跡(trail)，若此路徑每個點最多只走一次，稱之路徑(path)。
- 環/圈：一條只有第一個和最後一個點重複的非空路徑，故稱$(v_1,v_1)$自環
- 距離：兩點間的距離$d(v_1,v_2)$為$v_1$到$v_2$間的最短路徑長
- 連通：對於兩個點, 存在以其中兩點的路徑,則稱此兩點連通
- 連通圖：任兩點連通的圖
- $n-$部圖：簡單來說就是將頂點分成好幾個非空集合，而所有的邊所屬的兩個頂點來自不同的集合，通常以$G_{v_1,v_2...;E}$表示
此為$K_{3,3}$(完全二部圖/完全偶圖)
- 樹,森林：一種特別的圖，有三個定義且任兩個可推得第三個。若一張圖中沒有環，則稱之森林
- $|E|=|V|-1$
- 任兩點之間恰有一條簡單路徑
- 沒有環
- 平面圖：無邊相交的圖，以邊隔出來的區域稱之面，被隔在外的面稱之外部面，反之稱內部面

#### Remark.
在路徑和環那邊，有些人會去定義"簡單路徑"為點不重複之路徑，而"路徑"本身可以有重複點，環也一樣有這樣的問題。
## 2. 有向圖
- $(v_1,v_2)$代表從$v_1$到$v_2$的邊，圖上通常用箭頭表示$(v_1\rightarrow v_2)$，若任兩相異頂點間皆有邊，則稱之競賽圖
- 出、入度：$d^+(v_k),d^-(v_k)$分別代表$v_k$的出度與入度
- 連通：對於任兩相異點$x,y$，有從$x$到$y$與從$y$到$x$的路徑,則稱此兩點連通
- 強連通圖：任兩點連通的圖

---

接下來補幾個有無向圖的通用定義
- 邊/點權
就當作是在邊或點上的賦值吧，有時稱此種圖為權重圖
- 對偶
看看例圖就好了，跟幾何中的對偶概念大致上一樣：$V\to F,E\to E,F\to V$(圖源：wiki)

## 3. 小性質
- 奇頂點數$\equiv 0\pmod2$
- 對於任何無向圖皆滿足$\displaystyle{\sum^v_{k\in V}d(k) = 2|E|}$
- 在無向連通圖中，$|E| \geq |V|-1$；在有向強連通圖中，$|E| \geq |V|$
- 有向圖中，$\displaystyle{\sum^v_{k\in V}d^+(k) =\sum^v_{k\in V}d^-(k)=|E|}$
- $n$-完全圖的$\displaystyle{|E|=\frac{n(n-1)}{2}}$
- 樹與完全圖皆是連通圖，且$K_n$是$(n-1)$階正則圖
- 平面圖中，$e\leq 3v-6$
- 定義一個圖的邊加上數個頂點成新的圖，稱兩圖為同胚。在平面圖中，必不含同胚於$K_5,K_{3,3}$的子圖
- 在競賽圖中，若任兩相異點恰有一邊，必存在一點$v$到其他點的路徑長皆$\leq 2$，若出度最大的點只有一個，則$v$必為此點
- 在競賽圖中，若任兩相異點恰有一邊，且無頂點的入度$=0$，則必存在一個簡單路徑，其中此路徑走過所有點
- 在競賽圖中$(|V|\geq 3)$，存在迴路三角形的充要條件為：有兩個頂點$v,v'$，滿足$$d^+(v)=d^-(v')$$
## 4. 歐拉問題
### Problem4.1
歐拉請問您，一筆畫問題的充要條件是什麼？
### Problem4.2
又是歐拉請問您，若圖$G$中有$2k$個奇頂點，試問至少要幾筆畫才能畫成？
### Definition (Euler tour)
歐拉路徑(Euler trail)：若一圖中存在歐拉路徑，簡單來說就是可一筆畫的圖。若起點與終點相同，則稱此圖存在歐拉迴路(Euler tour)。
### Problem4.3
一有向圖$G$中存在歐拉迴路的充分必要條件是：$G$是強連通圖且對於所有頂點$v_i\in V$，滿足$d^+(v_i)=d^-(v_i)$
## 5. 歐拉示性數
### Problem5.1
若一連通圖$G(V,E)$中，由邊所圍成的區域中，若不包含頂點，則稱之面，今令$G$的點,邊,面數=$f$，試證$$v-e+f=2$$
以此圖為例，$v=6,e=8,f=4\Rightarrow 6-8+4=2$
### Problem5.2
請解釋為什麼任何立體圖形皆符合Problem5.1.的等式
### Problem5.3
呈Problem5.1.若圖$G$的連通數量為$r$，試證$$v-e+f=1+r$$
## 6. 更多名詞與小小性質
- (點)獨立集：若點集$S$在$G$中互相不連邊，則稱$S$為(點)獨立
- 匹配：若邊集$S$在$G$中使用到的點皆不相同，則稱$S$為一個匹配(或稱邊獨立集)
- 點覆蓋：點集$S$為點覆蓋表示圖$G$中的每條邊的兩個頂點都至少有一個在$S$裡
- 邊覆蓋：點集$S$為邊覆蓋表示圖$G$中的每個點都至少都被一條$S$裡的邊用到

- 直徑：圖$G$的直徑長diam$(G)$為最遠的兩個點的路徑長

- 半徑：圖$G$的半徑長rad$(G)$為一個點和其他點最遠距離的最小值，i.e.$$\displaystyle{\min_{v\in V}\max_{v\in V} d(v,u)}$$此時稱滿足此條件的點為中心點

- 腰圍：圖$G$的腰圍g$(G)$為圖中最小環的長度，若無環則定義為$\infty$

- 哈密頓路徑/迴圈：經過每個點恰一次的路徑/迴圈\\有哈密頓迴圈的圖稱之哈密頓圖

有些匹配的性質等到**圖論part 3**時一起講，我懶得放
### Property6.1
任何圖$G$都可以是某一個圖$H$的中心。此處稱中心為$H$的中心點所構成的集合
### Property6.2
在樹$G$中，若恰存在一個中心點，則$$\mbox{diam}(G)=2\mbox{rad}(G)$$若恰存在兩個中心點，則$$\mbox{diam}(G)=2\mbox{rad}(G)-1$$
### Property6.3
對於所有連通圖$G$，皆有$$\mbox{rad}(G)\leq\mbox{diam}(G)\leq 2\mbox{rad}(G)$$
### Remark.
Peterson graph：$3-$正則圖，腰圍$=5$，$|V|=3^2+1=10$，是一種常見的反例圖，可証此圖為唯一形式。以下附圖～