UyHiP 趣题:几个特殊的强正则图

下面这个趣题出自 Using your Head is Permitted 谜题站 2016 年 8 月的题目,稍有改动。

屋子里有若干个人,任意两个人都有恰好 1 个共同的朋友。这有可能吗?有可能。比方说,屋子里有 9 个人,其中 8 个人正好组成 4 对朋友,第 9 个人则和前面 8 个人都是朋友。容易验证,任意两个人都有恰好 1 个共同的朋友。我们可以用下面这个图表示此时这 9 个人之间的朋友关系,其中每个点代表一个人,如果两个人是朋友,就在他们之间连一条线。

除了上图展示的情况之外,我们还能构造出很多别的同样满足要求的情况。事实上,上述方案可以扩展到一切奇数个人的情况,比如下面这样:

现在,假设屋子里有若干个人,任意两个人都有恰好 2 个共同的朋友。这有可能吗?有可能。比方说,屋子里有 4 个人,他们互相之间都是朋友。容易验证,任意两个人都有恰好 2 个共同的朋友。我们可以用下面这个图表示此时这 4 个人之间的朋友关系。

我们的问题是,除了上图展示的情况之外,还有别的同样满足要求的情况吗?

 

 

 

 

 

 

 

 

有。想象屋子里有 16 个人,他们站成了一个 4 × 4 的方阵。每行里的 4 个人互相之间都是朋友,每列里的 4 个人互相之间也都是朋友。于是,对于任意两个同一行或者同一列的人来说,都恰好有 2 个共同的朋友,即这一行或者这一列的另外两个人;对于任意两个既不同行又不同列的人来说,也都恰好有 2 个共同的朋友,即与我同行与你同列的人,以及与你同行与我同列的人。我们可以用下面的这个图表示此时这 16 个人之间的朋友关系(我们把同一行的点以及同一列的点都稍微错开了一些,使得连线不会重叠在一起)。

那么,除此之外,还有没有别的满足要求的解呢?有,比如下面这个图:

上面这两个图有很多类似的地方:它们都有 16 个点, 48 条连线,每个点都恰好引出了 6 条连线。不过,这两个图确实是本质不同的两个图。你可以这样看出来:前面这个图中,与每个点相邻的 6 个点互相之间连成的是两个三角形;而后面这个图中,与每个点相邻的 6 个点互相之间连成的是一个“圈”。

任意两个人都有恰好 2 个共同的朋友,究竟有多少种可能的情况呢?现在,我们已经看到了三个解。第一个解是 4 个互相之间都有连线的点。在图论中,我们通常用 K4 来表示这个图。第二个解则是借助一个 4 × 4 的方阵构造出来的。在图论中,这个图叫做 4 × 4 rook’s graph ,因为它相当于国际象棋中的车(rook)摆成 4 × 4 的方阵后互相之间能否攻击的示意图。

真正神奇的就是问题的第三个解了。它叫做 Shrikhande graph 。这是由印度数学家 Sharadchandra Shankar Shrikhande 在 1959 年发现的。在图论中, Shrikhande graph 是一个非常神奇的图。

如果一个图的每个点都引出了相同数目的线,我们就说这个图是一个“正则图”(regular graph)。如果一个正则图有 v 个点,每个点都引出了 k 条线,并且它额外地满足,任意两个相邻的点之间都恰好有 λ 个公共邻点,任意两个不相邻的点之间都恰好有 μ 个公共邻点,我们就说这个图是一个“强正则图”(strongly regular graph),用符号 srg(v, k, λ, μ) 表示。

显然, n × n rook’s graph 属于强正则图 srg(n2, 2n – 2, n – 2, 2) 。那么反过来,满足 srg(n2, 2n – 2, n – 2, 2) 的图是否一定就是 n × n rook’s graph 呢?基本上是,除了唯一的一个反例:当 n = 4 时, Shrikhande graph 也满足 srg(n2, 2n – 2, n – 2, 2) 。

这篇文章的题目也反映出了 Shrikhande graph 的独特之处。如果任意两个点都有恰好 2 个公共邻点,那么除了 K4 和 n × n rook’s graph 以外, Shrikhande graph 是唯一满足要求的解了。也就是说,任意两个人都有恰好 2 个共同的朋友,可能的情况一共就只有 3 种。

43 条评论

  • 沙尘暴

    下周数学竞赛最近看了好多东西

  • 莫名

    这个是用什么软件做的图啊

  • UNIC

    听说图论现在不考

  • 龙在天边

    你好,有一个关于随机性图论有意思的问题,想请教您一下,希望能和你联系下,我邮箱是f.yan@buaa.edu.cn,谢谢。

  • 龙在天边

    这几年一直关注你的博客,收获了蛮多乐趣,也开拓了思维角度,最近有个问题一直想没有相通,就想到和你讨论一下,但又找不到你的联系方式,只能给你留言希望看到了回一下邮件,非常感谢。

  • 小筑净

    这完全是题海战术啊,很喜欢,很佩服!

  • 摇钱妹

    是用visio做的图吗?

  • midi

    我用edge浏览器留的言都看不见,如果重新发的话会显示duplicate comment detected
    这言是留下来了 但不知道哪去了。换其他浏览器没事
    edge问题是多

  • 小柿子

    为什么图的画法不一样,就说是不同的解呢?

  • F

    本质需要判断图是否同构,文中提到:
    你可以这样看出来:前面这个图中,与每个点相邻的 6 个点互相之间连成的是两个三角形;而后面这个图中,与每个点相邻的 6 个点互相之间连成的是一个“圈”。

  • 接着走

    现在,假设屋子里有若干个人,任意两个人都有恰好 n 个共同的朋友。除了K[n+2]的平凡解,有其他可能吗?

  • 正五边形,五个顶点连接到中心。
    题目没说每个点出来的线数都一样吧

  • jack zhou

    如果要构造一个4连通4正则,无K4子图,无K1,3子图的图,不知阁下有没有什么建议。

  • MatrixCascade

    orz

  • 日本藤樹

    http://www.japants99.com/
    日本藤素、威而鋼使用時機
    使用日本藤素這類型壯陽保健食品前,最好先問過醫生。
    醫生判斷建議使用,即可依照醫生指示購買適當劑量的日本藤素。
    若作為保健食品使用也應該先降低劑量,過猶不及。

    而使用日本藤素、威而鋼之後,並不是一輩子都要持續使用。
    當情況好轉,就可以與醫生討論是否能夠停藥。

  • dd

    收到很多私訊,大家很想知道如何使用日本藤素 以及自己的情況如何。 首先都會建議大家一樣先去看醫生,再使用日本藤素。 但還是可以稍微分享一下自己使用狀況 1.早上:地瓜+咖啡,餐後食用日本藤素 2.中午:正餐+莓果類果汁,餐後食用日本藤素 3.晚上:視情況而定,未必會使用 http://www.japants99.com/ http://cialisinin.com

  • 飛機杯

    飛機杯款式?挑選推薦。
    這兩年飛機杯款式越來越多,花招也極盡可能的多元豐富。
    為的就是取悅男性使用者。
    飛機杯款式大致區分為:
    1.重複使用款式
    2.一次免洗款式

    最頂級的重複使用款式飛機杯就是TENGA電動版飛機杯。
    其餘重複使用飛機杯款式也是非常多元,要如何挑選,則可以參考各大Youtuber或是部落客開箱推薦,這時候的挑選重點可以參考以下:
    1.使用上是否順手
    2.清洗是否方便
    3.內壁構造是否符合個人喜好
    4.價位是否可接受
    5.外觀是否會使人不自在

    市面上的飛機杯成千上萬種,絕對能挑選到符合自己喜好的一款。
    https://www.masturbation-cup.com

  • 日本藤樹犀利士

    困擾吳先生很久的問題:日本藤素哪裡買?
    約40歲的吳先生近半年常加班,回家也熬夜忙工作、打電動,
    身體沒有充分休息,因此碰到性功能障礙的問題,開始到處打聽日本藤素、樂威壯等保健食品。
    但這種問題不敢大肆宣傳,也不敢問人,自己卻困擾已久:
    到底日本藤素哪裡買?有人說日本藤素屈臣氏有賣,也有人說可以網購日本藤素。
    但都是未經證實,吳先生當然不敢亂買。

    日本藤樹 http://www.japants99.com/
    犀利士 http://cialisinin.com

  • pejal

    男性也有更年期,年齡增長男性荷爾蒙會逐漸降低,而精子量也會逐漸減少、精子品質也會變差,但通常精子不會用完,大多數是因為其他性功能問題導致無法射精,並非沒有精子。

    很多人會問會問美國黑金可以提高生育率嗎?

    美國黑金可以幫助促進精子的增加數量和提高精子的質量,的確可以大大的提高女性的受孕機會,和刺激生殖器官的活性化能力。

    但其實跟生活習慣更加相關,培養好的生活習慣,例如多喝水、飲食均衡、不過量飲酒抽煙,運動再搭配美國黑金保養,提高精子數量這是絕對肯定的,數量一提升,受孕機會當然就大很多。

  • pejal

    男性也有更年期,年齡增長男性荷爾蒙會逐漸降低,而精子量也會逐漸減少、精子品質也會變差,但通常精子不會用完,大多數是因為其他性功能問題導致無法射精,並非沒有精子。

    很多人會問會問美國黑金可以提高生育率嗎?

    美國黑金可以幫助促進精子的增加數量和提高精子的質量,的確可以大大的提高女性的受孕機會,和刺激生殖器官的活性化能力。

    但其實跟生活習慣更加相關,培養好的生活習慣,例如多喝水、飲食均衡、不過量飲酒抽煙,運動再搭配美國黑金保養,提高精子數量這是絕對肯定的,數量一提升,受孕機會當然就大很多。

    http://www.usa-blackman.com/

  • 飛機杯

    近期有女性粉絲敲碗:飛機杯正確使用方法。
    這實在讓人又驚又喜,原以為關注飛機杯的都是男性。
    因此決定先回覆女孩的飛機杯疑問。
    飛機杯正確使用方法之前其實有大致說明過。
    女孩買給男友的飛機杯是最高級的那種電動飛機杯。
    這款飛機杯正確使用方法如下:
    1.先拆開包裝,小心將電動飛機杯打開
    2.稍微用清水沖洗後晾乾(勿直接曝曬)
    3.使用時將潤滑產品擠在飛機杯口、內部
    4.啟動電動版,確認正常運作
    以上步驟執行完畢,就可以放心使用囉。
    http://masturbation-cup.com

  • 犀利士

    萬事俱備,只欠日本藤素?
    最近收到有趣的讀者來信,暱稱小明好了。
    小明表示邁入中年的他最近遇到了真愛,
    但時常抽煙、喝酒、熬夜應酬的他,在第一次要跟對方發生親密關係的時候,卻出現了大問題。
    重視氣氛的兩人,當晚準備了紅酒、燭光晚餐、醉人的爵士樂。
    萬事俱備,兩人都非常陶醉在當下的氣氛中,但小明卻發現自己硬不起來。
    這時想去拿多年前買過的日本藤素5mg,卻又怎麼樣都找不到,
    讓他事後回想起這段故事,自嘲「萬事俱備,只欠日本藤素」。
    日本藤樹 http://www.japants99.com/ 犀利士 http://cialisinin.com

  • 日本藤樹

    婚姻成功秘訣-早上的日本藤素
    有讀者來信分享,最近生活性福美滿可能是因為早上的日本藤素
    之前跟太太總是不協調,無法讓雙方滿足。
    後來第一次看到日本藤素就是在這裡的文章,爬完文後立刻聽從建議去掛號
    跟醫生討論後,先從低劑量日本藤素用起。
    也只使用早上一個時段,空腹使用日本藤素後喝咖啡。
    日本藤樹 http://www.japants99.com/ 犀利士 http://cialisinin.com

  • 飛機杯

    飛機杯如何在亞洲國家興起?成為國民男性最愛?
    若要討論飛機杯如何在亞洲國家興起,就要先聊到日本。
    飛機杯這類型產品是由日本開始盛行熱賣,單看日本Tenga在全球這麼火紅就可略知一二。
    而日本流行文化透過10-20年前的日劇、AV女優等不同管道輸出到各個國家。
    影響首當其衝的國家就是最為哈日的台灣、馬來西亞、新加坡等地。
    因此這些地方也成為飛機杯熱賣的國家。
    對這些國家的男性來說,飛機杯就是他們不可告人又必備的玩具。
    http://masturbation-cup.com

  • dogolin

    男性保健美國黑金
    http://www.usa-blackman.com/
    美國黑金是可以長期服用的,大部分同類產品,都是直接作用你的心血管系統來實現勃起。但美國黑金與常規的壯陽藥不同的地方在於他更像是一種“食補”的補品,主要是通過補充體內元素的形式去壯陽的,在身體負擔上沒有負擔,副作用自然小。

    要徹底根治性功能障礙不是一朝一夕的事情,不能光有藥效,長期服用副作用也要非常的小,想要可以有效根治也可以當長期保養的產品,副作用又不會很大的藥物時最推薦的當然是美國黑金,只能說美國黑金更為全方位補足男性所需,給你充滿體力自信的生活。

    http://www.usa-blackman.com/

  • 日本藤素

    日本藤素效果,以及使用的硬度為何?
    開始接觸犀利士的人最想知道的就是日本藤素效果,
    以及使用後的硬度能到達什麼程度?
    首先可以先討論日本藤素的效果

    這是一種常聽到的壯 陽保健品。
    獲取日本藤素的方法建議都是先就醫診斷,再請醫生開立處方。

    日本藤樹 http://www.japants99.com/ 犀利士 http://cialisinin.com

  • 飛機杯

    飛機杯哪裡買?PCHOME、MOMO以外的地方更划算?
    近期因為雞排妹在嘖嘖募資做了飛機杯專案的緣故,
    開始一堆男性網友、女性網友討論飛機杯,女生主要都是買來送人的。
    男生除了自用,也會送給較親近的友人,表示兄弟情誼。
    而第一常見的飛機杯問題就是:飛機杯哪裡買?
    有些人習慣到pchome、momo網購,
    但是有眼尖的網友發現網購飛機杯可以到情趣選品店,會有更多優惠。
    http://masturbation-cup.com

  • 飛機杯

    為什麼另一半寧願用飛機杯,也不想跟妳做?
    這種深夜食堂話題很常出現:飛機杯跟女朋友,男生心裡想選的是飛機杯?
    男生喜歡自慰、飛機杯大於跟女友、老婆做的原因百百種,
    以下帶大家了解可能的心理因素
    1. 使用飛機杯有效率,隨時隨地都能做
    2. 使用飛機杯不用講求前戲、燈光美、氣氛佳
    3. 使用飛機杯自己最懂自己,另一半未必能取悅自己
    http://masturbation-cup.com

  • 日本藤樹c

    如何知道自己是否需要使用日本藤素?
    若遇到早洩、陽痿、不舉等問題,或是性功能障礙、性事不協調,
    多數人就會開始急尋「如何知道自己是否需要使用日本藤素?」。
    但先別急著用日本藤素,以下最佳作法提供大家參考
    1.自行評量:使用勃起功能障礙ED程度評估標準
    2.找相關專業醫生詢問是否真的需要日本藤素,以及需要的劑量、使用時間多長等

    日本藤樹 http://www.japants99.com/ 犀利士 http://cialisinin.com

  • temo

    美國黑金治療勃起障礙有用嗎
    http://www.usa-blackman.com/
    男性長期服用藥物導致性功能問題,出現生殖器不能勃起的現象,美國黑金可以調理身體,讓身體機能恢復到一定水平,達到長期補氣補精的作用。

    如果你是情緒低落、精神緊張、工作壓力、環境等因素等不良的心理因素,會影響男性的性功能,出現生殖器不能勃起的現象,美國黑金可以短時間改善體質,讓使用者漸漸越來越有精神,不感到疲勞。

    萬一你是器質性的ED的話建議先就醫,把問題先治療好,再搭配美國黑金保養身體,效果才會加倍的好,千萬別在網路上道聽塗說,任何病徵都要對症下藥及時治療,保持良好心態,才是最正確作法。
    http://www.usa-blackman.com/

  • 飛機杯

    「飛機杯無感」原來是買到山寨品? 女網友分享日前送給男友一款網購的飛機杯, 男友用了竟然說無感,讓女網友相當傻眼。 連忙問了當地品牌客服,才發現原來自己買到的竟是TENGA飛機杯-山寨版。 其實各大飛機杯品牌在網路上都可以買得到,但價格多有落差。 在幾百塊以內的落差尚可接受,但差額若高達5折,就必須仔細思考。 http://masturbation-cup.com

  • 日本藤素

    「勃起功能正常比例」會隨著年齡增長而變低,
    因此也有人會將日本藤素這種保健品當作保養使用,定期吃當吃補(?)
    而使用日本藤素建議還是先詢問過醫生、藥師等專業人員。
    既然有養生一說,對於幾歲開始使用日本藤素,就不用太過緊張。

    日本藤樹 http://www.japants99.com/ 犀利士 http://cialisinin.com

  • bexeb

    http://www.usa-blackman.com/
    不少男人煙不離手,吃飽飯來一根,上廁所前來一根,事後菸再抽一根,覺得自己這樣是個真男人,萬萬沒想到手上那一根,毀掉下面那一根。

    吸煙有害身體健康這是大家都知道的,吸煙的危害相信大家也都有所了解,但大多男性選擇不看不聽不接受,吸菸就是導致陽痿的元兇,其實連菸的包裝盒也有明確標示,卻很少有人把它當作一回事,以為自己可以雄振天下一輩子,殊不知中年而已,就要尋求美國黑金的幫助。

    有很多長期吸菸的老菸槍,在發生性功能問題時,會認為美國黑金就是仙丹,美國黑金的確拯救了無數男性,但如果你一邊服用美國黑金,可是每天仍然抽兩包菸,長期下來身體能獲得改善嗎,真的誰都無法保證,效果很好的保健品,也要搭配良好生活習慣,包含了飲食、睡眠、運動等,才能達到最好的治療效果。http://www.usa-blackman.com/

  • 犀利士cialisinin

    談男性保健食品選擇,為什麼是犀利士cialis?
    市面上較知名的男性保健食品如下
    1.犀利士Cialis
    2.藍色小藥丸Viagra
    3.樂威 壯Levitra
    4.必利勁Priligy

    以上幾種男性保健食品知名度排名為:
    藍色小藥丸Viagra>犀利士Cialis>樂威 壯Levitra>必利勁Priligy

    而他們之間的不同點在於
    1.產生藥效所需的時間長短不同
    2.藥效維持時間不同
    3.適合的使用方式也不同,有的需要空腹使用
    犀利士 http://cialisinin.com

  • 飛機杯

    正夯的飛機杯都是哪些人在買?
    近期夯到一度缺貨的飛機杯都是哪些人在買?
    會有此問的原因是因為某網友前陣子在論壇說到飛機杯都價格不菲,
    奇怪到底都是誰在買飛機杯?引來許多網友熱烈討論回應。
    網友回應幾種可能:
    1.母胎單身且一輩子不(交)打(不)算(到)女友
    2.遠距離
    3.老婆懷孕
    4.有錢的學生
    5.有錢的上班族
    6.有錢的老人

    其實市面上這麼多飛機杯,也可以輕易找到大牌子又平價的,
    只不過功能未必如頂級飛機杯那麼奢華。
    像是日本飛機杯最知名的品牌Tenga,也有百元有找的一次性飛機杯。
    重複性的有5、6百元的可以挑,需要花點時間多比較多看看。
    真的有興趣的可以從最基本的Tenga Spinner系列看起。
    http://masturbation-cup.com

  • 飛機杯

    飛機杯盲測Swag活動分享
    SWAG應該是2021男性最愛的平台之一,各式各樣影片跟直播主。
    前陣子剛推出還有話題新聞:飛機杯盲測Swag活動
    一群SWAG人氣主播與觀眾一起猜猜到底誰是真射?誰是假射?
    不禁讓筆者好奇,這種情況下使用飛機杯真的能射嗎?
    聽起來是飛機杯品牌聯名,確實噱頭十足。

    以免有人不知道SWAG是什麼,以下擷取自維基百科的內容簡單為大家科普一下:
    是一個以「一對一私訊」為名的情色聊天平台,由黃立成在2016年8月創辦。該平台於2017年12月轉手由 Sam Liu 經營。

    回頭來聊飛機杯,票選最快「繳械」的飛機杯款式排名如下
    1.Tenga電動版Flip 0黑色緊緻
    2.貝克杯電動飛機杯
    3.Tenga Flip 0強黑板
    4.Tenga Air-tech Fit經典真空
    http://masturbation-cup.com

  • 犀利士cialisinin

    犀利士 ptt網友推薦嗎?討論熱烈的原因是什麼?
    2021年開始犀利士 ptt上面的討論度突然提高,網友紛紛提出不同問題與看法。
    1.犀利士 ptt網友推薦嗎?
    2.犀利士跟傳統藍色小藥丸最大的差異為何?
    3.犀利士是一般保健食品還是藥物?

    有些專業的網友針對以上3個問題,整理了資料分享。
    犀利士 http://cialisinin.com

  • 飛機杯

    使用飛機杯應該搭配哪種潤滑液?
    相信男生都知道,使用飛機杯一定要搭配潤滑液使用。
    若不搭配潤滑液使用飛機杯,非常容易造成傷害。
    至於飛機杯要選擇哪款潤滑液作為搭配使用呢?
    由於矽性、油性都可能侵蝕不同材質的飛機杯進而造成碑體毀損。
    因此一般都建議使用「水性潤滑液」較為安全。

    許多大品牌飛機杯也會附贈潤滑液試用包,
    光是Tenga飛機杯一款潤滑液就有4種不同黏度可以選擇。
    使用者分享,越黏稠的潤滑液用起來越順手,可以大幅降低摩擦與不適感。
    看到這邊還是不知道如何挑選適合的飛機杯潤滑液?
    寄信給客服「給我最滑最黏稠的那款」就對了。

    切記使用飛機杯不能省略重要的潤滑液!!!
    http://masturbation-cup.com

回复给 dasyue 取消回复