“欲买桂花同载酒，终不似，少年游”
前言
继二元关系后，果然图论还是来了…概念是真的无敌多，好在各自关联性比较强，方便记忆（也更方便混淆）
明天是最后的离散数学了，学完就能出去玩啦~QwQ
图
概念
- ψ(e)=<v1，v2>：e 是连接 v1，v2 的边。无向图中 v1，v2 均既是起点也是终点；有向图中 v1 为起点，v2 为终点
- 环（自回路）：从一个结点出发回到这个结点的边
- 平行：ψ(e1)=ψ(e2)，即两个结点间有多条边，则这些边平行
- 简单图：没有环，没有平行边
- 多重边图：没有环，有平行边
- 伪图：有环，有平行边
- 同构（同构映射）：理论上两个图的结点和边都一一对应则为同构。实际上可以将图进行拉扯，若能变为一样的图则为同构
个人理论：如果两个图同构，用邻接矩阵表示，通过列交换可以变为同一邻接矩阵 - 结点度：和该结点相连的边数总和为该结点的度
- 孤立结点：没有边与其相连的结点
- 端点：度为 1 的结点
- 零图：仅由孤立结点构成的图
- 平凡图：一阶零图
路径、回路和连通性
- 路径（通路）：点、边的交错序列
- 闭路径（回路）：起点和终点重合
- 路径长度：路径中包含边的数量
- 简单路径：路径中出现的边都不相同
- 简单回路：回路中出现的边都不相同
- 基本路径：路径中出现的点都不相同
- 基本回路（圈）：回路中出现的点都不相同（起点、终点相同，其他点都不同的路径）
- 连通图：图中任意两个结点可达（规定平凡图是连通的）
- 连通分量：图的一个连通子图
- 最大连通分量（极大连通子图）：图的一个连通子图。再加上图中任意一个该连通子图以外的结点，该连通子图就不连通
- 分支：无向图的极大连通子图
- 弱连通：忽略有向图边的方向，将其变为无向图。若此无向图是连通的，则该有向图是弱连通的
- 单向连通：有向图的任意两个结点，其中一个结点可以到达另一个节点，则该有向图是单项连通的
- 强连通：有向图中任意两个结点都互相可达。则该有向图是强连通的
若有向图为单向连通但不为强联通，则必有一个结点出度为 0 - 割点：无向图中，删去一个结点（及其关联的边），导致图的连通分量增加，则该结点是此图的一个割点
- 点割集：结点组成的集合，去掉这个集合里所有的点，图的连通分量增加，且该集合的真子集不是一个点割集
一个割点构成的集合就是一个点割集 - 点连通度：使连通图 G 成为一个不连通图需要删除的点的最小数目
点割集的最少元素数量为点连通度 - 割边（桥）：无向图中，删去一条边，导致图的连通分量增加，则该边是此图的一条割边
- 当一条边不在任何回路上，其一定是一条割边
- 边割集：边组成的集合，去掉这个集合里所有的边，图的连通分量增加，且该集合的真子集不是一个边割集
一条割边构成的集合就是一个边割集 - 边连通度：使连通图 G 成为一个不连通图需要删去的边的最少数目
边割集的最少元素数量为边连通度
参考：点割集、边割集、点连通度、边连通度
矩阵表示
- 可达性矩阵：仅表示两个结点的可达性，元素仅为 1 或 0
- 路径矩阵：元素两个结点之间的路径数量，可用矩阵乘法求得路径为 x 的路径矩阵
- 关联矩阵：表示结点和边的关系，即行和列分别表示结点和边。有向图的出边用 1 表示，入边用-1 表示
特殊的图
两个图，欧拉图和马米尔顿图，目的都是要回到出发点，所以一定要有回路
欧拉图
- 欧拉路径：包含所有边的简单路径（包含所有边，且所有边仅出现一次）
- 欧拉回路（欧拉闭路）：包含所有边的简单回路（包含所有边，且起点和终点相同，其余边只出现一次）
- 欧拉图：具有欧拉回路的连通无向图（欧拉定理）
仅有两个结点的度数是奇数的图具有一条欧拉路径（可以一笔画）；每个结点的度数都为偶数的图具有一条欧拉回路，为欧拉图（可以一笔画并回到起点）
哈密尔顿图
- 哈密尔顿路径：包含所有结点的简单路径（包含所有的结点，且所有结点仅出现一次）
- 哈密尔顿回路：包含所有结点的简单回路（包含所有顶点，且起点和终点相同，其余顶点只出现一次）
- 哈密尔顿图：具有哈密尔顿回路的连通无向图
平面图、对偶图及着色
平面图
如果一个图在平面上能画出（拉扯）没有任何的交叉，则称其为平面图，否则为非平面图
- 面：多边形的图分成的每个区域都成为该图的平面
- 无限面：外侧平面
- 欧拉公式：一个平面图 G（n，m）有 n 个顶点，m 条边，有 k 个面（包括无限面），则 n-m+k=2
对偶图
一个平面图，将其每个平面（包括外侧平面）用一个结点代替，经过平面图的每条边连接新的结点形成新的边，产生的新的图成为该平面图的对偶图
如果平面图有一条边单独伸出（一个结点仅有一条关联的边），则其对偶图表现为一条环
着色
- 正常着色：若可用 n 种颜色对图 G 着色，则称 G 是 n—可着色的
任何简单平面图都是 4—可着色的 - 着色数：对图着色是需要的最少颜色
韦尔奇.鲍威尔(Welch Powell)着色算法
参考：[学习笔记]韦尔奇.鲍威尔法(Welch Powell)
这里的操作针对的是对偶图
- 按度数递减次序排列各点
- 用第一种颜色，对第一点着色，并按排列次序对与前面结点不相邻的每一点着同样的颜色
- 按排列顺序向下检查，用第二种颜色对尚未着色的点重复第 2 步
- 重复 直到所有的点都着上颜色为止
