对典型的图论问题的描述做一下汇总, 仅仅介绍问题的基本描述和问题之间的联系, 下面所有问题都是在图 的基础上描述的, 默认为无向图.

1: 匹配. 图 的一个匹配 是 的子集, 满足 中的任意两条边都没有公共的顶点. 最大匹配问题要求找到满足最大的满足条件的 .

2: 覆盖. 图 的一个覆盖 是顶点 的子集, 满足 中的任意一条边中的某个端点在 中. 最小覆盖问题要求找到最小的满足条件的 .

3: 集合覆盖(Set Cover). 对于给定的集合 和集合, 若 满足 , 则称 覆盖集合 . 最小集合覆盖(MSC)问题要求找到最小的满足条件的 .

4: 独立集(Independent Set). 图 的独立集 是顶点集 的子集, 满足 中的任意一对顶点都不相邻. 最大独立集(MIS)问题要求找到最大的满足条件的 , 同时将最大的 记作图 的独立数 .

5: 支配集(Dominant Set). 图 的支配集 是顶点集 的子集, 满足 可以被划分为 和 . 最小支配集(MDS)问题要求找到最小的满足条件的 , 同时将最小的 记作图 的支配数 .

6: 染色(Graph Coloring). 无向图 的 -coloring 满足 , 即使用 种颜色给图 的每个顶点都分配一种颜色, 使得相邻顶点的颜色都不相同. 最小的能给 进行上述染色过程的 称为图 的色数, 记作 , 称为最优染色(optimal coloring). 染色问题要求找到图 的色数 或者更进一步地, 最优的染色方案 .

7: 最优树(最短路, 最小生成树, Steiner Tree)

8: 网络流(最大流, 最小费用流, 最小割)