--- # System prepended metadata title: 圖論part1 tags: [數讀] --- --- 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. 無向圖 - 點：另稱頂點,節點，為構成圖的基本單位(可以命名)![](https://i.imgur.com/YB9lqbQ.png =300x300) - 邊：兩個點之間的關係，一條邊一定連接兩個點，以$(v_1,v_2)$代表連結兩點$v_1,v_2$的邊，若有數條邊連結兩個點，則稱之重邊，若重邊的頂點一樣，稱之自環 ![](https://i.imgur.com/0K8OYCC.png =300x300) - $G(V,E)$代表一種圖，其中$G,V,E$分別代表圖的名稱,點與邊的集合 ![](https://i.imgur.com/u2nh2mn.png =300x300) - 簡單圖：1.沒有兩條邊，它們所關聯的兩個點都相同(無重邊),2.每條邊所關聯的是兩個不同的點(無自環) ![](https://i.imgur.com/7x0kFcz.png =300x300) - 完全圖：每對點恰有一邊(塞滿邊的簡單圖)，通常以$K_n$表示$n$階完全圖 ![](https://i.imgur.com/MkhqLJ8.png =300x300) - 度：一個點的度是指與該點相關聯的總邊數，通常以$d(v)$表示點v的度，對於圖$G$中最小度與最大度，通常以$\delta(G),\Delta(G)$表示，另外度=1的點稱之葉子，度=0的點稱之孤點 - 正則圖：即每個頂點的度相同的圖 ![](https://i.imgur.com/otTO1HO.png =300x300) - 同構：若兩張圖$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)。 ![](https://i.imgur.com/Py7pTaT.png =300x300) - 環/圈：一條只有第一個和最後一個點重複的非空路徑，故稱$(v_1,v_1)$自環 ![](https://i.imgur.com/9wFW3cU.png =300x300) - 距離：兩點間的距離$d(v_1,v_2)$為$v_1$到$v_2$間的最短路徑長 - 連通：對於兩個點, 存在以其中兩點的路徑,則稱此兩點連通 - 連通圖：任兩點連通的圖 - $n-$部圖：簡單來說就是將頂點分成好幾個非空集合，而所有的邊所屬的兩個頂點來自不同的集合，通常以$G_{v_1,v_2...;E}$表示 ![](https://i.imgur.com/JEyEjov.png =300x300) 此為$K_{3,3}$(完全二部圖/完全偶圖) - 樹,森林：一種特別的圖，有三個定義且任兩個可推得第三個。若一張圖中沒有環，則稱之森林 - $|E|=|V|-1$ - 任兩點之間恰有一條簡單路徑 - 沒有環 ![](https://i.imgur.com/8cdosf3.png =300x300) - 平面圖：無邊相交的圖，以邊隔出來的區域稱之面，被隔在外的面稱之外部面，反之稱內部面 ![](https://i.imgur.com/qXjOkkq.png =300x300) #### Remark. 在路徑和環那邊，有些人會去定義"簡單路徑"為點不重複之路徑，而"路徑"本身可以有重複點，環也一樣有這樣的問題。 ## 2. 有向圖 - $(v_1,v_2)$代表從$v_1$到$v_2$的邊，圖上通常用箭頭表示$(v_1\rightarrow v_2)$，若任兩相異頂點間皆有邊，則稱之競賽圖 ![](https://i.imgur.com/1V0u8hw.png =300x300) - 出、入度：$d^+(v_k),d^-(v_k)$分別代表$v_k$的出度與入度 - 連通：對於任兩相異點$x,y$，有從$x$到$y$與從$y$到$x$的路徑,則稱此兩點連通 ![](https://i.imgur.com/Yjof8l5.png =300x300) - 強連通圖：任兩點連通的圖 ![](https://i.imgur.com/wqx4qqJ.png =300x300) --- 接下來補幾個有無向圖的通用定義 - 邊/點權 就當作是在邊或點上的賦值吧，有時稱此種圖為權重圖 - 對偶 看看例圖就好了，跟幾何中的對偶概念大致上一樣：$V\to F,E\to E,F\to V$(圖源：wiki) ![](https://i.imgur.com/hf62hUG.png =450x300) ## 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$必為此點 ![](https://i.imgur.com/7dXB55i.png =300x300) - 在競賽圖中，若任兩相異點恰有一邊，且無頂點的入度$=0$，則必存在一個簡單路徑，其中此路徑走過所有點 ![](https://i.imgur.com/Xv9bO1k.png =300x300) - 在競賽圖中$(|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$$ ![](https://i.imgur.com/XaMpCeP.png =300x300) 以此圖為例，$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$$ ![](https://i.imgur.com/v9E8cTK.png =300x300) ## 6. 更多名詞與小小性質 - (點)獨立集：若點集$S$在$G$中互相不連邊，則稱$S$為(點)獨立 - 匹配：若邊集$S$在$G$中使用到的點皆不相同，則稱$S$為一個匹配(或稱邊獨立集) - 點覆蓋：點集$S$為點覆蓋表示圖$G$中的每條邊的兩個頂點都至少有一個在$S$裡 ![](https://i.imgur.com/fY46qkb.png =300x300) - 邊覆蓋：點集$S$為邊覆蓋表示圖$G$中的每個點都至少都被一條$S$裡的邊用到 ![](https://i.imgur.com/Qq5ixiF.png =280x300) - 直徑：圖$G$的直徑長diam$(G)$為最遠的兩個點的路徑長 ![](https://i.imgur.com/QrRDKGf.png =280x300) - 半徑：圖$G$的半徑長rad$(G)$為一個點和其他點最遠距離的最小值，i.e.$$\displaystyle{\min_{v\in V}\max_{v\in V} d(v,u)}$$此時稱滿足此條件的點為中心點 ![](https://i.imgur.com/JPaneFd.png =280x300) - 腰圍：圖$G$的腰圍g$(G)$為圖中最小環的長度，若無環則定義為$\infty$ ![](https://i.imgur.com/wGyzsm8.png =280x300) - 哈密頓路徑/迴圈：經過每個點恰一次的路徑/迴圈\\有哈密頓迴圈的圖稱之哈密頓圖 ![](https://i.imgur.com/77yJ27M.png =280x300) ![](https://i.imgur.com/W09qCjP.png =280x300) 有些匹配的性質等到**圖論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$，是一種常見的反例圖，可証此圖為唯一形式。以下附圖～ ![](https://i.imgur.com/loiHYFq.png =280x300) ![](https://i.imgur.com/FsV8v7V.png =280x300) ![](https://i.imgur.com/10LgDDs.png =280x300)