1樓：Bing
應該是個老題目了。 整體思想如下：
首先人為定點，認識關係為邊，構圖。假設N(vi)表示vi的相鄰邊 。證明2種情況：
2個熟人v1, v2, 有相同個數的熟人, 也就是v1和v2的出邊個數相等。
如下圖： v1和v2相識，那麼N(v1) 裡面除了v2至少還存在乙個vi（i != 2）, vi 不屬於N(v2), 否則有共同熟人了。
那麼vi和v2之間恰有2個熟人， 除去v1，至少還有乙個點，假設為vj, vj 屬於 N(V2)， 同時，對於N(v1)中的另外乙個點vk, vk 和vi 不可能同時跟vj相鄰， 那麼vk和v2之前至少存在乙個點vl， 使他們共同的相鄰點。按照這種思路， 我們知道N(v1) >= N(v2), 反過來推到，我們可以知道N(v1) <= N(v2). 因此N(v1) = N(v2)。
2個不是熟人的人有相同個數的熟人。即2個不相鄰的點，必有相同的出邊數。 證明的方法跟前一種情況類似，假設v1和v2不相識。
那麼v1和v2有2個共同的熟人(vi, vj), vi，vj 屬於N(v1), 同時vi, vj屬於N(v2)。 N(v1) = N(v2) = 2, 符合假設，證明結束。
如果，存在vk 屬於N(v1), 但是不屬於N(v2), 那麼按照第一步的證明可知，vk 和v2必有相同的出邊，且恰好有2個熟人，因為vk 不可能跟vi, vj相鄰（否則相鄰的點出現了共同熟人）， 所以v2至少有2個其他的相鄰點， 屬於N(v2)，其中2個(vl, vr)跟vk構成熟人關係。因此， N(v1) <= N(v2). 同理，翻過來也能證明 N(v2) <= N(v1)。
即證： N(v1) = N(v2).結束。
哪些看似與圖論無關的問題可用圖論模型解決？
Ray Zhang 那必然是random matrix的經典結論wigner semicircle law啊。對於乙個Wigner矩陣，我們考慮它特徵值 Wigner矩陣是Heimitian 的經驗譜分布 empirical spectrum distribution ESD 在經過scale 處理...