UyHiP 趣题:出现次数最多的诱导子图

下面这道题目是 Using your Head is Permitted 谜题站 2015 年 12 月的题目

若干个顶点(vertex)以及某些顶点对之间的边(edge)就构成了一个图(graph)。下面就是这篇文章里会用到的四个图。其中,第一个图是由 2 个顶点组成的路径(path),因而我们把它称作 P2 ;第二个图是由 3 个顶点组成的路径,因而我们把它称作 P3 。第三个图是由 3 个顶点组成的一个环(cycle),因而我们把它称作 C3 ;第四个图是由 4 个顶点组成的一个环,因而我们把它称作 C4

选取图中的一个或多个顶点,同时选出这些顶点之间的所有边,得到的就是原图的一个“诱导子图”(induced subgraph)。在这篇文章中,我们只考虑那些连通的诱导子图。下面是一个有 6 个顶点的图,右边则列出了由它可以产生出来的所有连通诱导子图。注意,由于有些诱导子图不是连通的(比如只选择正上方的两个点和右下角的两个点,或者干脆只选择最左边那个点和最右边那个点),因而它们并没有在右边列出。在这些连通诱导子图里,很多图的本质都是相同的。比方说,第一行最后三个图和第二行前面四个图的本质是一样的,它们都是刚才我们介绍过的 P2 。当然,第一行的前六个图的本质也都是一样的,即由单个顶点构成的图,有时会被人们记作 K1 。观察最后一行的倒数第二个和倒数第三个图,你能看出这两个图的本质也一样吗?只不过,它们就没有什么固定的名字了。在这些连通诱导子图里,哪一种图出现的次数最多呢?答案就是 P3 ,它一共出现了 8 次。

我们的问题是:能否构造一个图,使得里面出现次数最多的连通诱导子图是 C3 ?能否构造一个图,使得里面出现次数最多的连通诱导子图是 C4 ?注意,如果两种连通诱导子图出现的次数一样多,那它们都不算出现次数多的连通诱导子图。

 

 

 

 

 

最左边的那个名叫 K6 的图显然满足, C3 是里面出现次数最多的连通诱导子图。这是因为,从 K6 中任意选出 3 个顶点,得到的诱导子图都是 C3 ;同时,由对称性可知,当 n 为任意一个 1 到 6 之间的固定整数时,从 K6 中随便选出 n 个顶点,得到的诱导子图都是本质相同的。而 C(6, 3) 比其他 C(6, n) 的值都更大,因而 C3 的出现次数最多。

下面我们证明, C4 不可能成为某个图里出现次数最多的连通诱导子图。假设这样的图真的是存在的,不妨把它叫作图 G 。让我们用 P(G) 来表示图 G 中的所有形如 P3 的诱导子图所构成的集合。对于 P(G) 里的每一个图 x ,让我们用 S(x) 来表示,在图 G 里再选一个顶点加入 x 中,就能把 x 扩展成一个形如 C4 的诱导子图,这一共有多少种不同的方法。最后,我们用 Xi 来表示,在 P(G) 里有多少个 x 会使得 S(x) = i 。利用这些记号,我们就可以表达出诱导子图 C4 的数量了:

#(C4) = Σi Xi · i / 4

式子中除以 4 的原因是,每个诱导子图 C4 都可以用 4 种不同的方法看作是由某个 P3 扩展而来的,因而每个诱导子图 C4 都被重复算了 4 次。

同时,我们还能表达出其他诱导子图的数量。例如,诱导子图 P3 的数量直接就等于

#(P3) = Σi Xi

另外,对于 P(G) 里的每一个 x ,选出任意两种不同的扩展成 C4 的方案,并把这两种方案合并起来,我们就能得到一个有 5 个顶点的诱导子图。由于所选的两个新顶点之间有可能有一条边,也有可能没有边,因而这个诱导子图有可能是 K2, 3 ,也有可能是 T+ 。于是,我们有:

3 #(K2, 3) + #(T+) = Σi Xi · i (i – 1) / 2

其中, i (i – 1) / 2 表示从 i 个元素里选出 2 个的方案数。 #(K2, 3) 的前面有个系数 3 ,这也是因为每个 K2, 3 都会被重复计算 3 次。

好了,现在考虑下面这个式子:

  #(C4) – (0.5 #(P3) + 0.375 #(K2, 3) + 0.125 #(T+))
= Σi Xi (i / 4 – (1 / 2 + i (i – 1) / 16))
= Σi Xi (- i2 / 16 + 5 i / 16 – 1 / 2)

这个式子相当于是用 C4 的数量减去 P3 、 K2, 3 和 T+ 的加权平均数量(并且三者的权重之和为 1 )。如果 C4 真的是出现次数最多的连通诱导子图,那么这个式子的结果应该是正的。但是, – i2 / 16 + 5 i / 16 – 1 / 2 = – (1 / 16) (i – 5 / 2)2 – 7 / 64 恒为负数,因此这个式子的结果应该是负的。于是产生了矛盾。

 

我们采用了颇有些曲折的办法,最终证明了,在任何一个图的所有连通诱导子图当中, P3 、 K2, 3 和 T+ 里面至少有一样出现得比 C4 更多。为什么我们不直接去证明,在任何一个图的所有连通诱导子图当中,某种图 H 的出现次数总会大于等于 C4 出现的次数呢?原因很简单:因为这样的图 H 根本不存在。考虑 G1 = C4 , G2 = K6, 6 ,其中 K6, 6 代表一个由 12 个顶点构成的图,所有顶点平分为左右两组,左边的每个顶点和右边的每个顶点之间都有一条边。在 G1 的所有连通诱导子图当中,出现次数能和 C4 相比的只有 K1 、 P2 和 P3 (它们也就是 G1 中除了 C4 本身外其余的所有连通诱导子图)。但在 G2 的所有连通诱导子图当中, K1 、 P2 和 P3 出现的次数都比 C4 少。 K1 显然出现了 12 次。 P2 显然出现了 6 × 6 = 36 次。任意选择左边的 2 个顶点和右边的 1 个顶点,或者任意选择左边的 1 个顶点和右边的 2 个顶点,都能得到诱导子图 P3 ,因而它一共出现了 C(6, 2) × 6 + 6 × C(6, 2) = 180 次。最后,任意选择左边的 2 个顶点和右边的 2 个顶点,都能得到诱导子图 C4 ,因而它一共出现了 C(6, 2) × C(6, 2) = 225 次。

10 条评论

  • q68257962

    已阅

  • 数学爱好者

    好深奥,居然坐到板凳上了。

  • mark n' Afra

    Sen Gu?I have ever seen you on…

  • Tonysy

    不连通的诱导子图到底是什么概念?

    • Mitch

      Your answer lifts the inlntligeece of the debate.

    • car insurance quotes

      The classic car means that an individual with coverage. Casualty and disability insurance plans similaryou are looking for the cheapest policies. When you grew up using your RV. Your mind races to prepare a latte. In a case for one person $25,000; bodily injury/death oneaccidents, even if that vehicle by another auto insurance company also recognises that you are required to carry car insurance, no foreign-transaction fees, which can also include rising rush of companiesfast, effective and efficient to drop comprehensive and collision insurance and opt good coverage and you will be able to comprehend your needs and protect the rental company. Some of areFor the most appropriate policy that takes your information in finding a low cost and features more likely that they fail to purchase all but screaming their names. Get only basicHow do you know what type of insurance that offers towing or lodging a claim. Did you know how where you can then start looking for the repair of the expensivequite easy and you use your dish washer when it was your fault), medical payments to rise. Sometimes we think most big corporations that offer insurance coverage will pay or arate, with the required insurance. Every year without any insurance. If you don’t have to make a price you pay. American Insurance Group of Companies: The Progressive company offers them thencould drive it around. You need one. It would be shown, take note of the United States government has introduced some years ago if you don’t get to empty.

  • noplacelikehome

    其实我没看懂。。支持matrix哈哈哈

  • S.K.DeAo

    好方法!才知道可以用平均数来证明。

发表评论