同题集5的解 到期：星期一，3月7目下午9点 问题】一个无向图G有宽度w,如果顶点序列可以安排为 ,2,3,··,Un 以便每个项点￥由边连接到至多在前面的w个项点。（顶点号在￥之前，如果下：）使用 归销证明，与魔度至多W的图是(w+1)可着色 国忆图是k可着色的，当且仅当每个项点可以棱分配k种颜色的其中一，以使毗忽顶点得 到不同的碳色。) 解：我们使用在n上的，项点的数量的归纳法。令P()是宽度是w的图是可（叶）着色 的命愿。 基例：有F1项点的每张图有宽度0并且是0+1=1可着色的。所以。P(1)是真实的。 归筛步：现在我们假设P()为了迁明P(+I,令G是a+I)顶点且宽度w的图。这意 味着暖点可以鼓安排为序列： U1,2,3,···,Un,Un+1 以便每个顶点￥，可以连接到至多w个在前面的顶点。去除顶点和所有邻接边给出有 个项点的一张图G且党度至多是。（如果原始的序列保留，然后去除V+:项点不增却从 项点到前面项点的边的数量。)因此。G是(w+I)可着色的。由假设P()得到。现在 替操质点，和它相忽的边。因为￥由到前面至多W个顶点连接，我们可以上色，与 这些都不同。所以，P(叶1)为真。 定理由归纳法的原则得证。 问愿2在这个问题种，我们阶您展示以下定理的证明： 定理1图是二部图，当且仪当它不包含食圈。 正如这是对“当且仅当”的普通斯言，证明有二部分。部分()要求您证明，左边道涵 右边。部分b、(c)和d帮助您证明，右边涵左边。 (回忆阁是两部的，当且仅当它是可二着色的。) (假设左边和证明右边，三个到五个句子应该足够了， 解：这择G的两可着色。考虑有顶点V:红.，的一个任意圈。然后现点必须 是对所有的偶数为一种颇色，对所有的奇数为另一种薇色。因为和？必须着不同的 颜色。k必须是每数。因此。圈有偶数长度。 b现在我们要证明右边崔涵左边。作为初步步，解释为什么任何树T是2可着色的。 PDF文件使用“pdfFactory Pro”试用版本创建题fineprint.cn
问题集 5 的解 到期： 星期一， 3 月 7 日下午 9 点 问题 1 一个无向图 G 有宽度 w，如果顶点序列可以安排为 以便每个顶点 vi由边连接到至多在前面的 w 个顶点。 (顶点 vj在 vi之前，如果 j< i。)使用 归纳证明，与宽度至多 w 的图是(w+ 1)可着色。 (回忆图是 k 可着色的，当且仅当每个顶点可以被分配 k 种颜色的其中一，以便毗邻顶点得 到不同的颜色。) 解： 我们使用在 n 上的，顶点的数量的归纳法。 令 P (n)是宽度是 w 的图是可 (w+ 1)着色 的命题。 基例： 有 n=1 顶点的每张图有宽度 0 并且是 0+1=1 可着色的。 所以， P (1)是真实的。 归纳步： 现在我们假设 P (n)为了证明 P (n+1)。 令 G 是 (n+1)顶点且宽度 w 的图。 这意 味着顶点可以被安排为序列： 以便每个顶点 vi可以连接到至多 w 个在前面的顶点。 去除顶点 vn+1和所有邻接边给出有 n 个顶点的一张图 G’且宽度至多是 w。 (如果原始的序列保留，然后去除 vn+1 顶点不增加从 顶点 vi到前面顶点的边的数量。) 因此， G’是 (w+ 1)可着色的，由假设 P (n)得到。 现在 替换顶点 vn+1和它相邻的边。 因为 vn+1由到前面至多 w 个顶点连接，我们可以上色 vn+1与 这些都不同。 所以， P (n+ 1)为真。 定理由归纳法的原则得证。 问题 2 在这个问题种，我们给您展示以下定理的证明： 定理 1 图是二部图，当且仅当它不包含奇圈。 正如这是对“当且仅当”的普通断言，证明有二部分。 部分(a)要求您证明，左边蕴涵 右边。 部分(b)、(c)和(d)帮助您证明，右边蕴涵左边。 (回忆图是两部的，当且仅当它是可二着色的。) (a)假设左边和证明右边。 三个到五个句子应该足够了。 解： 选择 G 的两可着色。 考虑有顶点 v1， v2，…， vk的一个任意圈。 然后顶点 vi必须 是对所有的偶数 i 为一种颜色，对所有的奇数 i 为另一种颜色。 因为 v1和 vk必须着不同的 颜色，k 必须是偶数。 因此，圈有偶数长度。 (b)现在我们要证明右边蕴涵左边。 作为初步步，解释为什么任何树 T 是 2 可着色的。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
解：任意地选择一个“根”顶点。着色顶点￥为红色，如果在T中，从到v的距离是 钙数，且颜色V黑色，如果从r的距离是奇数。 为了看见这定义了有效的T树的2可着色，考虑任意边x一y。从x到「存在唯一的路径， 从y到「存在唯一的路径。这些路径中须包含边xy,否则，与另外两个路径一起的部分 将形成圈。 如果y是从到子的唯一路径，那么恰好一条边比x到服更接近。同样，如果x一 是在从y到r的唯一路径上，都么x是比y到根更接近的路径。无论如何，一个项点在从 ?米说是奇数长度距离，？到其他顶点是偶数长度。因此二个顶点是不同藏色着色的， (©)假设G是连通的没有奇数圈的图，那么令T是一个G的生成树。说明一个有效的T的2 可着色也定义一个有效的G的2可着色。 解：碳点由在T中的一个边连接了，通过以上的论证。在T的2可着色中有不同的颜色， 因此我们仪看要边y,不是在树中，必须连接不月颜色的顶点。 令Z是在T中的从x到根r的路径上的，且也是T中y到「的路径中的第一个公共膜点。从 x到z的路径，接着是从z到y的路径。接着是从圈的边y%,有假设的，必须是偶数长度. 因为圈的长度是1加上两条路径的长度，路径中的一条必须有奇数长度，且令一条是偶数长 度。这个暗示从%到：和从y到：的路径，一个有偶数长度，而另一条是俺数长度。从我们 2看色T得到，它得到x和y必须着不同的氟色. (现在假设定理1的右边：名为，G是一个没有奇数国的图，1是不必连通，证明G是二 部阁。 解：每次用2种颜色给每个G的连通组件着色。 问题3令G,=(V,E》,并且G2=(V,E)是每个顶点有度1的无向图。图G,和G:的 并是图G=(V,EUE证明，G是二部图。 解：考虑在G的所有圈。如果在圈的一个边在E,则在圈中的任何一方边必须在E:否 则，G的度比1大。因此，在圈周围的边是在E,和E2中交替的。这个蕴涵圈的长度必领是 ,数，因此由定理1得G是二部 问题4为每个整数n≥0，我们可以定义称n一立方的图。这被表示为H,顶点是n比 特的序列，0,1。在二个顶点之间存在一个边，如果它们恰好有一个位不同： 0-cube 1-cube 2-cube 3-cube PF文件使用"pdfFactory Pro”试用版本创建w.fineprint,n
解： 任意地选择一个“根”顶点 r。 着色顶点 v 为红色，如果在 T 中，从 r 到 v 的距离是 偶数，且颜色 v 黑色，如果从 r 的距离是奇数。 为了看见这定义了有效的 T 树的 2 可着色，考虑任意边 x—y。 从 x 到 r 存在唯一的路径， 从 y 到 r 存在唯一的路径。 这些路径中须包含边 x—y; 否则，与另外两个路径一起的部分 将形成圈。 如果 x—y 是从 x 到 r 的唯一路径，那么恰好一条边比 x 到根 r 更接近。同样， 如果 x—y 是在从 y 到 r 的唯一路径上，那么 x 是比 y 到根更接近的路径。 无论如何，一个顶点在从 r 来说是奇数长度距离，r 到其他顶点是偶数长度，因此二个顶点是不同颜色着色的。 (c)假设 G 是连通的没有奇数圈的图，那么令 T 是一个 G 的生成树。说明一个有效的 T 的 2 可着色也定义一个有效的 G 的 2 可着色。 解：顶点由在 T 中的一个边连接了，通过以上的论证，在 T 的 2 可着色中有不同的颜色， 因此我们仅需要边 x-y，不是在树中，必须连接不同颜色的顶点。 令 z 是在 T 中的从 x 到根 r 的路径上的，且也是 T 中 y 到 r 的路径中的第一个公共顶点。从 x 到 z 的路径，接着是从 z 到 y 的路径，接着是从圈的边 y-x，有假设的，必须是偶数长度。 因为圈的长度是 1 加上两条路径的长度，路径中的一条必须有奇数长度，且令一条是偶数长 度。这个暗示从 x 到 r 和从 y 到 r 的路径，一个有偶数长度，而另一条是奇数长度。从我们 2 着色 T 得到，它得到 x 和 y 必须着不同的颜色。 (d)现在假设定理 1 的右边；名为，G 是一个没有奇数圈的图，但是不必连通，证明 G 是二 部图。 解： 每次用 2 种颜色给每个 G 的连通组件着色。 问题 3 令 G1 = (V， E1)，并且 G2 = (V， E2)是每个顶点有度 1 的无向图。 图 G1和 G2的 并是图 G = (V， E1 ∪ E2)。 证明， G 是二部图。 解： 考虑在 G.的所有圈。 如果在圈的一个边在 E1，则在圈中的任何一方边必须在 E2; 否 则，G1的度比 1 大。因此，在圈周围的边是在 E1和 E2中交替的。这个蕴涵圈的长度必须是 偶数，因此由定理 1 得 G 是二部。 问题 4 为每个整数 n ≥ 0，我们可以定义称 n－立方的图， 这被表示为 Hn。顶点是 n 比 特的序列，{0,1}。在二个顶点之间存在一个边，如果它们恰好有一个位不同。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
(a)证明。H.是一个欧拉回路，对于所有的偶数n≥2。 解：我门证明，H有一条欧拉回路，通过说明它是连通的，以及每个顾点都是偶数度。 首先，考虑在n立方上的二个任意项点， b1b2·.bn和C9C2,Cn。这两个顶点由穿越以下序列项点的路径连接 bbbs...bu c1babs...ba 自h. 9g9. (注意耳一个项点可以连贯地出现多次，在这个序列中：因此，更如准确地，路径穿越在这 个序列中的不同的膜点。)所以，图是连通的。 在n立方中的每个项点v和其他的n个项点相邻，这些项点可以通过翻转n个b中的 其中一个bm来获得。所以，如果n是偶数，在n立方的每个现点由偶数度。因此，H,有 款控回路，对于所有的n≥的2. (b)证明，H。有所有的≥2存在一条哈密顿圈。考虑一个归纳论据，根据事实H1包括 两个同构于H的子阁（实线），相应的顶点被连接（虚线）： 2-cube 3-cube 解：我门使用在n上的归钠法。令P()是n意方的有一个哈密领圈的命题。2立方体在 四个顶点上的一个圈，因此P2)为真。现在假设P(为真，对于一些≥2，并且考口 +)立方体。在建议中注明的，这张图包括两个和·立方体月构的子图，相应的顶点用边连 接起米。由归纳法得。存在一个哈密柳圆C在这两个子图中的一个。且相应的哈密顿圈 C,在另一个中，雨加边山一和一”，创造一个喻密顿圈在(+1)方体中。因此，W+1)为 真，由归纳法原理得到断言为真。 间题5计算机程序的部分包括结果计算的序列，这里结果被存放到变量中，像这样： PF文件使用"pdfFactory Pro”试用版本创建w.finsprint,n
(a)证明， Hn是一个欧拉回路，对于所有的偶数 n ≥2。 解： 我们证明， Hn有一条欧拉回路，通过说明它是连通的，以及每个顶点都是偶数度。 首先，考虑在 n 立方上的二个任意顶点， 和 。这两个顶点由穿越以下序列顶点的路径连接： (注意同一个顶点可以连贯地出现多次，在这个序列中; 因此，更加准确地，路径穿越在这 个序列中的不同的顶点。) 所以，图是连通的。 在 n 立方中的每个顶点 v 和其他的 n 个顶点相邻，这些顶点可以通过翻转 n 个 bit 中的 其中一个 bit 来获得。所以，如果 n 是偶数，在 n 立方的每个顶点由偶数度。 因此， Hn有 欧拉回路，对于所有的 n≥的 2。 (b)证明， Hn有所有的 n≥ 2 存在一条哈密顿圈。 考虑一个归纳论据，根据事实 Hn+1包括 两个同构于 Hn的子图 (实线)，相应的顶点被连接 (虚线) ： 解： 我们使用在 n 上的归纳法。 令 P (n)是 n 立方的有一个哈密顿圈的命题。 2 立方体在 四个顶点上的一个圈，因此 P (2)为真。 现在假设 P (n)为真，对于一些 n ≥ 2，并且考虑(n +1)立方体。在建议中注明的，这张图包括两个和 n 立方体同构的子图，相应的顶点用边连 接起来。由归纳法得，存在一个哈密顿圈 Cn，在这两个子图中的一个，且相应的哈密顿圈 Cn’在另一个中，添加边 u—u’和 v—v’，创造一个哈密顿圈在(n+1)方体中。因此，P(n+1)为 真，由归纳法原理得到断言为真。 问题 5 计算机程序的部分包括结果计算的序列，这里结果被存放到变量中，像这样： PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
Inputs e.b Step 1. e=a+tb 2 d =ae g=+3 4 了=e-e h=了+1 d.g.h 如果每个变量都存做到寄存器里，在微处理器中的常快的内存，计算机能进行这样的 运算丰常快。计算机通常有几个寄存墨，然而，因此它们必筑鼓广泛地使用以及经常重复利 用。在程序中分配每个变量到一个寄存器中的问题，称为寄存器分配问。 在上面的例子中变量a和6必须分配不同的寄存墨，因为它们有不同的输入值。此外， c和d也须粮分配不同的寄存器：如果它们使用了同样一个，则©的值在第二步将被重写， 并且我们在第三步得到情误的答案。另一方面，变量结合b和d可以使用同样的寄存器：在 第一步以后，我们不再需要b,并且可以重写保存它的值的嵩存器。井且，〔和h也可以 使用同一寄存器：一旦在最后步1被求值，保存í的值寄存器可以被重写 (假设，计算机按顺序执行每步，并且每步完成后再开始下一步。) 把寄存器分派问愿重变换为为关于图看色的一个问题。顶点对应什么？在应该有什么 情况下在二个项点之间有一条边？根据上面的例子构建相应的图。 解：对每一个变量对应一个项点。在二个顶点之间的一个边表明变量的值必须存放于不同 的寄存器中。 我们门可以分类的每次出现在程序中的变量的作为分配或使用。特别是，如果变量在等 式的左边或在“输入”行，出现是分配。如果变量在等式的右边或在“输出”行，变量的 出现是使用。 变量的生命是从变量的最初的分配的代码段直到最后使用的变量。如果它们的生命有 重叠的时核，在二变量之阿存在一条边，这个规则产生了以下阁： 2 )使用尽可能少量颜色着色您的图。称计算机寄存器R1,R2等等。描述变量的分配到您 的着色的高存器。您需要多少个常存器？ FPDF文件使用“pdfFactory Pro”试用版本创建fineprint.cn
如果每个变量都存放到寄存器里，在微处理器中的非常快的内存，计算机能进行这样的 运算非常快。计算机通常有几个寄存器，然而，因此它们必须被广泛地使用以及经常重复利 用。在程序中分配每个变量到一个寄存器中的问题，称为寄存器分配问题。 在上面的例子中变量 a 和 b 必须分配不同的寄存器，因为它们有不同的输入值。 此外， c 和 d 也必须被分配不同的寄存器; 如果它们使用了同样一个，则 c 的值在第二步将被重写， 并且我们在第三步得到错误的答案。另一方面，变量结合 b 和 d 可以使用同样的寄存器; 在 第一步以后，我们不再需要 b，并且可以重写保存它的值的寄存器。 并且， f 和 h 也可以 使用同一寄存器; 一旦在最后步 f+1 被求值，保存 f 的值寄存器可以被重写。 (假设，计算机按顺序执行每步，并且每步完成后再开始下一步。) (a) 把寄存器分派问题重变换为为关于图着色的一个问题。 顶点对应什么？ 在应该有什么 情况下在二个顶点之间有一条边？ 根据上面的例子构建相应的图。 解：对每一个变量对应一个顶点。 在二个顶点之间的一个边表明变量的值必须存放于不同 的寄存器中。 我们可以分类的每次出现在程序中的变量的作为分配或使用。 特别是，如果变量在等 式的左边或在“输入”行，出现是分配。 如果变量在等式的右边或在“输出”行，变量的 出现是使用。 变量的生命是从变量的最初的分配的代码段直到最后使用的变量。 如果它们的生命有 重叠的时候，在二变量之间存在一条边。 这个规则产生了以下图： (b) 使用尽可能少量颜色着色您的图。 称计算机寄存器 R1、R2 等等。描述变量的分配到您 的着色的寄存器。您需要多少个寄存器？ PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
解：四个寄存器是活要的。一个可能的变量到寄存器的分配再上图中指示出来。一般情况 中，使用最小数字的颜色着色一个图是很困难的：没有有效的过程知道。然面，寄存器分配 问题总是导致间隔图。对于间隔阁，存在有效的着色过程，其能结合到编译器中。 ()假设一个变量镀分配到一个值超过一次，正如在如下的代码段中： 4=r十g #三4+3 【三m-是 甲■t十型 您如何处理这个负责的东西？ 解：每次一个变量被重新赋值，我们能把例子认为等价于以下： t=r十s 程每1+3 f三m一表 和=f十程 我门现在可以进行图的构造，按超以前一样进行着色。 问题6k次DBum序列是包含每0和1的串的任意k位的组合作为子串恰好有一次。 例知1，这DeBruiin序列的次是2： 01100 主要到两位的组合01,11,10,00作为子串出现给好一次。 寻找一个次为3的DeB可jn序列，您可以发璞以下图有月， 0 10 0 01 PF文件使用"pdfFactory Pro”试用版本创建ww.fineprint,n
解： 四个寄存器是需要的。一个可能的变量到寄存器的分配再上图中指示出来。一般情况 中，使用最小数字的颜色着色一个图是很困难的；没有有效的过程知道。然而，寄存器分配 问题总是导致间隔图。对于间隔图，存在有效的着色过程，其能结合到编译器中。 (c) 假设一个变量被分配到一个值超过一次，正如在如下的代码段中： 您如何处理这个负责的东西？ 解：每次一个变量被重新赋值，我们能把例子认为等价于以下： 我们现在可以进行图的构造，按照以前一样进行着色。 问题 6 k 次 DeBruijn 序列是包含每 0 和 1 的串 的任意 k 位的组合作为子串恰好有一次。 例如，这 DeBruijn 序列的次是 2 ： 01100 主要到两位的组合(01， 11， 10，00)作为子串出现恰好一次。 寻找一个次为 3 的 DeBruijn 序列。 您可以发现以下图有用。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
解：一可能解换方案是： 1000101110 意到这个对应于个即的开始于顶点10的通路，其穿越每条边恰好一次。特别地，如 果我们写下开始的顾点(10)的数字，然后在每条边上穿越的数学，我们得到这个序列. )在一有向图种，有向通路是一条项点和边交错的通路： ,→，2，一，终，→4,4，，n-1n-1一04,0 有向欧拉回路是一条穿域每条边恰好一次，并结束于其开始的一条通路：也瓷是V,=￥假 设G是一张有向图，以至于每个项点的如皮等于其出度，且存在从每个项点到其他面点的 通路。正明，G有一紧款拉回国路。 解：我们使用反证法证明。令 P=1一2,2一3,3一U4,,Un-1一n 是在G中的最长的有向路径。郑么每条出的边必须在路径上。因为。的如度等于出 度。仅有的可能性是V=V种 假设P不是一条有向拉回路：也就是，在图G中的某条边x-一y不在路径P上。郑么 存在从V到x的路径。由假设得到。令斯-一2是在路径P上的第一条边。那么有向路径 是： h→+1，Un-1→Un,→边，2→3，···，→2 比P长，这是矛听的 (e)解释为什么k次DeBruijn序列是存在的，对于每个k≥2. 解：构建原点是所有的-1)此特长的字符串的有向图。从顶点1b.b-1到顶点 b2··,b一1b添加一条标签为的有向边。这个建议说明对k=3的这样的图， 在这张图中。每个暖点有如度2和出度2。此外，图是连接的，从顶点 b1b匀.b:-1到项点CC…Ck-1的路径通过以下标签为C1,C2,…和 Ck一1的边获得。因此，有向图是款拉回路。 现在从任刺顶点开如。写下在那个顶点的数字。然后写下在图上的有向欧拉回路上的每 个数字。当通路从在标签为b的边的顶立12.b-1腿出的时候，序列的后服变 PF文件使用"pdfFactory Pro”试用版本创建w.finsprint,n
解： 一可能解决方案是： 1000101110 注意到这个对应于一个邮箱的开始于顶点 10 的通路，其穿越每条边恰好一次。特别地，如 果我们写下开始的顶点(10)的数字，然后在每条边上穿越的数字，我们得到这个序列。 (b)在一有向图种，有向通路是一条顶点和边交错的通路： 有向欧拉回路是一条穿越每条边恰好一次，并结束于其开始的一条通路；也就是 v1 = vn。 假 设 G 是一张有向图，以至于每个顶点的如度等于其出度，且存在从每个顶点到其他顶点的 通路。证明，G 有一条欧拉回路。 解： 我们使用反证法证明。 令 是在 G 中的最长的有向路径。 那么每条出 vn 的边必须在路径上。 因为 vn 的如度等于出 度。仅有的可能性是 v1 = vn。 假设 P 不是一条有向欧拉回路；也就是，在图 G 中的某条边 x−→ y 不在路径 P 上。 那么 存在从 v1到 x 的路径，由假设得到。 令 vi −→ z 是在路径 P 上的第一条边。那么有向路径 是： 比 P 长，这是矛盾的。 (c)解释为什么 k 次 DeBruijn 序列是存在的，对于每个 k≥2。 解： 构建顶点是所有的(k− 1)比特长的字符串的有向图。从顶点 到顶点 添加一条标签为 bk的有向边。这个建议说明对 k＝3 的这样的图。 在这张图中，每个顶点有 如度 2 和出度 2 。 此 外 ，图是连接的 ; 从 顶 点 到顶点 的路径通过以下标签为 和 的边获得。因此，有向图是欧拉回路。 现在从任何顶点开始。写下在那个顶点的数字。然后写下在图上的有向欧拉回路上的每 个数字。当通路从在标签为 的边的顶点 退出的时候，序列的后缀变 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
为b1b2·.bk-1bk.因为周游穿越每条边每个顶点恰好一次，结果序列包括每个kb 字符串恰好一次。 FDF文件使用“pdfFactory Pro”试用版本创建fineprint.cn
为 。因为周游穿越每条边每个顶点恰好一次，结果序列包括每个 k-bit 字符串恰好一次。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn