NJScientia

2024年10月26日星期六

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

故得證

2024年10月21日星期一

圖論 - 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

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

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

2024年10月20日星期日

演算法觀點的圖論習題 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 的長方形直接證明這個結論的正確性。

2023年4月12日星期三

色彩學筆記: 牛頓, 光與感知

(圖部分為假想圖, 透過Midjourney所做, 部分為 wiki )

(文為引導 chatGPT 所完成)

牛頓在 1666 年的夏季，通過一個實驗室的小窗戶，觀察到一道光線照在一個三棱鏡上，並發現這道光經過三棱鏡後被分解成不同顏色的光譜，包括紅、橙、黃、綠、藍、靛、紫七種顏色。牛頓意識到光在經過透明介質時，可能會產生不同的折射角度，從而產生不同的折射率，因此將光分解成不同的波長。

( 此圖為MJ 製作假想圖, 並非真實的狀況,

紅光的偏折小, 紫光的偏折大, 可以參考這個網頁的三稜鏡圖 -

台北教師 e 教材 )

牛頓進一步進行實驗，將光譜通過另一個三棱鏡進行反射，並將反射光譜通過一個透鏡重新聚焦成一束白光。通過這樣的實驗，牛頓發現光譜並非連續的，而是由許多不同顏色的光線組成的。牛頓還發現，不同顏色的光線在折射和反射時具有不同的性質，例如紅光的折射率較小，而紫光的折射率較大。

( 此圖為MJ 製作假想圖, 並非真實的狀況, )

牛頓的光譜實驗對色彩學有重大影響。在此之前，人們對顏色的理解只停留在基本的紅、橙、黃、綠、藍、靛、紫七種顏色，並無法解釋這些顏色的本質和形成機制。通過光譜實驗，牛頓揭示了光是由不同波長的光線組成的，並且不同的波長產生不同的顏色。這種新的理解對色彩學產生了深遠的影響，推動了後來的光譜分析和光學技術的發展，也揭示了光譜在物理、化學、天文學等領域的應用。

影像透過眼睛進入，經過角膜、瞳孔、晶狀體和玻璃體等透明介質的幫助，形成一個倒置的、小而清晰的影像在視網膜上。視網膜包含許多光敏細胞，包括錐狀細胞和桿狀細胞，它們對光的強度和顏色有不同的敏感度。當光照射到視網膜上時，這些光敏細胞會將光轉換為神經信號，通過視神經傳送到大腦的視覺皮層，形成我們所看到的影像。

視覺錯覺是因為我們的大腦對於收到的視覺訊息進行了解讀和詮釋，但是有些時候，我們的大腦會對收到的訊息進行錯誤的詮釋，這種錯覺就被稱為視覺錯覺。

例如認知錯覺: 鴨兔錯覺

ref: https://zh.wikipedia.org/zh-tw/%E8%A6%96%E9%8C%AF%E8%A6%BA#/media/File:Duck-Rabbit_illusion.jpg

關於"一朝被蛇咬，十年怕草繩"的狀況，這是一種經驗效應的例子。當我們經歷過某種壓力或不良體驗時，這種經驗會在我們的大腦中留下深刻的烙印，使我們更容易受到相似情況的影響。因此，如果一個人曾經被蛇咬過，即使在未來看到的只是草繩，他們仍然可能感到害怕，這是因為他們的大腦已經建立了一個與蛇相關的恐懼反應。

相似地，視覺錯覺可能是由於我們大腦中的經驗效應或刻板印象引起的。當我們看到某些圖案或形狀時，我們的大腦可能會根據過去的經驗或預設的印象，對這些圖案或形狀進行解讀和詮釋，從而引起錯覺。這種現象可以幫助我們更好地了解我們大腦如何處理視覺信息，以及我們如何對世界進行感知和詮釋。

例如, 著名的 M.C. Escher是一位荷蘭畫家，他以他的幾何學圖案和視覺錯覺作品而聞名。Escher的繪畫作品將幾何學和視覺錯覺技巧巧妙地結合在一起，創造出了一些極為獨特的作品。

ref: Wiki

Escher的繪畫作品常常包含著一些錯覺性的元素，例如不可能的幾何形狀、空間錯置、和無限循環等等。他通常會使用對比強烈的黑白調，來增強視覺效果，讓觀眾感受到作品的強烈張力。

Ref: wiki

Escher的作品經常被描述為「無限的循環」，因為他的作品中經常包含著重複的圖案和幾何形狀，這些形狀看似無法連接在一起，但是在整張作品中卻形成了一個無限循環的效果。他的作品經常被用來表達哲學和科學思想，如相對論、拓撲學和幾何學等等，具有非常高的藝術價值和科學價值，他的創作風格和獨特的視覺效果，對後世的設計師、藝術家和科學家產生了很大的影響。