##图论基本概念
###子图
子图 subgraph
图 $G=(V,E)$ ，则 $G’=(V’,E’),V’\subseteq V,E’\subseteq E$ 为图 $G$ 的子图。
诱导子图 induced subgraph
图 $G=(V,E)$ ，则 $G’=(V’,E’),V’\subseteq V,E’={(u,v)\mid u,v\in V’,(u,v)\in E}$ 为图 $G$ 的诱导子图。
###团
团 clique
图 $G$ 的一个子图 $G’=(V’,E’)$ ， $G’$ 为关于 $V’$ 的完全图。
极大团 maximal clique
一个团是极大团当且仅当它不是其它团的子集。
最大团 maximum clique
点数最多的团。
团数 $\omega(G)$
###关系
最小染色 minimum coloring
用最少的颜色给点染色使相邻的点颜色不同。 $\chi(G)$
最大独立集 maximum independent set
最大的一个点的子集使任何两个点不相邻。 $\alpha(G)$
最小团覆盖 minimum clique cover
用最少个数的团覆盖所有的点 $\kappa(G)$
关系
- $\omega(G)\leq\chi(G)$
- $\alpha(G)\leq\kappa(G)$
##弦图概念
弦 chord
连接环中两个不相邻点的边。
弦图 chordal graph
一个无向图成为弦图当途中任意长度大于 $3$ 的环都至少有一个弦。
定理 弦图的每一个诱导子图都是弦图。
##弦图的判定
###单纯点
单纯点 simplicial vertex
设 $N(v)$ 表示与点 $v$ 相邻的点集。一个点成为单纯点当 ${v}+N(v)$ 的诱导子图为一个团。
引理
任何一个弦图都至少有一个单纯点，不是完全图的线图至少有两个不相邻的单纯点。
###完美消除序列
完美消除序列 perfect elimination ordering
一个点的序列（每个点出现且只出现一次） $v_1,v_2,\dots,v_n$ 满足在 ${v_i,v_{i+1},\dots,v_n}$ 的诱导子图中存在一个单纯点。
定理
一个无向图是弦图当且仅当他有一个完美消除序列。
####朴素算法
- 每次找一个单纯点 $v$ ，加入到完美消除序列中；
- 将 $v$ 以及相关的边从图中删掉；
- 重复以上步骤知道所有点都被删除。
时间复杂度 $O(N^4)$ ，完全不能接受，每次找单纯点太费时间了。
####最大势算法 Maximum Cardinality Search