9.图

1. 图的基本概念

1. 无向图 $G$ 是二元组 $< V, E>$

2. 有向图 $D$ 是二元组 $< V, E>$

3. 图的阶：顶点数，$n$ 个顶点的图称作 $n$ 阶图

4. 零图：一条边也没有的图

5. 平凡图：1阶零图

6. 无向图 $G=< V, E>$：端点，关联，相邻

7. 有向图 $D=< V, E>$：端点，关联，相邻

8. 无向图的度数(度)：顶点 $v$ 作为边的端点的次数，记作 $d(v)$

9. 有向图的度数

   • 出度：顶点 $v$ 作为边的始点的次数，记作 $d^{+}(v)$
   • 入度：顶点 $v$ 作为边的终点的次数，记作 $d^{-}(v)$
   • $d(v) = d^{+}(v) + d^{-}(v)$

10. 握手定理

• 在任何无向图中，所有顶点的度数之和等于边数的 $2$ 倍。

• 在任何有向图中，所有顶点的度数之和等于边数的 $2$ 倍；所有顶点的入度之和等于所有顶点的出度之和，都等于边数。

  推论：任何图中，奇度顶点的个数是偶数。

  $度数之和 = 奇度顶点的度数之和 + 偶数顶点的度数之和$

  • 例：已知 $n$ 阶无向图 $G$ 中有 $m$ 条边，各顶点的度数均为3，又已知 $2 n-3=m$，则 $m=9$。
    解：列方程组$\begin{cases} 2 n-3 =m \\ 3 n =2 m\end{cases}$，解出 $m$ 和 $n$ 的值。

11. 度数列

• $n$ 阶无向图：$d(v_{1}), d(v_{2}), ..., d(v_{n})$，也可表示为 $d=(d_{1}, d_{2}, ..., d_{n})$
• $n$ 阶有向图：出度列 $d^{+}(v_{1}),d^{+}(v_{2}),...,d^{+}(v_{n})$；入度列 $d^{-}(v_{1}), d^{-}(v_{2}), … , d^{-}(v_{n})$

  • 例1：一个3阶有向图的度序列是 $2,2,4$，入度序列是 $2,0,2$，出度序列是 $0,2,2$。
    解：$(2,2,4)-(2,0,2)=(0,2,2)$

  • 例2：一个无向图有5个结点，其中4个的度数是$1,2,3,4$，则第5个结点的度数不可能是$\underline{D. 5}$。
    A.$0$ B.$2$ C.$4$ D.$5$

12. 非负整数列 $d=(d_{1}, d_{2}, ..., d_{n})$ 是可图化的当且仅当 $\sum_{i=1}^{n} d_{i}$ 为偶数。
    非负整数列 $d=(d_{1}, d_{2}, ..., d_{n})$ 是简单可图化的$\begin{cases} ① \sum_{i=1}^{n} d_{i}为偶数 \\ ② d(v_{i}) \leq n-1，\Delta(G) \leq n-1 \end{cases}$ 为偶数

    • 最大度 $\Delta(G)$\
    • 最小度 $\delta(G)$
      • 例：下列四组数据中，能作为某个4阶无向简单图的度序列的为 $\underline{D}$
        A. $1,2,3,4$
        B.$2,2,2,3$
        C.$1,1,2,3$
        D.$1,1,1,3$

13. 无向完全图：设 $G$ 为 $n$ 阶无向简单图，若 $G$ 中每个顶点均与其余的 $n-1$ 个顶点相邻，记作 $K_{n}(n ≥1)$。 $n$ 阶无向完全图 $K_{n}(n ≥1)$ 的边的条数为 $\frac{n(n-1)}{2}$。

    • 例：6阶无向完全图 $K_{6}$ 的边的条数 $15$。
      解：$\frac{6 \times(6-1)}{2}=15$

---

2.⭐通路､回路与连通性

通路： 无向图 $G$ 中顶点与边的交替序列 $\Gamma=v_{i_{0}} e_{j_{1}} v_{i_{1}} e_{j_{2}} ... e_{j_{l}} v_{i_{l}}$
若 $v_{i_{0}}=v_{i_{l}}$，则称 $\Gamma$ 为回路。

$$如图，通路 v_{2} e_{2} v_{1} e_{4} v_{3} e_{5} v_{4}；回路：v_{2} e_{2} v_{1} e_{3} v_{2}$$

连通性

1. 设无向图 $G=< V, E>$，若 $u, v \in V$ 之间存在通路，则称$u, v$ 是连通的，记作 $u \sim v$。
   连通图：若无向图 $G$ 是平凡图 或$G$中任何两个顶点都是连通的。

2. 可达：有向图 $G=< V, E>$，对$u, v \in V$ 若从$u$到$v$存在通路，则称 $u$ 到$v$是可达的。
   若从$u$到$v$存在通路，且从$v$到$u$存在通路，则称$u$和$v$是相互可达的。

3. 设 $G=< V, E>$ 是有向图

   • a) 强连通的：任意两个结点间是相互可达的。
   • b) 单向连通：任意两个结点至少从一个结点到另一个结点是可达的。
   • c) 弱连通的：在略去有向边的方向后得到的无向图是连通的。
     • 例：已知有向图 $D=< V, E>$，其中 $E=\{< v_{2}, v_{1}>,< v_{4}, v_{1}>,< v_{4}, v_{3}>,< v_{2}, v_{3}>,< v_{2}, v_{4}>\}$，$V=\{v_{1}, v_{2}, v_{3}, v_{4}\}$，
       则 $D$ 为弱连通图。

图的矩阵表示

关联矩阵

• 设无向图 $G=< V, E>$，$V=\{v_{1}, v_{2}, ..., v_{n}\}$，$E=\{e_{1}, e_{2}, ..., e_{m}\}$。 令 $m_{i j}$ 为顶点 $v_{i}$ 与边 $e_{j}$ 的关联次数，则称 $(m_{i j})_{n \times m}$ 为$G$的关联矩阵，记作 $M(G)$。
  如：

  $$关联次数：m_{i j}= \begin{cases} 2,& v_{i}为环(v_i=v_j) \\ 1,& v_{i} \text{与}e_j\text{关联且非环} \\ 0,& v_{i} \text{与}e_j\text{不关联} \end{cases}$$

  $e_1,e_2,e_3,e_4,e_5$ 共5列；$v_1,v_2,v_3,v_4$ 共4行。邻接矩阵：

  $$M(G)= \left[ \begin{array}{lllll} 2 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \end{array} \right]$$

• 设有向图 $D=< V, E>$ 中无环，$V=\{v_{1}, v_{2}, ..., v_{n}\}$，$E=\{e_{1}, e_{2}, ..., e_{m}\}$。

  $$m_{i j}= \begin{cases} 1, & v_{i} 为 e_{j}\text{的始点} \\ 0, & v_{i} \text{与}e_{j}\text{不关联} \\ -1, & v_{i} 是 e_{j}\text{的终点} \end{cases}$$

  则称 $(m_{i j})_{n \times m}$ 为$D$的关联矩阵，记作 $M(D)$。

  $$关联次数：m\_{i j}= \begin{cases} 1, \\ 0, \\ -1 \end{cases}$$

  $e_1,e_2,e_3,e_4,e_5$ 共5列；$v_1,v_2,v_3,v_4$ 共4行。邻接矩阵：

$$M(D)= \left[ \begin{array}{lllll} -1 & 1 & 0 & 0 & 0 \\ 1 & -1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & -1 \\ 0 & 0 & -1 & -1 & 1 \end{array} \right]$$

邻接矩阵

• 设有向图 $D=< V, E>$，$V=\{v_{1}, v_{2}, ..., v_{n}\}$。 令 $a_{i j}^{(1)}$ 为顶点 $v_{i}$ 邻接到顶点 $v_{j}$ 的边的条数，则称 $(a_{i j}^{(1)})_{n \times n}$ 为$D$的邻接矩阵，记作 $A(D)$ 或简记为 $A$。- 例：

  $$A(D)= \left[ \begin{array}{llll} 0 & 2 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{array} \right]$$

  • 回路总数相关

    • 设 $A$ 为有向图 $D$ 的邻接矩阵，$D$ 的顶点集 $V=\{v_{1}, v_{2}, ..., v_{n}\}$。
      则 $A$ 的 $l$ 次幂 $A^{l}(l \ge 1)$ 中，元素 $a_{i j}^{(l)}$ 为 $D$ 中 $v_{i}$ 到 $v_{j}$ 长度为 $l$ 的通路数；其中 $a_{i i}^{(l)}$ 为 $v_{i}$ 到自身长度为 $l$ 的回路总数。

      $$A= \left[ \begin{array}{llll} 0&2&1&0\\ 0&0&1&0\\ 0&0&0&1\\ 0&0&1&1 \end{array} \right] \quad A^{2}= \left[ \begin{array}{llll} 0&0&2&1\\ 0&0&0&1\\ 0&0&1&1\\ 0&0&1&2 \end{array} \right] \quad$$
      $$A^{3}= \left[ \begin{array}{llll} 0&0&1&3\\ 0&0&1&1\\ 0&0&1&2\\ 0&0&2&3 \end{array} \right] \quad A^{4}= \left[ \begin{array}{llll} 0&0&3&4\\ 0&0&1&2\\ 0&0&2&3\\ 0&0&3&5 \end{array} \right]$$

      $\sum_{i=1}^{n} \sum_{j=1}^{n} a_{i j}^{(l)}$ 为 $D$ 中长度为 $l$ 的通路(含回路)总数；其中 $\sum_{i=1}^{n} a_{i i}^{(l)}$ 为 $D$ 中长度为 $l$ 的回路总数。

    示例数据：

    • $v_{2}$ 到 $v_{4}$ 长度为$1,2,3,4$的通路条数：$0,1,1,2$
    • $v_{4}$ 到自身长度为$1,2,3,4$的回路的条数：$1,2,3,5$
    • 长度小于等于4的通路的条数：$53$
    • 长度小于等于4的回路的条数：$15$

可达矩阵

• $设 D=< V, E>为有向图，V=\{v_{1}, v_{2}, ..., v_{n}\}。$

  $$p_{i j}= \begin{cases} 1 & v_{i}\text{可达}v_{j} \\ 0 & v_{i}\text{不可达}v_{j} \end{cases}$$

  $则(p_{i j})_{n \times n}为 D的可达矩阵，记作 P(D) ，简记为P$。

  注：可达矩阵主对角线上的元素全为 $1$。

  

  $$P(D)= \left[ \begin{array}{llll} 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \end{array} \right]$$

  根据邻接矩阵求可达矩阵：$P=A^{1} \lor A^{2} \lor A^{3} \lor \cdots \lor A^{n}$

  强分图为 $P \land P^{T}$，强分图的顶点集为 $\{V_{1}, V_{2}, ..., V_{n}\}$。