图的概念以及常见的图论问题介绍_完全子图定义

图的相关概念

强连通图：很多人搞混，这个是在有向图框架下提出的，即每两个顶点均有边$(v_i,v_j),(v_j,v_i)$。例如：

强连通分量：其也叫做极大强连通子图，向该图中添加任意顶点都会导致其失去强连通的属性，则称其为G的强连通分量。
例如对于有向图：

其有很多强连通子图，例如虚线内的：

但是最大的那个强连通子图不是上面虚线的，而是下面虚线的：

这就叫强连通分量。不过要注意的是，强连通分量也不是唯一的，例如： G ′ = ( { 4 } , ϕ ) G'=(\{4\},\phi) G′=({4},ϕ)也是强连通分量。总之，牢牢抓住:添加任何顶点进来都会使其失去强连通的属性这个特点即可。

偶图（二分图、二部图）：若无向图$G=<V,E>$的结点集$V$能够划分为两个子集$V_1,V_2$，满足$V_1\cap V_2=\varphi ,V_1\cup V_2=V$，使得$G$中任意一条边的两个端点，一个属于$V_1$，另一个属于$V_2$，则称$G$为偶图（Bipartite Graph）或二分图（Bigraph）。$V_1$和$V_2$称为互补结点子集，偶图也可记为$G=<V1,E,V2>$。

bipartite:有两个部分的。

一个二部图举例如下：

但是我们一般是这样画成直的。如下：

这就是我们熟悉的，常见的二部图了。

最大团问题

团就是完全子图，最大团就是最大完全子图。
完全子图：给定无向图G=(V,E)。如果U$\subseteq$V，且对任意u,v$\in$U 有(u，v) $\in$E，则称U是G的完全子图。
G 的最大团是指G中所含顶点数最多的团。比如给定一个无向图：

其最大团有3个，都有3个顶点。

最大独立集问题

给定无向图G=(V,E)。如果U$\subseteq$V，且对任意u,v$\in$U 都没有(u，v) $\in$E，则称U是G的独立集。可以理解为孤立的点，没有边。

最大独立集就是独立集中顶点数最多的那个独立集。
比如上面的例子中，也有很多最大独立集，其中一个可以是{2,4}。

其等价为图G的补图的最大团，什么是图G的补图？
补图：将G中所有没有连接的边都连上，使之称为完全图，然后将原来的那些边删除，就成了G的补图。
上面的补图如下：

图着色问题

给定一个无向图G=（V, E），其中V为顶点集合，E为边集合，图着色问题即为将V分为K个颜色组，每个组形成一个独立集，即其中没有相邻的顶点。其优化版本是希望获得最小的K值，即至少需要多少种颜色，可以把图着色。

对于上图，至少需要4种颜色，使得每种颜色的顶点集合都是独立集。下面是一个解：

为了尽量补充，还有判定问题k-着色：

给定一个图，请问可以k着色吗？

意思是，用k种颜色能不能够使得每一种颜色的顶点都是独立集。显然，如果我们都求出了最少需要多少种颜色来给图染色，那么这个问题也就解决了。
比如上图：4着色可以，3着色不可以。

SAT

SAT即satisfiable，即可满足性。
其整体称为一个句子sentence（其实就是一个命题公式），多个短语(phrase)合取而成，每个短语中由命题变元析取而成，这些命题变元又称文字(literal)。
例如：
$(p_1\vee p_2)\wedge (\neg p_1\vee p_3)$
其中$(p_1\vee p_2)$称为一个短语，$(p_1)$称为文字，一整个称为句子。

SAT问题是指，是否存在一种指派，使得整个句子为真。

k-SAT问题，即每个短语中文字的个数限制为k，常见的有2-SAT,3-SAT，比如上面的例子是2-SAT问题。

顶点覆盖

顶点覆盖是图$G=(V,E）$中顶点$V$的子集$V^{\prime }$，使得对于图$G$中的任何一个条边$e$，都存在$V^{\prime }$中的某一个顶点，是这个边$e$的一个端点。寻找$V^{\prime }$并使得$V^{\prime }$元素个数最少的问题叫做最小顶点覆盖问题。
例如对于下面这个图，绿色顶点集合就是一个最小顶点覆盖（答案不唯一）。

set cover（集合覆盖）

假设我们有个全集U (Universal Set), 以及m个子集合
$S_1,S_2\dots ,S_m$, 目标是要寻找最少的集合，使得集合的并集等于U。

注意：乍一看很简单，但是并不简单哦，并不是先选那个最多元素的集合就会越好，例如：

我们直接选择后两个完事，如果你选择了第一个，那么也还是要选择后两个。