作者:
Hatred (╮(⊙＿⊙∥)╭)
2015-01-02 18:04:58小妹是鍵盤數學家、30cm、E cup、溫拿、高富帥、勝利組。
在圖論（graph theory）中，無向圖（undirected graph）指的是一堆點和其間的邊，其
中每個邊可以將兩個點連起來、並且沒有特定的方向。以下將「無向圖」都簡稱為「圖」
。
如果一個圖中，每個點接觸的邊數都相同，則稱之為正規圖（regular graph）。
圖的相鄰矩陣（adjacency matrix）是一個方陣（square matrix），其中第i列第j欄表
示是否有邊連接第i點與第j點，若有，則第i列第j欄為1、否則為0。
正規圖的相鄰矩陣的最大特徵值（eigenvalue）會等於每個點接觸到的邊數，如果除了最
大特徵值外，諸特徵值取絕對值後的最大者與最大特徵值相差很大，則稱該圖為拉馬努金
圖。在此不贅述「很大」是多大。
拉馬努金圖的諸多性質與隨機正規圖很類似，對拉馬努金圖上的任兩個點集S、T而言，
S、T之間的邊數會與隨機正規圖上S、T間的邊數相仿，這是擴張混合引理（expander
mixing lemma）的特例。
對各種有一定機率犯錯的隨機演算法而言，我們可藉由重複執行該演算法多次、並取諸次
輸出的多數決，來減小錯誤機率，這個過程中需要的亂數個數可利用拉馬努金圖有效地減
少。
拉馬努金圖是一種擴張圖（expander graph），一個懸宕多年的問題是：如何利用最少的
記憶體判斷任意給定圖中的兩點是否能用一條路徑連起來，這個問題在數年前被利用擴張
圖解決了。
※ 引述《ma4wanderer (師大之狼)》之銘言：
: 大家好 乳頭 堅挺!!
: 拉馬努金，除了谷山豐、艾迪續以外，哥崇拜的數學家之一
: 家裡窮，沒受過正規高等數學教育，32歲英年早逝
: 但在倉促的一生中寫下上千條恆等式
: 能在他的諸多恆等式中看出他驚人的洞察力，如
: 1/PI=(2sqrt(2)/9801)＊ sum{ [(4k)!(1103+26390k)] / [(k!)^4＊369^(4k)] }
: 傳說哈代探望拉馬努金病情的時候，哈代說他搭車牌1729的計程車來，
: 哈代說這個數字沒什麼特別之處，相當無趣
: 拉馬努金跟他說，1729很有趣，
: 1729能寫成兩個數的立方和，而且有兩種表示：1729=1^3+12^3=9^3+10^3
: 不只如此，這種情況下，1729是最小的
: 告訴我有沒有拉馬努金的八卦，好撲好!!