Graph – 图论

无向图 Undirected Grpah

图是顶点集和边集合的组合 G=(V,E) where E \subseteq 2^V
重要性质
– 握手定理：所有顶点度数之和等于边数之和的两倍 (sum of the degrees of a nodes in a graph is twice the number of edges)，i.e. \sum_{v \in V} \deg(v) = 2|E|
– 推论：任何图中都有偶数数量的度数为奇数的顶点

同构图 isomorphic

同构图含义是图的双射：G_1 \simeq G_2 when there is a bijection: \beta: V_1 \to V2 s.t. for any u1,v1 \in V, u_1\text{-}u_2 \in E_1 iff \beta(u_1)\text{-}\beta(v_1) \in E_2
也就是两个图中顶点可以形成一一对应的关系，而且只有图1对应顶点有边的时候，图2对应顶点才能有边
– 对完全图、路径图、圈、无边图来说，只要顶点数量一样，就同构
– 同构图在连通性、无圈性上都一致

连通分量 connected components

连通的含义:u-…-v if there exits some walk/path with endpoins u and v
连通分量是图的一个顶点子集：任意两个顶点都能连接, 而且是最大的
重要性质
– 命题: 任意两个CC之间是不相交(disjoint)的
– 命题: 连通分量的数量下限是顶点和边数之差: |CC| \ge |V| – |E| （证明：递归）
– 命题: 边数的下限是顶点和连通分量数量之差，上限是\binom{|V|}{2}

子图

子图：选取顶点集，然后选择其中的边集
诱导子图：选取顶点集，即确定边集

树

树是最大无圈的，森林的所有连通分量都是树
性质
– 树的边数一定是顶点数-1：最高效的联通图
– 最长路径的头尾一定是叶子节点，而且每个树一定至少有两个叶子节点
– 引理： 移除叶子节点和关联边留下的依然是树
– 最小连接命题： 移除任何边都会导致不是树
– 最大无圈命题：加上任何边都会导致有圈，但是增加一条边顶多增加一个圈
– 唯一路径命题 任何两个顶点之间都只有唯一路径（否则有圈）
– 引理：

生成树

生成子图：包括原图所有顶点的子图（但不一定包含所有边）
生成树：如果一个CG的生成子图是一棵树，那么称其为生成树
生成森林：对于非联通图，每个CC的生成树共同构成了该图的生成森林
割边：如果删除这条边一定会导致更多的连通分量；不属于一个cycle的边就是割边
性质：：
– 每个连通图都至少拥有一棵生成树
– 树的所有边都是割边，反之亦然（都是割边的图就是树）
构建生成树的算法：删边或者加边，判断是否是cutting edge割边，然后移除所有不是割边的边
实际应用
– 铺设电缆问题：找到联网所有房屋的最低成本路线
– 复杂网格图去冗

图的着色 Coloring

• k-着色是图的顶点集到色彩集合的映射：k-coloring of G is a function f:V\rightarrow [1..k]
• 适当着色即 f(u)\neq f(v) for any edge u-v; 可以用k个颜色适当着色的图叫做k-colorable
• 色数 (\chi(G)) ：使图 G 实现适当着色的最小正整数 k 被称为该图的色数
• 二分图（Bipartite graphs):

简单性质
– k-可着色的图必然可以用大于 k 的颜色数进行适当着色
– 路径图都是二分的；奇数圈三分，偶数圈二分
– 完全图的着色数=顶点数：\chi(K_n)=n (证明：鸽巢原理)
– 所有路径图P_n都是二分的；所有Tree都是二分的（证明：归纳法）

进阶性质
– $\Delta+1$定理：每一个图G都是\Delta+1可着色的，其中\Delta是图中顶点的最大度数

证明：归纳法
试图证明顶点数为k+1且最大度数为\Delta的图G’可以
\Delta+1着色，给定顶点数为k,最大度数为\Delta的图G可以\Delta+1着色，
G’移除一个顶点u后得到子图G”，余下顶点数图可以\Delta”+1着色;又加上\Delta’\ge \Delta”，所以显然G”也能用\Delta’+1着色
然后加u回去,它的相邻边最多有\Delta’条，所以在已有的\Delta’+1种颜色种必定还剩余1种颜色可供使用，因此G’也是\Delta’+1可着色的
– 命题：二分图的必要充分条件：图种不包含任何奇数长度的圈
– 可以推出树是二分的
– 可以推出二分图的任何子图都是二分的
– 色数引理： 子图的色数一定小于或等于

团和独立集

团(cliquese)是图的完全子图
在一个具有n个顶点的完全图K中，大小为k的团的数量恰好是\binom{n}{k}
独立集：
顶点集的一个子集S,其中没有任何两个顶点是相邻的
或者说独立集的诱导子图是一个无边图
补图：
P_n的补图中包含的边数量为\frac{(n-1)(n-2)}{2}
命题：
– 一个图是k-colorable的必要充分条件是：它的顶点集可以被划分为k个独立集**
– 一个图是团的必要充分条件是：顶点集S是图G中的一个团，当且仅当S是其补图
\bar{G}中的一个独立集
实际应用
– 小圈子识别 (Cliques)： 社会科学家利用团的概念来识别社交网络中的紧密群体。例如，研究认为 Facebook 的图谱中存在包含 200-250 人的极大团（即这几百人之间两两互为好友）
– K-coloring聚焦冲突下的资源分配最优化问题，比如通信网络: 无线电频率分配中，相邻的基站不能使用相通的频率

有向图 Directed Graph

有向图

• 有向图的E是一个有序对组成的边集, E \subseteq V \times V
• 边允许自环、允许反平行边、不允许平行边
• Reachability是单向的，但强连通性是双向的u\leftrightarrow v
• 最大的边数是n^2
  握手定理：所有顶点的出度之和 = 所有顶点的入度之和 = 总边数|E|
  有向路径 (Directed path): 顶点互不重复的directed walk
  强连通分量 SCCs：
  每个顶点之间都是强连通的
  缩减图
  缩减图中，每个节点代表原图中的一个SCC
  如果原图中存在S1中某个顶点向S2中顶点的边，缩减图中就会有一条从节点S1到节点S2的边
  核心性质：
• 任意两个强连通分量之间必定是不相交的(disjoint)，所以强连通分量构成了所有顶点的划分，但是不构成对边的划分
• 边可能不属于任何一个连通分量 —— 也就是说两个SCC之间可能存在S1中某个顶点向S2中顶点的边，但是S1到S2之间不存在双向的路径
• 缩减图是一个DAG，绝对没有圈

有向无圈图 Directed Acyclic Graph

核心性质：
– 命题：每个DAG都至少拥有一个源点和一个汇点

证明：如果图中有边，考虑一个最大程度的有效路径p，则该路径的起点u必定是源点；因为如果u有前驱节点w那么它要么不在路径中（否则可以延长，与最长矛盾），要么已经在路径中（形成一个圈，与无环矛盾）；同理可证明路径终点是汇点。

拓扑排序 (Topological Sort)

DAG中最重要的线性化工具：是图中所有顶点的一个排列，使得对于每一条有向边u \rightarrow v ，顶点u在序列中都出现在顶点v之前
核心性质
– 命题： 有拓扑排序的充分必要条件就是DAG
– 拓扑排序的第一个顶点必须是源点，最后一个顶点必然是汇点
– 不唯一性：一个图通常有多个正确的拓扑排序

例如：一个拥有n个顶点的无边图（属于特殊的 DAG），其拓扑排序方案共有n!种

构造拓扑排序的算法
– 算法A: 递归移除汇点及相关边
– 算法A: 递归移除源点及相关边

核心应用
– 课程先修关系： 通过拓扑排序可以规划出合理的修课顺序，确保学生在修高级课程前已完成基础课
– 软件依赖管理： 在软件开发中，模块间的调用关系（如模块 B 依赖模块 A）被建模为A \rightarrow B. 拓扑排序决定了模块的编译顺序，以防止编译冲突

二叉树

Root到任意一个其他顶点的路径都是唯一的，所以将根树视为一个根是源点、所有叶子节点都是汇点的有向图
一个二叉根树是指每个节点最多只有两个孩子的根树
性质
– 对于高度为h的二叉树，其最大节点数为2^{h+1}-1
重要应用
存储逻辑：通常遵循左小右大的原则，这种结构使得查找、插入和删除操作能够非常高效地进行
– 查找时，每一步都是在做二分决策，避开了大量不需要检查的数据
– 插入时，算法和搜索类似，直到找到一个空的叶子位；路径长度受限于树的高度所以插入速度极快，因为无论树中有多少数据，执行一次操作所经过的步数绝对不会超过h
– 性能的关键在于高度 – 即便有1023个节点，高度也只有9；查找、插入和删除操作的复杂度都与树的高度h正比，所以能大量降低操作步数, 也就是将操作的复杂度从线性(N)降低到了对数级(\log N)，即高度h