演算法觀念的圖論 習題 1-4

鴿籠原理 - wiki

題目 1-4 : 當 n >= 2 時, 假設 2n 個人當中, 每個人至少與其他 n 個人認識, 證明其中至少有四個人, 使這四個人能圍著圓桌而坐, 讓每個人兩旁的人都是他認識的人

解答 1 : (此為自己所想, 不一定正確)

這問題很像鴿籠原理的思路

假設 A 是 2n 個人當中的一員, A0 ~ An-1 是 A 認識的人, 會有兩種情況: 

     情況 1 : A0 ~ An-1 中 有兩位彼此認識, 

        例如 A0, A1 彼此認識, 將認識的人之間連線, 

        則 A, A0, A1 可以畫成一個彼此認識的三角形

        如果有位認識 A, A0, A1 中其中兩位, 這四人就可圍著圓桌而坐, 符合題目需求

        假設沒有這樣一個人, 則 

        (1) 至少有 n-1 位認識 A, 但不認識 A0 和 A1 

        (2) 至少有 n-1 位認識 A0, 但不認識 A 和 A1 

        (3) 至少有 n-1 位認識 A1, 但不認識 A 和 A0

        這樣總共人數為 3n 超過 2n 人, 所以根據 鴿籠原理, 可以找到這一位符合要求 

    情況 2 : A0 ~ An-1 中 彼此都不認識

         如果 2n 人中, 都不存在 一位 A 符合情況 1 的話, 

          則這 2n 人, 可以畫成一個 2分圖 (A0 ~ An-1) 和 (B0 ~ Bn-1)

          每個 Ai 都認識 B0~Bn-1, 但對其他 Ai 都不認識

          每個 Bi 都認識 A0~An-1, 但對其他 Bi 都不認識

          這樣其實 A0 - B0 - A1 - B1 - A0 就已經符合題目所需

故得證