1樓：好地方bug
@猹猹 大佬的回答很完善了，我來個簡單漸進版本的。我們設函式 表示乙個有 條邊的圖的三角形數量的最大值。
引理：乙個有 條邊的圖， 。
證明：
首先我們考慮這個圖是個完全圖，即存在 0" eeimg="1"/>使得 。這個時候，三角形的數量
我們假設 是最小的正整數使得 。令 ，不難證明 （否則有： ，這與 是最小的矛盾）。於是我們可以得到：
2樓：育空之心
採取貪心策略，如果已有的圖沒有構成完全圖，則在乙個沒有和其它頂點全部相連的頂點上加一條邊，並且每次都在這個頂點上加直到構成完全圖，如果已經構成完全圖則增加乙個頂點再在這個頂點上加一條邊。
這樣算下來如果n=kC2+a(a 3樓：猹猹 這個極圖還是好猜的。盡可能湊完全圖應該是最好的，即當n∈(k(k-1)/2,k(k+1)/2]時(k整)，達到最多三角形個數的圖應當是乙個k點完全圖，外加乙個點隨意地連邊到前k個點(直至用完邊數)。 這時的三角形個數是： k(k-1)(k-2)/6+(n-k(k-1)/2)(n-1-k(k-1)/2)/2。 這個式子當然可以只用n寫出來，畢竟k可以用有關n的根號取整式寫出來，不過太麻煩，我就不整了。為了方便我們姑且把此式記作f(n)。 證明它可以考慮調整法：即對遠離極圖的圖，做某種保邊數變換能讓此圖三角形個數增多且更接近極圖。 僅僅調整法怕是也不夠，還可以開個歸納法buff。 (以下d(x)是x點度，即與點x關聯邊個數，N(x)是x鄰居集，即與x形成邊的點組成的集合(因此d(x)=|N(x)|)) 此圖三角形個數為=不含a,b點的三角形+含a、b之一的三角形+含a,b兩點的三角形 其中：第二項=N(a)、N(b)匯出子圖中邊的個數，第三項=0(ab非邊時)或|N(a)∩N(b)|(a,b相鄰時)。 我們使用調整法，把a的鄰居中不是b的鄰居的全送給b，這樣總邊數不變，和式中第一項、第三項不變；而第二項變成： 故：不是極圖的做了此操作有可能是極圖；是極圖的做了此操作後不可能變為非極圖。 這樣，我們固定乙個點v，不斷讓這個點與其他點做此操作，把其他點的鄰居移給它。每次操作，v度數都不會下降；只要有與v不相鄰的點(不考慮孤立點)，都可以通過此方法把此點變成v的鄰居，因此，操作完成後，v與所有其他點相鄰。 注意到，此圖經過操作仍是達到最大三角形個數的圖。 現在我們用歸納法，刪掉此點v。 由歸納假設，剩下的圖有至多f(n-d(v))個三角形。而原圖與v相關的三角形(即因刪點被破壞掉的那些)個數是刪後圖的邊數，故未刪前三角形個數≤f(n-d(v))+n-d(v)。 為了方便，我們可以加強命題，證明極圖(非孤立)點數一定是那個k+1，這樣d(v)也被鎖死，不難證明f(n)≤f(n-k)+n-k，等號顯然可以取到。 4樓： 之前沒空想這個問題，不過我猜測就是「盡量組成完全圖」時三角形最多。之後有時間就寫個思路。 已經有大佬寫了，我沒什麼新的想法，溜了（ 趙馮平 1.做9輪冒泡，把最大的9條邊 冒泡 到最後位置，這時前面n 1條邊是無序的，但其權值小於後面9條邊，而後面9條邊是按權值從小到大排序的。進行了9 n次冒泡操作，複雜度O n 生成的邊的序列成為A，A的每個元素包含邊的起點 終點及權值。2.類似克魯斯卡爾演算法，按第1步生成的順序A中，從頭到... Chester 氣息 共鳴 聲帶的閉合，這些是影響音色的主要內容，他們的力度 壓強 閉合程度等等，你能有多少種組合就有多少種聲音，另外共鳴位置又有很多，看你自己了。 Da老師 這個問題說起來是複雜的。音色分為基礎音色和包裹物兩個層面，單純聲帶的音色特質其實是固定的，但是使用方式不同色彩又會不同，比如... Lancewu 已知定理 在乙個圓內，有條直線，個 交點 則圓被分為塊。此定理對平面同樣成立 定義一下 如何計算交點的數量 即 兩線相交一點為，三線相交一點為，線相交一點為，只要碰到圓的都不算。證明 假設圓內已經有很多條線，或者沒有，現在加上一條線。從圓某一點開始延長一條線的過程中，每碰到一條線，就...乙個連通圖有n個頂點，n 8條邊，權值各不相同，如何設計O n 的演算法計算最小生成樹
乙個人的嗓子最多有幾個音色？
在乙個平面內n條直線和1個圓最多能把乙個平面分成幾部分？