图论第89章.ppt

第七章 独立集和团 7.1 独立集 7.2 Ramsey定理 7.3 Turan定理 7.1 独立集 设S是V的一个子集，若S中任意两个顶点在G中均不相邻，则称S为G的一个独立集. G的一个独立集S称为G的最大独立集，如果G不包含适合|S’| ＞ |S|的独立集S’. 设K是V的一个子集，若G 的每条边都至少有一个端点在K中，则称K为G的一个覆盖. G的一个覆盖K称为G的最小覆盖，如果G不包含适合|K’| ＜ |K|的覆盖K’. G的最大独立集的顶点数称为G的独立数－α(G) G的最小覆盖的顶点数称为G的覆盖数－β(G) 定理7.1 设S?V，则S是G的独立集当且仅当V\S是G的覆盖. 证 按定义，S是G的独立集当且仅当G中每条边的两个端点都不同时属于S，即当且仅当G的每条边至少有一个端点属于V\S，亦即V\S是G的覆盖. 推论7.1 α + β ＝ ν. 类似可以定义G的边覆盖： 设L是E的一个子集，若G 的每个顶点都是L中某条边的端点，则称L为G的一个边覆盖. G有边覆盖当且仅当δ ＞0. 记G的最大对集的边数为α’(G) ，而记G的最小边覆盖的边数为β’(G)，分别称为G边独立数和边覆盖数. 定理7.2 若δ ＞0 ，则α’ + β’ ＝ ν. 定理7.3 在δ ＞0 的偶图中，α ＝ β’. (Konig 1931) 推论7.3 在偶图中，α’ ＝β. 7.2 Ramsey定理 7.3 Turan定理 第八章 顶点着色 8.1 色数 8.2 Brooks定理 8.3 Hajos猜想 8.4 围长和色数 8.5 储藏问题 8.1 色 数 只考虑简单图 G的一个k顶点着色是指k种颜色1, 2, …, k对于G的各顶点的一个分配. 若任意两个相邻顶点的颜色不相同，则称该着色是正常的. 一个k顶点着色可以看作是V的一个分类(V1, V2, …, Vk)，这里Vi(可能为空)表示染有颜色i的顶点集. 若顶点着色是正常的，则每个Vi均为独立集. 将“正常的(k)顶点着色”简称为“(k)着色”； 若G有正常的k顶点着色，则称G是k可着色的. 每个图都是ν可着色的； 若G是k可着色的，则一定是k＋1可着色的. 使G为k可着色的最小整数k称为G的色数，记为χ(G) . 若G的色数为k，也称G是k色的. 1可着色的?空图 2可着色的?偶图 K临界图 若G的每个真子图的色数都比G的色数小，则称G是临界的；若G是临界的且是k色的，则称它为k临界图. 每个k色图都有k临界子图. 定理8.1 若G是k临界图，则δ≥ k?1. 证 用反证法. 若G是k临界图，且δ＜k?1.设v是G中具有最小度的顶点，由于G是临界的，所以G?v是k?1可着色的，对于G?v的一个k?1着色，由于v在G中的度小于k?1，所以总可以在k?1种颜色中选取一种颜色给顶点v，从而得到G的一个k?1着色，矛盾. 推论8.1.1 每个k色图至少有k个度不小于k?1的顶点. 证 设G是k色图，H是它的k临界子图，则由定理8.1，H中每个顶点的度不小于k?1，又由于H是k色图,它至少有k个顶点，所以G至少有k个度不小于k?1的顶点. 推论8.1.2 对任意图G，χ≤Δ+ 1. 8.2 Brooks定理 由Vizing 定理知，对于简单图，χ’＝Δ或χ’＝Δ+1. 虽然χ与χ’有相同的上界Δ+1，但χ可能比Δ+1小得多，如：偶图 定理8.2 (Brooks 1941)若G是连通的简单图，并且它既不是奇圈，也不是完全图，则χ≤Δ. 8.3 Hajos猜想 图G的一个剖分图是指把G的边进行一系列剖分而得到的一个图. 虽然目前还不知道k≥3时的k色图的充分必要条件，但是（1961）提出了一个似乎可信的必要条件 Hajos猜想 若G是k色图，则G包含Kk的一个剖分图. (这个条件不是充分的，如4圈不是3色的) Dirac解决了k＝4的情形 定理8.3 若G是4色图，则G包含K4的一个剖分图. Hajos猜想是公认的一个难题，目前尚未解决. 8.4 围长和色数 究竟是什么深层的原因决定着图的色数？这个问题目前还没有满意的答案. 显然在任何顶点着色中，一个团中的顶点必然要分配互不相同的颜色，因此一个图的色数如果很大，它是不是应该含有较大的团呢？回答是否定的. 定理8.4 对于任何正整数k，存在不包含三角形的k色图. Erdos(1961)证明了： 给定任意两个整数k和l，存在一个围长为k而色数为l的图. 8.5 储藏问题 图的色数在许多实际问题中都有应用 一家公司制造n种化学制品C1，C2，…, Cn，其中某些制品是互不相容的，如果它们互相接触就会引起爆炸. 作为一种预防措施，该公司希望