其他主题（选学）完美图ppt课件.ppt

1 第 章其他主题 选学 8 1完美图定义 如果图 的任意诱导子图均满足 H 则称 是完美的 在讨论完美图时 一般用稳定集来指独立集 对于每个图 有 个有用的最优化参数 2 独立数a G 稳定集中的最大顶点数团数 G 团中最大顶点数色数最小着色数团覆盖数q G 最小团覆盖数如果 G A 对所有 V G 成立 则称 是r 完美的 如果q G A a G A 对所有 V G 成立 则称 是a 完美的 定理 在最小的非完美图中 任何一个稳定集不可能与每个最大团都相交 证明 如果 中一个稳定集 与任何 G 团均相交 则由G S的完美性得到 3 G S G S G 1 而且 完成了 的一个 G 着色 这样 就是完美的 定理 完美图定理 一个图是完美的当且仅当它的补图是完美的 证明 证明 的a 完美性蕴涵 的r 完美性 将此应用到Gc即得到充分性的证明 如上述结论不成立 则考虑一个a 完美但不是r 完美的最小图 根据定理1 可以假设 中的每个最大稳定集 与某个最大团Q S 不相交 4 构造 的一个特殊的顶点多重复制 S Si 是 的所有最大稳定集构成的集合 对每个顶点加权 权值的大小是该顶点在 Q Si 中出现的频率 设hj是满足xj Q Si 的稳定集Si S的个数 根据顶点多重复制性保持r 完美性和a 完美性 H G h是a 完美的 即a H q H 我们用计数方法分别得到a H 和q H 由此得出一个矛盾 将 Q Si 和V G 之间的关联关系表示成一个0 1 矩阵 用A来表示这个矩阵 于是 aij 1当且仅当xj Q Si 根据构造 hj是A的第j列中 的个数 n H 是A中所有 的个数 5 由于每行都有 G 个 故n H w G S 由于顶点复制不能使团扩大 故 H G 所以 q H n H H S 我们证明a H S 从而得出矛盾 H中的每个稳定集包含G中某个稳定集的所有顶点的所有拷贝 所以a H maxT S i xi Thi 这个和计算了A中由T索引的列上的 的个数 如果我们利用行来计算这些 便能得到a H maxT S s S T Q S 由于T是一个稳定集 它最多有一个顶点位于每个选定的Q S 中 而且 T和Q T 是不相交的 由于 T Q S 对于所有的S S成立 并且 6 T Q T 0 故我们得到a H S 弦图的再研究同树一样 更一般的弦图类有很多特征刻画 在弦图的定义中 不包含无弦环这种定义本身就是一种特征刻画 它不允许某种子结构出现 限制有限子结构序列的出现往往可以得到一个有效算法来测试成员资格 但是对于弦图而言 这种需要限制的子结构序列是无限的 故而需要其他的方法来测试线图的成员资格 弦图均可以由如下方法构造得到 由单个顶点开始 不断添加新顶点使其与某个团内的所 7 有顶点均邻接 这种构造顺序恰好是单纯顶点删除顺序的逆序 在这样一个构造顺序下进行贪心着色恰好得到一个最优着色 定义 图G的交表示是一个集族 Sv v V G 使得u v当且仅当Su Sv不为空集 如果 Sv 是G的一个交表示 则称G是 Sv 的交图 引理 如果T1 Tk是树T中两两相交的子树 则有一个顶点属于所有T1 Tk 定理 一个图是弦图当且仅当它有由一棵树的一些子树构成的交表示 证明 我们选择归纳法 以K1开始 8 设 n是G的一个单纯删除顺序 由于 n是G v1的单纯删除顺序 由归纳假设得 存在一棵树T使得它的一些子树构成G v1的子树表示 由于v1在G中是单纯的 集合S NG v1 诱导得到G v1的一个团 故为S中的这些顶点指定的那些T的子树是两两相交的 由引理 这些子树有一个公共顶点x 添加一个叶子y使之与x相邻 这样就把T扩张成T 同时 我们还将边xy添加到表示S中顶点的那些子树中 我们用仅含顶点y的子树来表示v1 这样在T 中完成了G的一个子树表示 9 反之 设T是对G进行子树表示时用到的最小的一棵树 并假设其中v V G 是由T v T来表示的 如果xy E T 则G必有一个顶点u使得T u 包含x而不包含y 否则 将xy收缩到y之后将在一棵比T更小的树中得到G的另一个子树表示 令x是T的一个叶子 u是G中满足如下条件的一个顶点 T u 包含x但不包含x的相邻顶点 G中u的相邻顶点对应的子树必然包含x并且它们是两两相交的 于是u在G中是单纯的 删除T u 即得到G u的子树表示 根据归纳假设 得到了G u的一个单纯删除顺序 进而 10 将u添加进来即得到G的一个单纯删除顺序 最大基数搜索算法 输入 图G输出 一个顶点 数字双射f V G 1 n G 思想 对任意未编号的顶点v 维护一个标签l v 以表示该顶点在已编号的顶点中的度 位于单纯删除顺序尾部的顶点是在最后一个顶点周围的顶点 所以在单纯构造顺序中 标签大的顶点应当先被添加进去 初始化 将所有顶点标记为 令i 1 11 迭代 任意选择一个标签值最大的未编号的的顶点 将它编号为i并将其相邻顶点的标签加 将i加 继续迭代 8 2拟阵定义 一个遗传族或者一个理想是由若干集合构成一个集族F 且F中任意集合的子集也属于F E上的一个遗传系统M包含由E的若干个子集构成的非空理想IM和构造该理想的各种方法 这种构造方法称为M的要素 12 IM的元素称为M的独立集 E的其他子集都是非独立的 这些子集构成集族DM 基指的是极大独立集 回路指的是极小非独立集 BM和CM分别表示E的这两个子集族 E的子集的秩指的是其中独立集大小的最大值 秩函数rM定义为r X max Y Y X Y I 定义 图G的一个环拟阵M G 是E G 上的一个遗传系统 其回路是G中的环 一个遗传系统 如果它是某个图G的环拟阵M G 则称之为可图解拟阵 13 对于遗传系统M 基可交换性指的是 如果B1 B2 BM 则对任意e B1 B2均存在f B2 B1使得B1 e f BM 拟阵是满足基可交换性的遗传系统 定义 在遗传系统中 圈指的是一个元素 它形成大小为 的回路 并行元素指的是两个不同的元素 它们构成一个大小为 的回路 如果一个遗传系统没有圈和并行元素 则称它是简单的 定义 向量空间中 向量集合E的向量拟阵是一个遗传系统 其独立集是E中线形无关的 14 向量集 可以用上述方法表达的拟阵称为线形拟阵 或可表达拟阵 矩阵A的列拟阵M A 是定义在其所有列上的向量矩阵 定义 由并集为E的集合A1 Am诱导的横截拟阵是E上的一个传递系统 其独立集是 A1 Am 的子集的相异代表系 等价的说法是 令G是一个E m 二部图 其中e i当且仅当e Ai 独立集是被G的匹配浸润的E的子集 定义 E上的一个遗传系统M是一个拟阵 如果它满足下列条件之一 其中I B C和r分别 15 表示M的独立集 基 回路和秩函数 I 扩展性 如果I1 I2 I且 I2 I1 则存在e I2 I1使得I1 e IU 一致性 对任意X E 属于I的X的极大子集均有相同的大小 B 基交换性 如果B1 B2 B 则对任意e B1 B2均存在f B2 B1使得B1 e f B R 子模块性 只要X Y E 则r X Y r X Y r X r Y A 弱吸收性 只要X E且e f E 则 16 r X r X e r X f 蕴涵r X e f r X A 强吸收性 如果X Y E且r X e r X 对任意e Y成立 则r X Y r X C 弱消除性 对不同的回路C1 C2 C和x C1 C2 另有C的一个成员含于 C1 C2 x中 J 诱导回路 如果I I 则I e至多包含一个回路 G 贪心算法 对于E上的任意非负权函数 贪心算法选出一个总权重最大的独立集 定理 对于遗传系统M 上述定义拟阵的各种条件是相互等价的 17 拟阵的交定义 给定E上的遗传系统M1 M2 M1与M2的交是独立集族为 X E X I1 I2 的遗传系统 拟阵交定理 对于E上的拟阵M1 M2 最大公共独立集的大小满足max I I I1 I2 minX E r1 X r2 Xc 证明 对于弱对偶 考虑任意I I1 I2和X E 集合I X和I Xc也是公共独立集 18 I I X I Xc r1 X r2 Xc 为了证明等号成立 我们对 E 进行归纳 当 E 0时 两端都是 如果E的任意元素在M1或M2中都是一个圈 则max I 0 r1 X r2 Xc 其中X由M1中的所有圈构成 因此 我们假设 E 0且某个e E在两个拟阵中都不是圈 令F E e 考虑拟阵M1 F M2 F M1 F和M2 F 令k minX E r1 X r2 Xc 我们在M1和M2中找出一个公共的独立k 集 如果这样的集合不存在 则M1 F和M2 F没有公共的独 19 立k 集且M1 F和M2 F没有公共的独立k 1 集 由归纳假设和秩公式得到 对于某个X F r1 X r2 F X k 1对于某个Y F r1 Y e 1 r2 F Y e k 2我们利用F Y e Yc和F X X e c 将两个不等式相加 有r1 X r2 X e c r1 Y e r2 Yc 2k 1现在 我们把r1的子模块性应用到X和Y e上 同时把r2的子模块性应用到Yc和 X e c上 20 为清晰起见 令U X e V Y e 将它代入前面的不等式得到