
同题集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