1樓：Ray Zhang
那必然是random matrix的經典結論wigner semicircle law啊。
對於乙個Wigner矩陣，我們考慮它特徵值（Wigner矩陣是Heimitian）的經驗譜分布（empirical spectrum distribution ESD)，（在經過scale 處理之後），當矩陣的維數趨於無窮的時候，ESD會收斂到所謂的半圓律，即乙個以原點為圓心，2為半徑的上半圓。
Moment method的證明方法在Terry Tao的 Topics in RMT裡有具體的說明，或者AGZ Introdutio to RMT但是這個方法有個致命的侷限就是依賴於Wigner matrix上半對角元iid的independence的限定，使得moment method無法推廣到一般的ensemble上，於是就有所謂的free probability來處理non-Hermitian的情形。
反正我第一次看到moment method的這個證明時候是很震驚的，典型的還tm能這樣證。。。純碼字，沒敲公式，寫的很糙，只是把證明的思路描述了一遍，具體每一步的分析和估計都還是很硬核的，尤其是Cauchy transformation的方法，第一遍看是收穫滿滿的。
總之，隨機矩陣這個領域博大精深，方興未艾，有從統計物理出發的，Riemann-Hilbert problem，local law and universality，random graph，high-dimensional statistics，甚至analytical number theory，quantum dynamical system各種匪夷所思的領域都有random matrices的影子（我就是個名詞黨。。，老闆是universality這個領域的先驅）。然而一切精彩的工作都開始於semicircle law。
2樓：
說乙個比較簡單的例子。
對自然數序列 進行三染色，即構造對映 。證明對於任意染色方式，序列中一定存在三個數 同色，且滿足 。
構造17個頂點的完全圖 ，並對其邊進行三染色，染色方案為：任意的邊 的染色與 相同。根據廣義的Ramsey Number定義， ，因此對 的邊進行任意三染色，一定存在單色三角形 。
此時，滿足 ，即自然數序列中存在同色的三個數 。
在此基礎上，如果要求 ，只需要求 中任意兩個頂點對應的值相減結果唯一即可，如對1至 進行三染色，圖的17個頂點分別對應 ，命題同理得證。
這個命題推廣的結果是Schur's Theorem，證明了對自然數序列進行任意n染色，並給定任意k，都存在 同色且滿足 。
3樓：鄭欣怡
證明驗證乙個 code 是 Uniquely Decipherable 可以在 Polynomial 時間內解決
有乙個經典思路是先證明這個問題可以在 Polynomial 時間內等價成 Graph Reachability 的問題，然後再證明 Graph Reachability
這個問題似乎比較 Computaional Complexity 和大神們說的問題 level 差距比較大
4樓：Fan You
不知道腎移植算不算開起來和圖論模型無關。
Abraham, D.J., Blum, A.
and Sandholm, T., 2007, June. Clearing algorithms for barter exchange markets:
Enabling nationwide kidney exchanges. InProceedings of the 8th ACM conference on Electronic commerce(pp. 295-304).
ACM.
5樓：
6樓：shihang Wen
寫乙個在最近在學習的吧，利用複雜網路研究上市公司之間的擔保關係以及銀行的同業拆借關係。
金融機構之間有著多種連線的方式，如債權債務關係，擔保關係，所有權關係。這種情況我們可以用網路理論來刻畫這樣的關係。所謂的網路，就是由節點和邊構成的集合。
我們將我們所要研究的金融機構都定義成節點，將他們之間的擔保關係定義成邊，這樣就形成了乙個圖。將擔保的金額賦值給邊，那麼我們可以形成乙個加權圖。利用圖論中的一些性質與結論，我們可以對擔保市場或者是銀行間市場的結構做出分析。
在擔保市場種存在著多種的擔保關係，例如連帶責任擔保，保證擔保，一般擔保等，我們以擔保關係來分類構建不同的擔保網路，例如連帶責任擔保網路，保證擔保網路等等，這樣就形成了多層網路。
擔保網路的例項：
從該擔保網路中可以看出，某一家上市公司都是與多家上市公司有著擔保關係的。我們將其抽象成圖，即每乙個節點的度數（連線的邊數）都是大於或者等於1的。同時，每乙個節點的度數也是有一定的區別，說明節點在網路中的重要性也是不一樣的。
通過centrality（中心度）這乙個指標，我們可以刻畫節點在網路中的重要性，尋找出擔保網路中最關鍵的上市公司。
事實證明，擔保市場網路是具有複雜網路的特徵。2023年，Watts和Strogatz首次提出了小世界網路模型。所謂的小世界網路，就是兩個不相鄰的節點，經過有限的步數可以相互到達。
乙個比較通俗的案例就是六度分隔理論：https://
zh.wikipedia.org/wiki/%
2023年，Barabasi和Albert提出網路具有無標度的性質，既滿足冪律分布。所謂的無標度，就是大部分的節點只和很少一部分節點連線，而這一少部分的節點度數極大。比較典型的例子就是馬太效應。
擔保網路的小世界性
一般的擔保網路平均路徑長度為18.2，聚集係數為0.103，均小於起同等規模的隨機網路。
我們可以認為這是小世界特徵。在這樣的網路中，資訊傳遞較快，並且少量改變幾個連線就能夠改變網路的效能。
無標度性：
這是擔保網路度的分布，網路表現為比較明顯的冪律分布，其節點的連線狀況具有不均勻的分布性。
吉豔冰, 王偉, 趙亞偉. 基於複雜網路理論的擔保網路研究[J]. 複雜系統與複雜性科學, 2014, 11(2): 17-23.
7樓：
集合合併問題， 將任意兩個有相同元素的集合合併。
比如集合A的元素為, 集合B的元素為, 集合C的元素為, 集合D的元素為
則合併後的集合應該為,
一種解決方法就是借助圖論裡將1，2，3，4，5分為作為Node，其中根據給出的資訊將1，2，3，4結點進行連線，最後該問題轉化為尋找所有連通圖的問題。
8樓：oscar
既然題主貼了acm的標籤，我就舉乙個演算法競賽方面的例子吧（某波蘭比賽試題，bzoj上有，忘了題號）乙個人有n個杯子，編號1～n，每個杯子裡都有一些球。
你可以花費c_ij的錢詢問魔術師編號大於等於i且小於等於j的杯子中一共有多少球。
問至少要多少錢才能知道每個杯子裡各有多少球
9樓：藥罐子千里冰封
不知道地圖裡的河流生成算不算無關，不過這可以用A*做(搜尋應該屬於圖論吧)。而且效果還不錯，我的那個玩具是記錄了每個座標的高度的，那麼就可以有山和谷的概念，也就有了湖和峰。
河流生成我是用的A*從高往低走，基本上都是走的鞍部，看起來還挺真實的。
10樓：王小虎
[1703.02050] Topological quantum chemistry
圖論解決拓撲材料問題，應該會出現在nature或science
11樓：赤風
2SAT
Problem 1823. -- [JSOI2010]滿漢全席線性規劃（部分題目可以用網路流做）
Problem 1061. -- [Noi2008]志願者招募dp或者費用流
Problem 2424. -- [HAOI2010]訂貨差分約束系統
Problem 2330. -- [SCOI2011]糖果
12樓：冒泡
當然了，任何np問題都能轉npc，npc裡隨便挑個圖問題就好
13樓：三三
貝葉斯網路和馬爾科夫網路，都可以用有向或無向圖表示。於是你會發現，概率和圖論竟然聯絡起來了，然後就可以名正言順地開始「概率圖模型」之旅了。
14樓：張宇森
如果嚴格意義上來說圖論模型的問題就很多了：
資料結構的：線段樹，k-d樹，主席樹，樹套樹，treap，劃分樹，splay，map（紅黑樹），二叉搜尋樹，平衡二叉樹，並查集還有很多。能解決的問題幾乎和圖論不沾邊。
還有一類是在建圖上不怎麼沾邊的：網路流，迴圈流，mcmf，上下界網路流，2-sat，差分約束系統，基本上問題和他最原始的定義無關。
15樓：「已登出」
隨便舉乙個例子：
原題：There is a sequence X (i.e.
x[1], x[2], ..., x[n]). We define increasing subsequence of X
as x[i1], x[i2],...,x[ik], which satisfies follow conditions:
1) x[i1] < x[i2],..., 2) 1<=i1 < i2,..., As an excellent program designer, you must know how to find the maximum length of the increasing sequense, which is defined as s. Now, the next question is how many increasing subsequence with s-length can you find out from the sequence X. For example, in one case, if s = 3, and you can find out 2 such subsequence A and B from X. 1) A = a1, a2, a3. B = b1, b2, b3. 2) Each ai or bj(i,j = 1,2,3) can only be chose once at most. Now, the question is: 1) Find the maximum length of increasing subsequence of X(i.e. s). 2) Find the number of increasing subsequence with s-length under conditions described (i.e. num). 翻譯： 給你乙個序列，求出其最長上公升子串行，並給出這種長度的子串行有幾個，注意每個子串行之間不能有交叉。 caoglish 睡覺 良好的睡眠的有兩個功能很重要，乙個是精力恢復，可以為第二天精神集中最好準備。如果精神不集中，你就要消耗大量精力來保證清醒，反而無法集中在學習上。第二，睡眠有自動整理白天學習內容的功能。另外，良好睡眠有提高記憶力，保證智力良好發育的功能，所以要學習學得好，得到良好睡眠是非常重要... emotional 003 不請自來。許光漢主演了 想見你 想見你 中王詮勝送給黃雨萱的戒指上寫著Only If You Asked To See Me，這句話出自西蒙波伏娃的 越洋情書 越洋情書 是西蒙為薩特所寫，薩特和加繆恩怨情仇冗雜繁長，從摯交到因為蘇聯問題決裂。所以四捨五入許光漢和加繆也可以... 幾百年前德意志的幾座橋推動了電腦科學的發展 柯尼斯堡 Konigsberg 問題 尤拉 Leornhard Euler 解決了柯尼斯堡問題，由此圖論 Graph Theory 誕生。圖論主要研究點線之間的關係。到現在圖論已經發展出很多分支。其中，網路拓撲 Network Topology 圖論的眾多...有哪些看似與學習無關，卻關係很大的能力與前提？
有哪些 看似無關，實則有很大因果關係 的例子？
哪些新事物的出現，引發了看似毫無關聯的領域的變革？