9个点的所有解锁图_图的类型——图论与SAT

最近学SAT遇到不少图- -，嘛，所以不怎么谈计科以外的部分

不管是什么结构，只要结构中的对象存在一种二元联系，那么总是可以找到一个图来描述它，这里说的图是用一些有向边或无向边把一些点连起来，无所谓其中边的长度；如果是多元关系，可以用超图表示。

图论是应用数学中应用极其广泛的一类，在计算机科学中也是如此，日常生活中其实也很广泛；任意一种网络，都是图；家谱是图；思维导图鱼骨图是图；PPT中经常各种这样的图；食物链鄙视链是图；网格其实也是图，等等。

图论的未解决问题之多不管是在应用数学还是在计算机科学都是突出的

TCS中以NP-complete问题为例，List of NP-complete problems中涉及图论的是最多的

图的类别

四大类：有向图、无向图、Mixed graph（既有有向边也有无向边）、network（每条边赋了一个实数值）

Orientation graph

将一个无向图的每一条边加上一个方向，得到的有向图称为一个orientation，或者Oriented graph，这样的图中任意2个点最多有一条有向边相连。

Regular graph

度数degree：无向图中，一个点连接的边的数目称为该点的度，无向图的度数定义为点中的最大度数；有向图则按该点是按方向分为入度和出度

邻居neighbour：无向图中与一个点相连的点的集合称为该点的邻居(neighbour)，

regular graph即每个点的度数相同的图，如果这个度数为k，那么称为k-regular graph；

如果一个k-regular graph中每一对相连的点的邻居恰好有λ个相同，每一对不相连的点的邻居恰好有μ个相同，则其为Strongly regular graph，记为srg(v,k, λ, μ)，v是点的数量。

Complete graph

complete graph（完全图）即每一对点都有边相连的图，如果是有向图则每一对点都有2个相反的有向边。

无向完全图记为

, n为点的数目。如

，

Finite graph

点和边的数量都有限则称为有限图(finite graph)，否则称为无限图(infinite graph)

Connected graph

path：用边连接的两个点u和v表示边uv，那么如果存在一组边

，那么这个序列称为一个从u到v的路径(path)，如果无向图中任意两个边u,v都存在一个对应的路径，那么该图

k-vertex-connected graph/k-edge-connected graph：如果任意去掉k-1 个点/条边，图仍然连通，称该图为k-(vertex-)connected graph/k-edge-connected graph

Bipartite graph

如果一个图中，所有的边都是一些点之一和另一些点之一的边，则称为偶图(Bipartite graph)，完全偶图(complete bipartite graph)是指这两个点集中每一对点都有边相连的偶图，2个点集假设一个为m，一个为n，则记为

，如果可以是

，那么记之为

，那是star graph。

Path graph

track：如果一个从u到v的路径中不经过同一个点两次或以上，称为track（轨道）

除了两个点度数为1以外其余度数为2的连通图称为path graph，或者说一个可以用一个轨道表示的图称为path graph，设点数目为n，记为

Cycle graph

cycle（圈）:一个轨道如果是从u到u的，称为cycle（圈）

Trace（行迹）：一个path如果不包含相同的边，称为trace（轨道）

circuit（回路）： 一个行迹如果是从u到u的，称为circuit（回路）

一个图若每个点的度数都是2则称为cycle graph，或者说一个图若可以表示为圈则称为cycle graph，设点的数目为n，记为

，可以绘制为一个正多边形

Planar graph

Planar graph（平面图）：如果一个图这样表示：任意两条边除了它们自己连接的点以外不相交，那么称其可以嵌入平面，称为planar graph（平面图），否则称为nonplanar graph（非平面图）

tree

一个无向无回路连通图称为tree（树），或者说任意2个点都恰好有1条path的图称为tree（树）

forest: 如果一个图中，任意2个点至多有1条path，那么称为forest（森林），这样的图可以表示为若干不相交的树的合并

poly tree

poly tree: tree的一个orientation，将一个tree的边各赋予一个方向形成的有向图称为poly tree，类似的有定义polyforest

Wikipedia在页面上对graph类型的直接介绍大概就展开到这里了，不过还有更多的图

line graph

line graph: 一个图G的line graph（边图）是这样的图：每个点代表G中一条边，每条边以及其连接的两个点表示G中相交于一个点的两条边，如果一个图可以表示成某个图的边图，则称其为边图，一个图F是图G的边图，则记为F=L(G)

chordal graph

chord: 一个图的一个圈有一个chord（弦）表示存在一条边，不是这个圈中的边但是连接了圈中两个点

chordal graph：一个图中，任意一个包含了至少4个点的圈cycle包含一个chord，则称之为chordal graph(弦图)

Comparability graph

Comparability graph：如果存在一个偏序关系，图中2个点相连当她们彼此可比较大小，则该图称为Comparability graph

补图：一个图的补图即保留所有点，把所有图中已有的边去除同时把未有的边加入得到的图

comparability graph的补图称为cocomparability graph

Hamiltonian graph&Euler graph

这两个太有名就不多说了，Hamiltonian graph（哈密顿图）：存在哈密顿回路的图即哈密顿图；Euler graph（欧拉图）：存在欧拉回路的图即欧拉图

perfect graph

vertex coloring(点染色): 将图中的点赋予一个颜色，若任意一个点的邻居的颜色与该点不同，则称该染色为vertex coloring，类似地有edge coloring(边染色)的定义

chromatic number(染色数，色数): 对图进行点染色最少需要的颜色的数目称为chromatic number（染色数，或点染色数），进行边染色最少需要的颜色的数目称为edge-chromatic number（边染色数），图G的染色数和边染色数分布记为

Clique: 一个图中的某些点彼此相连，则这些点组成的点集称为一个clique

clique number（团数）：图中最大的clique包含的点的数目称为clique number，图G的clique number记为

induced graph(生成子图)：一个图中取某些点以及连接这些点的所有边组成的子图称为induce graph，图G关于点集S的生成子图记为 G[S]

若一个图G的每一个生成子图G[S]的色数chromatic number=团数clique number

，那么该图称为perfect graph（完美图）

以下类别的图都是perfect graph：

1. 偶图
2. 偶图的边图
3. 弦图，弦图又包括了
   1. forest, k-tree
   2. split graph（这些没有中文的都不知道中文叫啥，弃疗了..）
   3. block graph
   4. Ptolemaic graph
   5. interval graph
   6. trivially perfect graphs
   7. windmill graph
   8. strongly chordal graph
4. comparability graph，该图又包括了
   1. 偶图
   2. cograph
   3. permutation graph
5. Perfectly orderable graph
   1. distance-hereditary graph
   2. wheel graph
6. Trapezoid graph

以上是完美图的图一篇文章不能很好地全部说清楚- -，作为例子各举一个

这里有一张图能说明一些图的关系，

既然是说与SAT相关，提一下相关的图；

implication graph

将一个2CNF中，每个literal作为点放在图上，对每个clause

，将2条对应的有向边连上，形成的图称为implication graph，2CNF有解当且仅当其implication graph的每个强连通分量不包含2个相反的literal点

2CNF也可以用无向图表示，同样把每个literal作为一个点，存在一个clause

就把两个literal x,y相连，这样形成的图可以用来证明#2SAT是#P-complete，实际上对kSAT，用超图也能做这样的表示；另外，若2CNF中所有的literal都是pure literal，那么用最多一半的literal作为点形成无向图也可以表示，这样的情况，解#2SAT问题相当于求这个无向图的独立集的个数，由此求无向图独立集个数的算法也可以#2SAT的算法实现，实际上似乎只有这个办法能够一般性地求这个问题。

关于图的类别还远不止这些，有缘再写.. 类别可以在这里看；下期预告：图算法；下下期预告：图性质

参考文献

1. Graph Classes: A Survey
2. Murty - Graph theory
3. Reinhard Diestel - Graph theory
4. Efficient graph representations
5. Graph-classes-with-structured-neighborhoods-and-alg_2013_Theoretical-Compute

参考网站

1. https://www.graphclasses.org/
2. Graph (discrete mathematics)
3. http://www.openproblemgarden.org/