图论讲义第5讲节-支配集.pdf

第五章 支配集、独立集、覆盖集和Ramsey 数 本章讨论图中具有某种特性的顶点子集和边子集，以及它们之间的关系。本章所讨论的 图均为简单图。 §5.1 支配集、点独立集、点覆盖集 一、支配集(Domination set) 定义 5.1.1 设D ⊆V(G) ，若对∀u ∈V(G) ，要么u ∈D ，要么 u 与 D 中的某些顶点相邻， 则称 D 为图 G 的一个支配集。如果一个支配集的任何真子集都不是支配集，则称它为极小支 配集。图G 的含顶点最少的支配集称为最小支配集。最小支配集的顶点个数称为G 的支配数， 记为γ(G) 或γ 。 例如，在下图中，D {v } ，D {v , v , v } ，D {v , v , v , v }都是 G 的支配集， 0 0 1 1 4 7 2 1 3 5 6 前两个是极小支配集，D0 是最小支配集。γ(G) 1 。 v1 v2 v8 v0 v3 v7 v4 v6 v5 G 注：（1）最小支配集必是一个极小支配集，反之不然。 （2 ）任一支配集必含有一个极小支配集。 （3 ）极小支配集不唯一，最小支配集一般也不唯一。 （4 ）对二部图G (X , Y ) ，X 和 Y 都是支配集。 * * （5 ）若图G 有完美匹配 M ，则从M 中每边取一个端点构成的顶点集是一个支配集。 定理 5.1.1 设图 G 中无孤立顶点，则存在支配集D ，使得D V (G ) −D 也是一个支配集。 证明：无妨设 G 是连通图。于是 G 有生成树 T 。任取v0 ∈V(G) 。令 D {v | v ∈V(G) 且d (v , v) ＝偶数}， T 0 则D V (G ) =−D {v | v =∈V (G ) 且d (v , v) ＝奇数}，且D 和D 都是支配集。证毕。 T 0 定理 5.1.2 设图 G 无孤立顶点，D 是一个极小支配集，则D V (G ) −D 也是一个支配集。 1 1 1 证明（反证法）：若不然，存在v ∈D ，它与D 中所有顶点都无边相连，但它又不是孤立顶 0 1 1 点，故必与D 中顶点连边，因此D −v 仍是支配集。这与D 是极小支配集矛盾。证毕。 1 1 0 1 推论 5.1.1 设图 G 中无孤立顶点。对 G 的任一个极小支配集D1 ，必存在另一个极小支配集D2 ， 使得D1 ∩D2 φ 。 证明：由定理 5.1.2，D V (G ) =−D 也是一个支配集，且D ∩D φ 。D 中必含有一个极 1 1 1 1 小支配集D2 。显然D1 ∩D2 φ 。证毕。