owned this note
owned this note
Published
Linked with GitHub
###### tags: `課程筆記`
# 圖形理論
[TOC]
> Introduction to Graph Theory (Second Edition)
> Douglas B. West
## Ch1. Fundamental Concepts
### 1-1 What is graph?
- A loop is 一個邊的 **endpoints 相同**.
- Multiple edges are **很多邊們,有相同 endpoint**
- simple graph 沒有 **loops 跟 multiple edges**
- When u and v are the endpoints of an edge, they are **adjacent**
- complement $\bar G$ of a graph $G$
![](https://i.imgur.com/qgDqK5w.png)
- **Clique** in a graph: a set of pairwise adjacent vertices 就是全部都彼此相連的最大點點集合個數
- 相反的就是 **Independent set**,不相連的點點配對集合
- A graph G is **bipartite** if V(G) is *the union of two disjoint (possible empty) independent sets* called partite sets of G
- ![](https://i.imgur.com/uJ5NBMv.png)
- **Chromatic number** of a graph, is the minimum number of colors
- A **path** is a sequence $\{v_1 ,v_2 ,...,v_k\}$ of **distinct vertices**, such that any two consecutive vertices are adjacent
- **cycle** 就是改成頭尾相同 $\{v_0 ,v_1 ,v_2 ,..., v_k ,v_0\}$
- A graph G is **connected** if each pair of vertices in G belongs to a path
- Adjacency matrix and Incidence matrix
- ![](https://i.imgur.com/BXzKO13.png)
- **isomorphism** 表示兩個 graph 之間存在 bijection (一對一且onto) 的關係
- complete graph and complete bipartite
- ![](https://i.imgur.com/jgdmI3d.png)
- **self-complementary**:graph is isomorphic to its complement
- A **decomposition** of a graph is a list of subgraphs such that each edge appears in exactly one subgraph in the list,就是分解成不同的小 graph,但每邊只能出現一次
- **Petersen graph**
- ![](https://i.imgur.com/qMHlzRb.png)
- If two vertices are nonadjacent in Petersen graph, then they have exactly one common neighbor.
- The Petersen graph has girth 5.(周長為五)
- **automorphism** of G is an isomorphism from G to G
- G: the path with $V(G)=\{1,2,3,4\}$ and $E(G)=\{12, 23, 34\}$. G has two automorphisms: the identity permutation and the permutation $1↔4$ and $2↔3$
- $Kr,s$ has $r!s!$ automorphisms when $r≠s$. $2(r!)^2$ when $r=s$
- A graph G is **vertex-transitive** if for every pair $u,v∈V(G)$, there is an automorphism that maps u to v.
### 1-2 Paths, Cycles, and Trails
- walk is a list of vertices and edges
- A **trail** is a walk with no repeated edge,不能重複邊
- A **circuit** is a closed trail
- 而 path 跟 cycle 不能重複點
- The **length** of a walk, trail, path, or cycle is its *number of edges*. A walk or trail is **closed** if its endpoints are the same
- ![](https://i.imgur.com/lrpypfz.png)
![](https://i.imgur.com/1WL1s4M.png)
- Every u, v-walk contains a u, v-path.
![](https://i.imgur.com/r03hVKj.png)
- A graph G is **connected** if it has a u, v-path whenever $u, v∈V(G)$
- The **components** of a graph G are its maximal connected subgraphs
- Every graph with $n$ vertices and $k$ edges has at least $n-k$ components.
- A **cut-edge or cut-vertex** of a graph is an edge or vertex whose deletion increases the number of components.
- The **induced subgraph** $G[T]$ consists of $T⊆V(G)$ and all edges whose endpoints are contained in T. 就是有選擇的點的邊全都要,比較嚴格
- A graph is bipartite if and only if it has *no odd cycle*.
- ![](https://i.imgur.com/H7G3ICx.png)
- An **Eulerian circuit or Eulerian trail** in a graph is a circuit or trail (不能重複邊) containing all the edges
- If every vertex of a graph G has degree at least 2, then G contains a cycle.
![](https://i.imgur.com/nL0MiVA.png)
- For a connected nontrival graph with exactly $2k$ oddvertices, the **minimum number of trails that decompose** it is $max\{k, 1\}$.
- 一個 trail 能處理全部的 evenvertices+一組兩個 oddvertex
- 剩下的 oddvertex 兩個兩個一組連起來
### 1-3 Vertex Degree and Counting
- The degree of vertex v in a graph G, or d(v), is the number of **edges incident to v**
- The maximum degree is $∆(G)$,
- The minimum degree is $δ(G)$,
- G is **regular** if $∆(G) = δ(G)$,
- **k-regular** if the common degree is k.
- The **neighborhood** of v, $N_G(v)$ or $N(v)$
- The **order** of a graph G, $n(G)$, is the number of vertices of G
- The **size** of a graph G, $e(G)$, is the number of edges in G
- **Degree-Sum Formula**
- ![](https://i.imgur.com/O3KDTpq.png)
- The minimum number of edges in a connected graph with n vertices is n-1
- If G is a simple n-vertex graph with **$δ(G) \geq \frac{(n-1)}{2}$** then G is connected
- ![](https://i.imgur.com/ixiyGHr.png)
- The maximum number of edges in an n-vertex **triangle-free** simple graph is $\lfloor \frac{n^2}{4}\rfloor$
- ![](https://i.imgur.com/olC0c6G.png)
- The nonnegative integers $\{d_1, d_2,...,d_n\}$ are the vertex degrees of some graph if and only if $\sum d_i$ is even
- ![](https://i.imgur.com/JqY4yKX.png)
### 1-4 Directed Graphs
- A **directed graph or digraph G** is a triple consisting of a vertex set V(G), an edge set E(G), and a function assigning each edge an **ordered** pair of vertices
- An edge is from its tail to its head.
- A **digraph is simple** if each ordered pair is the head and tail of at most one edge
- A **digraph is a path** if it’s a simple digraph whose vertices can be linearly ordered
- The **underlying graph** of a digraph D is the graph G obtained by treating the edges of D as unordered pairs(就是把 digraph 的方向去掉)
![](https://i.imgur.com/WFfQWPR.png)
- **adjacency matrix A(G) and incidence matrix M(G)**
![](https://i.imgur.com/Lcsbck1.png)
- An n-vertex path has n **strong components**, but a cycle has only one
![](https://i.imgur.com/fgB6ttF.png)
- In a digraph G, $\sum_{v∈V(G)}d^+(v)=e(G)=\sum_{v∈V(G)}d^-(v)$
- **Eulerian trail** in a digraph is a trail containing all edges
- **Eulerian circuit** is a closed trail containing all edges
- If G is a digraph with $δ^+(G) \geq 1$, then G contains a cycle,就是 Min out-edge 至少一
![](https://i.imgur.com/t1G2HFd.png)
- **orientation** of a graph G is a digraph D obtained from G by choosing an orientation (就是選一個方向) for each edge
- **tournament** is an orientation of a complete graph
![](https://i.imgur.com/jAWd8C6.png)
## Ch2. Trees and Distance
### 2-1 Basic Properties
- A graph with no cycle is **acyclic**
- A **tree** is a connected acyclic graph
- A **leaf** (or pendant vertex) is a vertex of degree 1
- Every tree with **at least two vertices** has at least two leaves.
- **Deleting a leaf** from an n-vertex tree produces a tree with n-1 vertices
- n-vertex graph G, the following are equivalent.
- G is *connected* and *no cycles*.
- G is *connected* and has *n-1 edges*.
- G has *n-1 edges* and *no cycles*.
- G has *no loops* and has, for exactly one *u,v-path*
- Every edge of a tree is a **cut-edge**.
- **Adding one edge** to a tree forms exactly one cycle.
- Every connected graph contains **a spanning tree**.
- If T and T’ are spanning trees of a connected graph G and $𝑒∈𝐸(𝑇)−𝐸(𝑇′)$ ,then there is an edge $𝑒′∈𝐸(𝑇′)−𝐸(𝑇)$ such that $𝑇′+𝑒−𝑒′$ is a spanning tree of G. 就是加別人、扣自己,一樣是樹。
![](https://i.imgur.com/rJ9EnJO.png)
- **distance** from u to v, $d_G(u,v)$, is the $min$ length of a u,v-path.
- **eccentricity** of a vertex $u$, $ε(u)$, is $max_{v∈V(G)}d(u,v)$
- **diameter** of a graph G, diam G, is $max_{u,v∈V(G)}d(u,v)$,也是 $max_{u∈V(G)}ε(u)$
- **radius** of a graph G, rad G, is $min_{u∈V(G)}ε(u)$
- In the graph below, each vertex is labeled with its eccentricity. The radius is 2, the diameter is 4, and the length of the longest path is 7.
> ![](https://i.imgur.com/OkThkAS.png)
- If G is a simple graph, then $𝑑𝑖𝑎𝑚𝐺≥3⇒𝑑𝑖𝑎𝑚\bar{𝐺}≤3.$
- When $𝑑𝑖𝑎𝑚𝐺≥3⇒𝑑𝑖𝑎𝑚\bar{𝐺}≤3.$ there exist nonadjacent vertices $𝑢,𝑣∈𝑉(𝐺)$ with no common neighbor.
- ![](https://i.imgur.com/rUeGby5.png)
- The **center** of a graph G is the subgraph induced by the vertices of minimum eccentricity.
- The center of a tree is a vertex or an edge.
- **Wiener index** of G is $D(G)= \sum_{u,v∈V(G)}d_G(u,v)$,也就是兩兩點 length 的總和
- minimized by stars and maximized by paths
- **star**: A tree has n-1 edges, it has n-1 pairs of vertices at distance 1, and all other pairs have distance at least 2 $\Rightarrow$ star minimizes $D(T)$.
- consider a leaf $x$ in $T$ with its neighbor $v$. If all other vertices have distance 2 from $x$, $x∈N(v) \Rightarrow T$ is a **star**.
$D(K_{1,n-1}) = (n-1) +2{n-1 \choose 2} = (n-1)^2$
![](https://i.imgur.com/z1zNUYa.png)
- **path**: u is an endpoint of $P_n$
- $D(P_n) = D(P_{n-1}) + C{n \choose 2} \Rightarrow D(P_n) = C{n+1 \choose 3}$
- If H is a subgraph of G,
- then $dG (u, v) \leq dH (u, v)$,有可能最短路徑沒有包含
- and $D(G) \leq D(Pn)$
- so $D(G) \leq D(T) \leq D(Pn)$
### 2-2 Spanning Trees and Enumeration
- **Prüfer code**
- Iteration: At the ith step, delete the least remaining leaf, and let ai be the neighbor of this leaf,刪掉最小葉子,並記下葉子旁邊那個
> ![](https://i.imgur.com/RUSuiy4.png)
> ![](https://i.imgur.com/TnIcFGT.png)
- 因此若,給 size n 問 tree 可能性,就是**Prüfer code** 的所有可能:Cayley’s Formula [1889]). For a set $S \subseteq N$ of **size n**, there are $n^{n-2}$ trees with vertex set S,就是a數列所有的可能性
- 給所有點的 degree:Given positive integers $\{d1,…,dn\}$ there are $\frac{(n-2)!}{\Pi(d_i-1)!}$,排列數除以可交換數
> ![](https://i.imgur.com/GpiGhOn.png)
- Let $\tau(G)$ denote the number of spanning trees of a graph G. If $e \in E(G)$ is not a loop, then $\tau(G)= \tau(G\in e)+\tau(G\notin e)$.
![](https://i.imgur.com/cL5ixnU.png)
- **Matrix Tree Theorem**
- ![](https://i.imgur.com/pI8pMPT.png)
- **graceful labeling**
- ![](https://i.imgur.com/BtGQjoM.png)
- If a tree T with m edges has a graceful labeling, then $K_{2m+1}$ has a decomposition into $2m+1$ copies of T.
- ![](https://i.imgur.com/dVCqtVX.png)
- A **caterpillar** is a tree in which a simple path (the spine) is incident to (or contain) every edge.就是有一條能到達每一個點的脊椎。
- ![](https://i.imgur.com/H63eTEE.png)
- A tree is a caterpillar if and only if it does not contain the tree Y.
- A **branching or out-tree** is an orientation of a tree having a root of indegree 0 and all other vertices of indegree 1.
- An **in-tree** is an out-tree with edges reversed.
- In a **strong digraph**, every vertex is the root of an out-tree (and an in-tree)
> ![](https://i.imgur.com/0E8SOiM.png)
> ![](https://i.imgur.com/CCEXBGi.png)
### 2-3 Optimizations and Trees
- **Kruskal**'s Algorithm
>Maintain an acyclic spanning subgraph H, enlarging it by edges with low weight to form a spanning tree. Consider edges in nondecreasing order of weight, breaking ties arbitrarily
- ![](https://i.imgur.com/an4oiPe.png)
- **Dijkstra**'s Algorithm
- ![](https://i.imgur.com/WYp5j8g.png)
- **BSF** is an unweighted graph Dijkstra
## Ch3. Matchings and Factors
### 3-1 Matchings and Factors
- **Matching** is a set of non-loop edges with no shared endpoints
- 點 **saturated** by M 就是點在 matching 的邊上
- A **perfect matching** in a graph is a matching that **saturates every vertex**
- A **maximal** matching in a graph is a matching that cannot be enlarged by adding an edge
- A **maximum** matching is a matching of maximum size among all matchings in the graph
- Maximal $\neq$ maximum
- ![](https://i.imgur.com/XZwoVgj.png)
- 兩張圖皆為 maximal 但不是 maximum
- **M-alternating path** is a path that *alternates between edges* in M and edges not in M `就是path上的連續邊邊,依序出現是 M 與非 M`
- **M-augmenting path** is an M-alternating path whose 兩端都沒有被 M 碰到
- **symmetric difference**:For two matchings M and M’, $M \Delta M' = (M-M')\cup(M'-M)$
- ![](https://i.imgur.com/0xd67ca.png)
- Every component of the **symmetric difference** of two matchings is a path or an even cycle.
- $F = M \Delta M'$ and $\Delta F \leq2$(就是 Component 每個最大的 degree 為 2)
- every component of $F$ is a path or a cycle
- A matching $M$ in a graph $G$ is a **maximum matching** in $G$ if and only if $G$ has **no M-augmenting path**
- **`Hall's condition`**:An $X$, $Y$-bigraph $G$ has a matching that **saturates $X$** iff $|N(S)| \geq|S|$ for all $S \subseteq X$ `對面鄰居永遠都比我多,那我一定可以被 saturated by a matching`
- ![](https://i.imgur.com/HieqYfZ.png)
- 因此 For $k>0$, every k-regular bipartite graph has a *perfect matching*.
- A **vertex cover** of a graph G is a set that contains at least one endpoint of every edge.
- no vertex can cover two edges of a matching, $|matching|\leq|vertex\ cover|$
- ![](https://i.imgur.com/hzQXI8S.png)
- If G is a bipartite graph, then the **maximum size of a matching** in G equals **the minimum size of a vertex cover** of G
- The independence number of a graph is the **maximum size of an independent set** of vertices
- ![](https://i.imgur.com/kAOTxsZ.png)
- Def:
:::success
- maximum size of **independent set $\alpha(G)$**
- maximum size of **matching $\alpha\prime(G)$**
- minimum size of **vertex cover $\beta(G)$**
- minimum size of **edge cover $\beta\prime(G)$**
:::
- Property:
:::info
- In a graph G, $S \subseteq V(G)$ is an **independent set** iff $\bar S$ is a **vertex cover**, and hence $\alpha(G) + \beta(G) = n(G)$
- If G is a graph **without isolated vertices**, then $\alpha\prime(G) + \beta\prime(G) = n(G)$
- If G is a **bipartite graph** with **no isolated vertices**, than $\alpha(G) = \beta\prime(G)$
:::
- In a graph $G$, a set $S \subseteq V(G)$ is a **dominating set** if every vertex not in $S$ has a neighbor in $S$ `我跟我的鄰居全包了`
- The **dominating number** $\gamma(G)$ is the minimum size of a dominating set in G.
- When a graph G has no isolated vertices, every vertex cover is a dominating set, so $\gamma(G) \leq \beta(G)$
- ex:$\gamma(K_n)=1 ;\beta(K_n)=n-1$
### 3-2 Algorithms and Applications
- **Maximum Bipartite Matching**
> ![](https://i.imgur.com/8QswxS3.png)
> ![](https://i.imgur.com/ieULfqZ.png)
![](https://i.imgur.com/uB4jEn0.png)
![](https://i.imgur.com/p0n6gVu.png)
![](https://i.imgur.com/6HbMnpV.png)
- [AALG5: Flow networks, maximum bipartite matching example](https://www.youtube.com/watch?v=x2BdRml5lmc)
- Repeated applying the Augmenting Path Algorithm to a bipartite graph produces a **matching and a vertex cover of equal size**.
- **Weighted Bipartite Matching**
- **transversal** of an n-by-n matrix consists of n positions, one in each row and each column
- **Assignment Problem** is finding a transversal with maximum sum
> ![](https://i.imgur.com/UoLgkTK.png)
> ![](https://i.imgur.com/1qDlieM.png)
> ![](https://i.imgur.com/5xs3EGz.png)
- **The minimum weighted cover** problem is that of finding a cover of minimum cost
- **Stable Matchings**
- 用 greedy 來解即可
> ![](https://i.imgur.com/UtvjYSy.png)
> ![](https://i.imgur.com/1qPYCB9.png)
### 3-3 Matchings in General Graphs
- Def:
- A **factor** of a graph G is a spanning subgraph of G.
- A **k-factor** is a spanning k-regular subgraph.
- An **odd component** of a graph is a component of odd order.
- The number of odd components of H is **o(H)**.
- A graph G has a **1-factor** iff $o(G-S) \leq |S|$ for every $S \subseteq V(G)$
- ![](https://i.imgur.com/K7iuIte.png)
- ![](https://i.imgur.com/mgehMDH.png)
- ![](https://i.imgur.com/Cqdc4vz.png)
- ![](https://i.imgur.com/1fjzaDK.png)
- Every $3$-regular graph with no cut-edge has a $1$-factor
- ![](https://i.imgur.com/KzTWS8x.png)
- Every regular graph of even degree has a $2$-factor
- ![](https://i.imgur.com/VR1e7Qx.png)
- ![](https://i.imgur.com/k3iz6K3.png)
- **f-factors of graphs**
- Given a function $f:V(G) \rightarrow N \cup \{0\}$ an $f$-factor of a graph $G$ is a spanning subgraph $H$ such that $d_H(v) = f(v)$ for all $v \in V(G)$
- ![](https://i.imgur.com/RjCksFP.png)
- A graph $G$ has an f-factor iff the graph $H$ constructed from $G$ and $f$ has a 1-factor
- ***`Edmond’s Blossom Algorithm`***
- [blossom algorithm 影片參考](https://www.youtube.com/watch?v=3roPs1Bvg1Q&t=8s)
> ![](https://i.imgur.com/BmEeTcW.png)![](https://i.imgur.com/gmpmLtp.png)![](https://i.imgur.com/qrMFEIY.png)![](https://i.imgur.com/nDMB3nh.png)
## Ch4. Connectivity and Paths
### 4-1 Cuts and Connectivity
- A **separating set** or **vertex cut** of a graph G is a set $S \subseteq V(G)$ such that $G-S$ has more than one component
- The **connectivity** $k(G)$ of $G$ is the minimum size of a vertex set $S$ such that $G-S$ is disconnected or has only one vertex.`就是最少要拿掉 k 點,才能讓圖變 disconnected`
- A graph with more than two vertices has **connectivity 1 iff it is connected and has a cut vertex**
- A graph G is $k-connected$ if its connectivity is at least k
- $k(K_n) = n-1$
- $k(G) \leq n(G) - 2$ when $G$ is not a complete graph
- $k(K_{m,n}) = min\{m, n\}$
- The connectivity of $K_{3,3}$ is $3$; the graph is $1$-connected, $2$-connected, and $3$-connected, but not $4$-connected.
- A graph with more than one vertex has connectivity zero iff it is disconnected. `因為本身就是 disconnected`
- $k(K_1) = 0$
- An n-dimensional hypercube denoted by $Qn$, where the number of vertices are $N = 2n$, and we use an n-bit binary string to denote a node.
- $V(Q2) = \{00,01,10,11\}$
- ![](https://i.imgur.com/nR7eSPv.png)
- ![](https://i.imgur.com/NZxtgnH.png)
- ![](https://i.imgur.com/DWBi4qM.png)
- ![](https://i.imgur.com/3FcHSWM.png)
- ![](https://i.imgur.com/FByrUyf.png)
- Let $Q_k$ be a hypercube. Then, $k(Q_k) = k$
- ***`Harary graphs`*** $H_{k,n}$
- ![](https://i.imgur.com/NDwf77k.png)
- ![](https://i.imgur.com/leHbQSr.png)
:::danger
:100: $k(H_{k,n}) = k$ and hence the **minimum number of edges** in a $k$-connected graph on n-vertices is $\lceil \frac{kn}{2} \rceil$
:::
- A **disconnecting set** of edges is a set $F \subseteq E(G)$ such that $G-F$ has more than one component `點是 separating set`
- A graph is **k-edge-connected** if every disconnecting set has at least $k$ edges.
- The **edge-connectivity** $k\prime(G)$ of $G$ is the minimum size of $G$ disconnecting set.
- Given $S,T \subseteq V(G)$ let $[S, T]$ for the set of edges having one endpoint in $S$ and the other in $T$
- An **edge cut** is an edge set of the form $[S, \bar S]$ , where $S$ is a nonempty proper subset of $V(G)$ and $\bar S = V(G) - S$
- ![](https://i.imgur.com/eDMxuOF.png)
- Every edge cut is a disconnecting set
- Every minimal disconnecting set of edges is an edge cut
- If $G$ is a simple graph, then $k(G) \leq k\prime(G) \leq \delta(G)$
- ![](https://i.imgur.com/2KZapKp.png)
- If G is a 3-regular graph, then $k(G) = k\prime(G)$
- If $S$ is a set of vertices in a graph $G$, then $|[S,\bar S]| = \sum_{v \in S}d(v) - 2e(G[S])$
- If $G$ is a simple graph and $|[S,\bar S]| < \delta(G)$ for some nonempty proper subset $S$ of $V(G)$, then $|S| > \delta(G)$
> ![](https://i.imgur.com/xsycPbI.png)
- A **bond** is a minimal nonempty edge cut
- If $G$ is a connected graph, then an edge cut $F$ is a bond iff $G-F$ has exactly two components
:::warning
:bulb: *disconnecting set -> edge cut -> bond*
:::
- A **block** of a graph $G$ is a **maximal connected subgraph** of $G$ that has **no cut-vertex**
- If $G$ itself is connected and has no cut-vertex, then $G$ is a block `一個點不足以拆散我們`
- ![](https://i.imgur.com/qIRAtbG.png)
### 4-2 k-connected Graphs
- **Two paths** from $u$ to $v$ are **internally disjoint** if they have no common internal vertex
- A graph $G$ having at least **three vertices is 2-connected** iff for each pair $u, v \in V(G)$ there exist internally disjoint $u,v$-path in $G$.
- If $G$ is a $k$-connected graph, and $G’$ is obtained from $G$ by **adding a new vertex $y$ with at least $k$ neighbors** in $G$, then $G’$ is $k$-connected
- $G\prime =$ ![](https://i.imgur.com/Fq4Cfil.png)
- For a graph $G$ with **at least three vertices**, the following conditions are **equivalent**.
- $G$ is connected and has no cut-vertex.
- For all $x, y \in V(G)$ there are internally disjoint $x,y$-paths.
- For all $x, y \in V(G)$ there is a cycle through $x$ and $y$.
- $\delta(G) \geq 1$ and every pair of edges in $G$ lies on a common cycle.
- In a graph $G$, **subdivision** of an edge $uv$ is the operation of replacing $uv$ with a path $u, w, v$ through a new vertex $w$
- ![](https://i.imgur.com/xqykM4y.png)
- An **ear** of a graph $G$ is a maximal path whose internal vertices have degree 2 in $G$. `不是只有 degree 2 是有 degree 2`
- An ear decomposition of G is a decomposition $P_0, P_1, ...,P_k$ such that $P_0$ is a cycle and $P_i$ for $i \geq 1$ is an ear of $P_0 \cup P_1 \cup ... \cup P_k$
- ![](https://i.imgur.com/38dQh23.png)
- A graph is $2$-connected iff it has an ear decomposition.
- Furthermore, every cycle in a $2$-connected graph is the initial cycle in some ear decomposition.
- ![](https://i.imgur.com/tzWy2sm.png)
- A graph is **2-edge-connected** iff it has a **closed-ear decomposition**, and every cycle in a 2-edge-connected graph is the initial cycle in some decomposition
- A graph has a **strong orientation** iff it is 2-edge-connected
- ![](https://i.imgur.com/zfHyqgp.png)
- (Menger 1927). If $x,y$ are vertices of a graph $G$ and $xy \notin E(G)$, then the **minimum size of an $x,y$-cut (separating set)** equals the maximum number of **pairwise internally disjoint $x,y$-paths $\lambda(x, y)$**
> ![](https://i.imgur.com/voUVAjd.png)
> 上左圖:$\{b,c,z,d\}$ is an $x,y$-cut, $\kappa(x, y) = \lambda(x, y) = 4$
> 上右圖:$\{b,c,x\}$ is an $w,z$-cut, $\kappa(w, z) = \lambda(w, z) = 4$
- ![](https://i.imgur.com/5Vol9Oq.png)
- Substituting “digraph” for “graph” yields the definition of line digraph.
> ![](https://i.imgur.com/XP7NFUz.png)
- If $x$ and $y$ are distinct vertices of a graph or digraph $G$, then the minimum size of an $x,y$-disconnecting set of edges equals the maximum number of pairwise edge-disjoint $x,y$-paths `就是上面的邊的版本`
- **Deletion of an edge** reduces connectivity by at most 1.
- A graph is $k$-connected iff it has at least $k+1$ vertices and, for every choice of **x, U with $|U| \geq k$ it has an x, U-fan** of size k
- Suppose G satisfies the fan condition. For $v\in V(G)$ and $U = V(G)-\{v\}$ there is a $v,U$-fan of size $k$
### 4-3 Newtworks Flow Problems
- ![](https://i.imgur.com/oRH1GkY.png)
- ![](https://i.imgur.com/9D1bfNw.png)
- ![](https://i.imgur.com/tZOIth8.png)
- ![](https://i.imgur.com/i6Gu1Kt.png)
- ![](https://i.imgur.com/j8etOvs.png)
> ![](https://i.imgur.com/cirxWQb.png)
- [補充影片:Ford-Fulkerson in 5 minutes](https://www.youtube.com/watch?v=Tl90tNtKvxs)
- *`Max-flow Min-cut Theorem`*:In every network, the maximum value of a feasible flow equals the minimum capacity of a source/sink cut.
> ![](https://i.imgur.com/Ht7zHaq.png)
## Ch5. Coloring of Graphs
### 5-1 Vertex Coloring and Upper Bounds
- A **k-coloring** of a graph G is a labeling $f: V(G)\rightarrow S$ where $|S|=k$ (often we use $S=[k]$), and the labels are colors.
- A k-coloring is **proper** if adjacent vertices have different labels.
- A graph is **k-colorable** if it has a proper k-coloring.
- The **chromatic number $\chi(G)$** is the least k such that G is k-colorable.
> ![](https://i.imgur.com/9Hw6LR7.png)
The chromatic number of the Petersen graph is 3
- A graph G is **k-chromatic** if $\chi(G)=k$
- If $\chi(H) < \chi(G) = k$ for every proper subgraph H of G, then G is **color-critical or k-critical**
- $K_2$ is the only 2-critical graph.
- $K_1$ is the only 1-critical graph.
- The 3-critical graphs are the odd cycles.
- If $H$ is a k-critical graph, then $\delta(H) \geq k-1$
- The **clique number** $\omega(G)$ of a graph G, is the maximum size of a set of pairwise adjacent vertices (clique) in G. `就是全部都彼此相連的最大點點集合個數`
- ![](https://i.imgur.com/lds3Y21.png)
- ![](https://i.imgur.com/nGG5bxc.png)
- $\chi(G\times H)=max\{\chi(G), \chi(H)\}$
- [**Greedy coloring**](https://www.youtube.com/watch?v=vGjsi8NIpSE) relative to a vertex ordering $v_1,...,v_n$ of $V(G)$ is obtained by coloring vertices in the order $v_1,...,v_n$, assigning to $v_i$ the smallest-indexed color not already used on its lower-indexed neighbors.
>- $\chi(G) \leq \Delta(G) + 1$,加1表示加上自己點的顏色
>- ![](https://i.imgur.com/LYm7A6M.png)
- An **interval representation** of a graph is a family of intervals assigned to the vertices so that *vertices are adjacent iff the corresponding intervals intersect*
> ![](https://i.imgur.com/Ffg3snZ.png)
> If $G$ is an interval graph, then $\chi(G) = \omega(G)$,$\omega(G)$
> :::info
> 就是全部都彼此相連的最大點點集合個數;圖形上就是最多重疊點的數量
> :::
- If $H$ is a k-critical graph, then $\delta(H) \geq k-1$
> ![](https://i.imgur.com/zvNPLIi.png)
- If $D$ is an orientation of $G$ with longest path length $l(D)$, then $\chi(G) \leq 1 +l(D)$. Furthermore, equality holds for some orientation of $G$.
> ![](https://i.imgur.com/LShm9oj.png)
- Brook's Theorem:If $G$ is a connected graph other than a complete graph or an odd cycle, then $\chi(G) \leq \Delta(G)$
### 5-2 Structure of k-chromatic Graphs
- ***`Mycielski’s construction`***
1. Beginning with $G$ having vertex set $\{v_1,v_2,…,v_n\}$, add vertices $U=\{u_1,u_2,…,u_n\}$ and One more vertex $w$
2. Add edges to make $u_i$ adjacent to all of $N_G(v_i)$, and finally let $N(w) = U$
> ![](https://i.imgur.com/WwafP44.png)
- From a $k$-chromatic triangle-free graph $G$, Mycielski’s construction produces a $k+1$-chromatic triangle-free graph $G’$.
- Every $k$-chromatic graph with $n$ vertices has at least $C(k, 2)$ edges. Equality holds for a complete graph plus isolated vertices.
- :::success
每種兩兩顏色組合最少都會有一個邊
:::
- A ***`complete multipartite`*** graph is a simple graph $G$ whose vertices can be partitioned into sets so that $u \leftrightarrow v$ iff $u$ and $v$ belong to different sets of the partition.
- Every component of $\bar G$ is a complete graph
- A complete $k$-partite graph is $k$-chromatic
- :::info
一個 partite set 就用一種顏色
:::
- When $k \geq 2, K_{n_1, n_2,...,n_k}$ is used to denote the complete $k$-partite graph with partite sets of sizes $n_1, n_2,...,n_k$ and complement $K_{n_1} + K_{n_2} +...+ K_{n_k}$
- ![](https://i.imgur.com/X9pMBPi.png)
- Among simple $r$-partite graphs with $n$ vertices, the *Turán* graph is the unique graph with the most edges
- Among the $n$-vertex simple graphs with no $r+1$-clique, $Tn,r$ has the maximum number of edges
- A graph G with no isolated vertices is **color-critical** iff $\chi(G-e) < \chi(G)$ for every $e \in E(G)$
- Proposition. Let G be a $k$-critical graph.
- For $v \in V(G)$ there is a proper $k$-coloring of $G$ in which the color on $v$ appears nowhere else, and the other colors must be appear on $N(v)$.
- For $e \in E(G)$ every proper $k-1$-coloring of $G-e$ gives the same color to the two endpoints of $e$
- Let $G$ be a graph with $\chi(G) > k$ and let $X$, $Y$ be a partition of $V(G)$. If $G[X]$ and $G[Y]$ are $k$-colorable, then the edge cut $[X,Y]$ has at least $k$ edges
- :::warning
至少把兩邊相同顏色的 k 個串聯起來
:::
- Every k-critical graph is k-1-edge-connected`(every disconnecting set has at least k-1 edges)`
### 5-3 Enumerative Aspects
- Given $k\in N$ and a graph $G$, the value $\chi(G;k)$ is the number of proper colorings $f:V(G) \rightarrow [k]$ The set of available colors is $[k]=\{1, 2,...,k\}$; the $k$ colors need not all be used in a coloring $f$. Changing the names of the colors that are used produces a different coloring.
- ![](https://i.imgur.com/mpDKX4d.png)
- If T is a tree with $n$ vertices, then $\chi(T:k) = k(k-1)^{n-1}$
- ![](https://i.imgur.com/25nRdZG.png)
- 第一個是 root 有 k 個選擇,其他點都 k-1 個選擇
- ![](https://i.imgur.com/f7zmnjv.png)
- *Chromatic recurrence*:If $G$ is a simple graph and $e \in E(G)$, then $\chi(G;k) = \chi(G-e;k) - \chi(G\cdot e;k)$
- ![](https://i.imgur.com/yZIsAgu.png)
> eg. $\chi(C_4;k) = \chi(P_4;k) - \chi(K_3;k) = k(k-1)(k^2-3k+3)$
> ![](https://i.imgur.com/cFJerdh.png)
- The chromatic polynomail $\chi(G;k)$ has degree $n(G)$, with integer coefficients alternating in sign and beginning $1,-e(G),…$*`prove by induction`*
- A vertex of $G$ is **simplicial** if its neighborhood in $G$ induces a clique
- A **simplicial elimination ordering** (perfect elimination orderings) is an ordering $v_n,...,v_1$ for deletion of vertices so that each vertex $v_i$ is a simplicial vertex of the remaining graph induced by $\{v_1, v_2,...,v_i\}$ `從 1 2 依序降到 n`
- **Chromatic polynomial** is $k(k-1)(k-1)(k-2)(k-3)(k-2)$ `就是每一點在 elimination 之後能夠塗的顏色`
> ![](https://i.imgur.com/mhUnsWS.png)
- A **chord** of a cycle $C$ is an edge not in $C$ whose endpoints lie in $C$.
- A *chordless cycle* in $G$ is a cycle of length at least 4 in $G$ that has no chord.
- A graph $G$ is **chordal** if it is simple and has *no chordless cycle*
:::info
🔼 圖形就會由很多三角形組成
:::
- For every vertex $x$ in a chordal graph $G$, there is a simplical vertex of $G$ farthest from $x$
- A simple graph has a simplicial elimination ordering iff it’s a chordal graph
- A graph is **perfect** if $\chi(H) = \omega(H)$ `(clique number)` for every induced subgraph $H \subseteq G$
- Clique cover number $\theta(G)$ of a graph $G$ is the minimum number of cliques in $G$ needed to cover $V(G)$
- $\theta(G) = \chi(\bar G)$ `猶如 complete multipartite`
- A family of graphs $G$ is **hereditary** if every induced subgraph of a graph in $G$ is also a graph in $G$
- Chordal graphs are perfect.
- A **transitive orientation** of a graph $G$ is an orientation $D$ such that whenever $xy$ and $yz$ are edges in $D$, also there is an edge $xz$ in $G$ that is oriented from $x$ to $z$ in $D$.
- A simple graph $G$ is **comparability** graph if it has a transitive orientation.
- Comparability graphs are perfcet