离散数学：图论基础及算法应用

# 离散数学
## 图论基础
### 图的定义
- **无向图**
  - 节点与边的集合
  - 边无方向
- **有向图**
  - 节点与边的集合
  - 边有方向（箭头指向）
- **混合图**
  - 包含无向边和有向边的组合图
### 图的表示
- **邻接矩阵**
  - 二维数组表示连接关系
  - 适用于稠密图
- **邻接表**
  - 数组中每个元素是链表
  - 适用于稀疏图
## 图的性质
### 连通性
- **无向图的连通性**
  - 两个节点间的可达性
### 强连通性
- **有向图的强连通性**
  - 任意两个节点间的相互可达性
### 欧拉性
- **欧拉路径**
  - 遍历每条边恰好一次的路径
- **欧拉回路**
  - 从某点出发，遍历每条边恰好一次，回到出发点的回路
### 哈密顿性
- **哈密顿路径**
  - 遍历每个节点恰好一次的路径
- **哈密顿回路**
  - 从某点出发，遍历每个节点恰好一次，回到出发点的回路
## 图的算法
### 深度优先搜索 (DFS)
- 使用栈实现的遍历算法
- 应用场景
  - 拓扑排序
  - 连通分量
### 广度优先搜索 (BFS)
- 使用队列实现的遍历算法
- 应用场景
  - 最短路径查找
  - 扩展搜索
### 最短路径算法
- **Dijkstra 算法**
  - 适合非负权重的图
- **Floyd-Warshall 算法**
  - 适合所有节点间的最短路径计算
### 最小生成树算法
- **Prim 算法**
  - 从一个节点开始生成树
- **Kruskal 算法**
  - 按边的权重从小到大选择边
## 特殊类型的图
- **树**
  - 无环且连通的图
  - 每两个节点有且仅有一条路径相连
- **二分图**
  - 节点可分为两个集合
  - 每条边连接不同集合的节点
- **平面图**
  - 可以嵌入二维平面而不交叉
## 应用
### 网络流
- **最大流问题**
  - Ford-Fulkerson 方法
- **最小割定理**
### 匹配问题
- **最大匹配**
  - 查找二分图中的最大匹配
- **最小顶点覆盖**
  - 求解覆盖所有边的最少顶点集合
### 地图着色
- **四色定理**
  - 任何地图最多需要四种颜色着色相邻区域