省选前刷一刷bzoj上的hnoi，结果2008神奇的国度要用到弦图，于是就学习了一下。
1.
子图：对于图
G
=
(
V
,
E
)
，有
G
′
=
(
V
′
,
E
′
)
,
V
′
∈
V
,
E
′
∈
E
为其子图；
2.
诱导子图：对于图
G
=
(
V
,
E
)
,
有
G
′
=
(
V
′
,
E
′
)
,
V
′
∈
V
,
E
′
=
{
(
u
,
v
)
|
u
,
v
∈
V
′
,
(
u
,
v
)
∈
E
}
为其诱导子图；
3.
团：图
G
的一个子图
G
′
=
(
V
′
,
E
′
)
，
G
′
为关于
V
′
的完全图；
4.
极大团：一个团是极大团当它不是其它团的子集；
5.
最大团：点数最多的团；
6.
团数
w
(
G
)
=
最大团点数；
7.
最小色数：用最少的颜色给点染色使相邻点颜色不同，
χ
(
G
)
为其色数；
8.
最大独立集：最大的一个点集使任意两个点不相邻，
α
(
G
)
为其点数；
9.
最小团覆盖：用最少个数的团覆盖所有的点，
κ
(
G
)
为其团数；
10.
w
(
G
)
<
=
χ
(
G
)
；
证明：最大团由于点两两相邻，因此有
w
(
G
)
种不同的颜色，故
w
(
G
)
<
=
χ
(
G
)
。
11.
α
(
G
)
<
=
κ
(
G
)
；
证明：最小团覆盖中的每一个团中的点都是两两相邻的，故一个团中至多有一个最大点独立集中的点，命题得证。
12.
弦：连接环中不相邻两个点的边；
13.
弦图：一个无向图称为弦图当图中任意长度大于3的环都至少有一个弦。
引理：(1)弦图的每一个诱导子图一定是弦图。(2)弦图的任一个诱导子图不同构于
C
n
(
C
n
为长度为n的环)
(
n
>
3
)
14.
[例题 ]
Z
j
u
1015
F
i
s
h
i
n
g
n
e
t
给定一个无向图，判定它是否为弦图。
15.
单纯点：设
N
(
v
)
表示与点
v
相邻的点集。一个点称为单纯点当
{
v
}
+
N
(
v
)
的诱导子图为一个团。
未完待续…
16.
引理：任何一个弦图都至少有一个单纯点，不是完全图的弦图至少有两个不相邻的单纯点。
(求神犇证明)
/*
证明：
(
1
)
若图为完全图，很显然有
n
个单纯点，当
n
=
1
时，有一个单纯点。
(
2
)
若图不为完全图，则有
n
>
=
2
。
1
o
若图无环，那么图可转化为森林。
->
1.1
若树的棵树
>
=
2
，很显然有
2
个以上的叶子结点，也就是单纯点；
->
1.2
若只有一棵树，我们取度数
>
=
2
的点作为根，必有
>
=
2
个叶子节点；
2
o
若图有环。
*/
17.
完美消除序列：一个点的序列
(
每个点出现且恰好出现一次
)
v
1
,
v
2
,
…
,
v
n
满足vi在
{
v
i
,
v
i
+
1
,
…
,
v
n
}
的诱导子图中为一个单纯点。
18.
定理：一个无向图是弦图当且仅当它有一个完美消除序列。
证明：
(
1
)
充分性：由引理知任何一个弦图都至少有一个单纯点以及弦图的诱导子图都是弦图。可以使用数学归纳法假设当点数
<
n
<script type="math/tex" id="MathJax-Element-129">
n
的弦图的完美消除序列可以由一个单纯点加上剩余点的诱导子图的完美消除序列得到。
(
2
)
必要性：反证若无向图存在一个长度
>
3
的无弦环，不妨设环中在完美消除序列中出现在最前面的点为
v
，设环中
v
与
v
1
,
v
2
相连，根据完美消除序列的性质知
v
1
,
v
2
相连，与环无弦矛盾。所以无向图为弦图。
19.
M
C
S
算法：
从n到1的顺序依次给点标号(标号为i的点出现在完美消除序列的第i个)。
设label[i]表示第i个点与多少个已标号的点相邻，每次选择label[i]最大的未标号的点进行标号。