演算法觀念的圖論 習題 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 就已經符合題目所需

故得證

圖論 - 1 定義

無向圖 G = (V, E)

V : Vertex 點 

E : Edge 邊

--

e = {u, v} 

   e : edge 邊

   e is in E

   u, v 邊兩端點

   u, v is in V

--

deg(v) : 該點的度數 : 多少邊從該點引出

--

握手引理 : handshaking lemma

對任意無向圖 G = (V, E) , 

所有點的度數和, 為邊數量的兩倍: Sum( deg(V) ) = 2|E|

 

--

奇點 : 該點的邊數量為奇數個

偶點 : 該點的邊數量為偶數個

根據 握手引理 可知, 無向圖的奇點數目為偶數個

--

walk 道路 : 點邊的序列 : v0e1v1e2v2...eivi

trail 行跡： 一條邊不重複的道路

path 路徑 : 一條點不重複的道路

Euler trail / 歐拉行跡 : 有條行跡可以經過所有的邊

Euler tour / 歐拉迴路 : 封閉的歐拉行跡 

歐拉行跡 可以搭配 Leetcode 332 之類的題目來看 - kotlin leetcode 332

--

如果無向圖有一條歐拉迴路, 那麼每一點一定是偶點 

如果無向圖有一條開放的歐拉行跡, 那麼一定恰好有兩個奇點

演算法觀點的圖論 習題 1-1

前面為自己所想紀錄, 不一定正確; 圖片為 chatgpt 3.5 所回答, 非正解; 

最後 chatgpt 4 回答的, 看來是對的;

Q: 證明假設把 8x8 的 西洋棋盤上 位於同一條對角線上的兩個頂角格子去掉(於是剩下一個只有 62 格的棋盤), 則這個棋盤沒辦法分割成若干個 1x2 的長方形

由上而下, 由左而右, 將格子標記成 (0,0) ~ (7,7), 假設 (0,0) 和 (7,7) 格子被拿掉

在 第 0 row : (0, Y), 因為 (0,0) 被拿掉, 剩下 7 個格子為奇數, 所以從第 0 row  開始往下擺直的

1x2 的長方形有奇數個;

因為第0row 擺直的有奇數個, 所以第 1 row 擺直的有奇數個...到最後第 6 row 擺直的有奇數個

因為 0~6 為 奇數個 rows, 所以所有擺直的有奇數個

同理從 第 0 column 推導, 可得知, 所有擺橫的有奇數個

這樣所有 1x2 的 長方形 有 偶數個; 

但 62 格 只有 31 個 長方形是奇數個, 矛盾, 所以無法分割

Q: 二分圖的一般性原則, 有可能是 定理 1.8 ?

    二分圖 若且唯若 沒有奇圈

待續

--

2024.10.21

今天問了一下 chatgpt 

chatgpt 3.5 的時候, 它還不會解, 打了一個煙霧彈

到 chatgpt 4 時, 好像這思路有點道理, 比較像圖論的做法 (著色相關定理?) 

這樣比較能回答第二個問題

Ans: 

要證明這個問題，我們首先觀察原始 8x8 的西洋棋盤。

這個棋盤可以看作是一個由 64 個格子組成的棋盤，其中有黑白相間的格子排列。

如果我們把棋盤上的格子來進一步思考，那麼不妨把左上角的格子視為白色。 在這樣的黑白交錯排列中，無論是在橫排還是縱列上，兩個相鄰的格子一定是一黑一白。

因此，一個 1x2 的長方形（也就是所謂的「骨牌」）必定覆蓋一個黑色格子和一個白色格子。 8x8 的棋盤中擁有 32 個白色格子和 32 個黑色格子。

現在我們去掉了兩個位於同一條對角線上的頂角格子，這兩個被去掉的格子的顏色必定是相同的。這是因為棋盤的對角線上，所有格子的顏色都是一樣的。因此，如果第一個頂角格子是白色，那麼另一個被去掉的頂角格子也會是白色（或都為黑色）。 

去掉這兩個相同顏色的格子之後，留在棋盤上的格子們會呈現不平衡的色塊數。

例如，如果你去掉了兩個白色格子，那麼棋盤上便剩下 30 個白色格子和 32 個黑色格子。 

由於每個 1x2 的長方形要求必須覆蓋一個白色和一個黑色格子，因此在剩下的 62 格棋盤中，我們總有兩個格子的顏色無法成對，導致無法用 1x2 長方形完整地覆蓋。 

因此，去除棋盤上同一對角線的兩個頂角格子後，剩下的棋盤無法被完全分割成若干個 1x2 的長方形直接證明這個結論的正確性。