基础图
编辑一个简单无向图，实时观察顶点度数、握手定理和图的基本性质。
当前知识点
基础图
图由顶点集 V 和边集 E 组成。你可以在画布上添加顶点、连边、删除元素，并观察图的阶、边数和度数变化。
邻接矩阵
编辑矩阵单元格自动增删图中的边
编辑一个简单无向图，实时观察顶点度数、握手定理和图的基本性质。
图由顶点集 V 和边集 E 组成。你可以在画布上添加顶点、连边、删除元素，并观察图的阶、边数和度数变化。
编辑矩阵单元格自动增删图中的边
无向图 \(G = \langle V, E \rangle\)，边是无序对 \((u, v)\)。
有向图 \(D = \langle V, E \rangle\)，边是有序对 \(\langle u, v \rangle\)。
\(n\) 阶图：\(n\) 个顶点。零图：\(E = \emptyset\)。平凡图：1 阶零图。空图：\(V = \emptyset\)。
无向图 \(d(v)\)：\(v\) 作为边的端点的次数之和。
有向图：出度 \(d^+(v)\)、入度 \(d^-(v)\)，\(d(v) = d^+(v) + d^-(v)\)。
最大度 \(\Delta\)、最小度 \(\delta\)。悬挂顶点（度 1），悬挂边。
定理 6.1 任何图（无向或有向），所有顶点度数之和等于边数的两倍：
\[\sum_{i=1}^{n} d(v_i) = 2m\]
推论： 奇度顶点的个数必为偶数。
定理 6.2 有向图中，出度之和 = 入度之和 = 边数：
\[\sum_{i=1}^{n} d^+(v_i) = \sum_{i=1}^{n} d^-(v_i) = m\]
平行边： 关联同一对顶点的多条边（重数）。
多重图： 含平行边的图。
简单图： 既无平行边也无环的图。
\(n\) 阶无向完全图 \(K_n\)：任何顶点都与其余 \(n-1\) 个顶点相邻。
\(n\) 阶有向完全图：任意两顶点间有双向边。
子图： \(V' \subseteq V\) 且 \(E' \subseteq E\)
生成子图： \(V' = V\)
导出子图： \(G[V_1]\) — 取顶点子集及所有两端在其中的边；\(G[E_1]\) — 取边子集及关联顶点。
补图： 简单图 \(G\) 的补图 \(\bar{G}\)，边集为 \(K_n\) 去掉 \(G\) 的边。
存在双射 \(f: V_1 \to V_2\) 保持边关系与重数。必要条件：顶点数、边数、度数列相同。尚无多项式时间充要算法。
\(\Gamma = v_0 e_1 v_1 \dots e_l v_l\)，\(l\) 为长度。
边互不相同 → 简单通路；顶点互不相同（除首尾） → 初级通路（路径）。闭合 → 回路 / 圈。
定理 6.3 \(n\) 阶图中，若 \(u\) 到 \(v\)（\(u \neq v\)）有通路，则存在长度 \(\leq n-1\) 的通路。
推论： 存在长度 \(\leq n-1\) 的初级通路。
定理 6.4 若存在 \(v\) 到自身的回路，则存在长度 \(\leq n\) 的回路。
推论： 若存在简单回路，则存在长度 \(\leq n\) 的初级回路。
连通图： 任意两顶点间都有通路。连通分支数 \(p(G)\)。
有向图：强连通（双向可达）、单向连通（至少一方可达）、弱连通（基图连通）。
割点： 删除后 \(p(G - v) > p(G)\) 的顶点。
桥（割边）： 删除后 \(p(G - e) > p(G)\) 的边。
有向图 \(D\) 的邻接矩阵 \(A(D)\)：\(a_{ij}\) 为 \(v_i\) 邻接到 \(v_j\) 的边数。
行和 = \(d^+(v_i)\)，列和 = \(d^-(v_i)\)。
定理 6.5 \(A^l\) 中 \((i,j)\) 元素 = \(v_i\) 到 \(v_j\) 长度为 \(l\) 的通路数。\(B_r = A + A^2 + \dots + A^r\) 中元素为长度 \(\leq r\) 的通路数。
可达矩阵 \(P(D)\)：\(p_{ij}=1\) 当 \(v_i\) 可达 \(v_j\)（主对角线恒为 1）。
无向图 \(M(G)\)：\(m_{ij}\) 为关联次数。每列恰有两个 1 或一个 2。行和 = \(d(v_i)\)。全 0 行 ↔ 孤立点。平行边 ↔ 相同列。
有向图（无环） \(M(D)\)：\(m_{ij}=1\)（始点）、\(-1\)（终点）、\(0\)（不关联）。每列恰有一个 1 和一个 \(-1\)。
边附加实数 \(w(e)\) 作为权。通路权 = 各边权之和。距离 \(d(u,v)\) = 最短路径的权。
Dijkstra 算法： 初始化 \(l_1=0\)，\(l_j=+\infty\)；每次从 \(T\) 中选距离最小顶点移入 \(P\)，用其松弛相邻顶点；重复至 \(T = \emptyset\)。
项目网络图中从始点到终点的最长路径。
最早开始 \(ES(1)=0\)，\(ES(i)=\max\{ES(j)+w_{ji}\}\)
最晚完成 \(LF(n)=ES(n)\)，\(LF(i)=\min\{LF(j)-w_{ij}\}\)
缓冲时间 \(SL(i,j)=LS(i,j)-ES(i,j)\)。关键活动缓冲时间为 0。
欧拉回路： 经过每条边一次且仅一次的回路。存在欧拉回路的图称为欧拉图。
定理 7.4 无向图有欧拉回路 ⇔ 连通且无奇度顶点。
有欧拉通路（无回路） ⇔ 连通且恰有两个奇度顶点（即通路端点）。
定理 7.5 有向图有欧拉回路 ⇔ 连通且每个顶点入度 = 出度。
有欧拉通路（无回路） ⇔ 连通且恰有两个顶点入度 ≠ 出度（一个入度大 1，一个出度大 1）。
哈密顿回路： 经过每个顶点一次且仅一次的回路。存在哈密顿回路的图称为哈密顿图。
定理 7.6（必要条件） 对任意非空子集 \(V_1 \subset V\)，\(p(G - V_1) \leq |V_1|\)。
推论： 有哈密顿通路时 \(p(G - V_1) \leq |V_1| + 1\)。
定理 7.7（充分条件） \(n \geq 3\) 阶无向简单图，若任何一对不相邻顶点度数和 \(\geq n\)，则存在哈密顿回路；若 \(\geq n-1\)，则存在哈密顿通路。
定理 7.8 \(n\) 阶有向图若基图含 \(K_n\) 生成子图，则存在哈密顿通路。
竞赛图（任意两顶点间恰有一条有向边）中一定有哈密顿通路。
定义： 顶点可划分为两个不相交非空子集 \(V_1, V_2\)，所有边两端各属其一。
定理 7.1 ⇔ 图中无奇回路。
完全二部图 \(K_{n,m}\)：\(V_1\) 中每个顶点与 \(V_2\) 中每个顶点恰有一条边。
Hall 定理（定理 7.2） 二部图 \(G=\langle V_1, V_2, E \rangle\)（\(|V_1|\leq|V_2|\)）存在 \(V_1\to V_2\) 完备匹配 ⇔ \(V_1\) 中任意 \(k\) 个顶点至少邻接 \(V_2\) 中 \(k\) 个顶点。
t 条件（定理 7.3） 若存在 \(t>0\) 使 \(V_1\) 每顶点至少关联 \(t\) 条边、\(V_2\) 每顶点至多关联 \(t\) 条边，则存在完备匹配。
能画在平面上使边仅在顶点处相交。这样的画法称为平面嵌入。
面： 边将平面划分成的区域。面 \(R_i\) 的次数 \(\deg(R_i)\) = 边界长度。
定理 7.9 所有面的次数之和 = 边数的 2 倍：\(\sum \deg(R_i) = 2m\)。
欧拉公式（定理 7.11） 连通平面图：\(n - m + r = 2\)。
推广： \(p\) 个连通分支：\(n - m + r = p + 1\)。
定理 7.12 每个面次数 \(\geq l\)（\(l\geq 3\)）的连通平面图：\(m \leq \frac{l}{l-2}(n-2)\)。
推论 \(K_5\)（\(n=5,m=10\)）和 \(K_{3,3}\)（\(n=6,m=9\)）不是平面图。
定理 7.10 \(n\geq 3\) 阶简单平面图是极大平面图 ⇔ 连通且每个面次数为 3。
库拉图斯基定理（定理 7.13） 平面图 ⇔ 无 \(K_5\) 或 \(K_{3,3}\) 同胚子图（即可收缩到它们的子图）。
对偶图 \(G^*\)：每个面对应一个顶点，每条公共边界对应一条边。对偶图连通、平面。
四色定理（定理 7.14） 任何平面图都是 4-可着色的（1976 年阿佩尔和黑肯用计算机证明）。
五色定理（希伍德，1890） 任何平面图都是 5-可着色的。
给顶点涂色，相邻顶点不同色。最少颜色数称为色数。
应用：排课冲突、寄存器分配、波长分配、地图面着色（⇔ 对偶图的点着色）。