1樓：猹猹
①邊數：
上界某人已經給出了，乙個平衡二部圖在某條邊上額外塞乙個點就是極圖(未必唯一)。邊數貌似[(n-1)/4]+1。
下界就讓這個圖盡量不平衡(未必唯一)，邊數2n-5。
可能取到的邊數可以考慮以下圖：
這種圖顯然是符合條件的一系列圖，事實上這就是5圈的blow-up的一種特例，s=t=1就是邊數最大的情況，a=...=1就是邊數最小的情況。而取t=2可以發現，邊數=(a+2)n-a-5a-4-s，s是可以在1到n-a-4之間任取的。
僅從這點即可發現，邊數應該是沒有什麼整除性的事實的。
事實上，我猜測對於一定範圍內的數，都有辦法構造能取到有對應邊數的飽和圖(僅僅靠我這類圖應該不足以cover能取到的所有值，不過大部分是可以的)，而在接近上界時才會出現部分取不到的值。(之所以這樣猜是因為曾經做過類似的問題_(:з」∠)_)
②度數由某個經典結論，此圖最小度至多是[2n/5]；至少的話，1肯定不行，2很好構造出對應的圖。
此圖最大度最小值是個有趣的問題，我得想想(反正0.2n到0.3n之間，不知道是不是個open的問題，先猜0.3n)；同上，最大度最大能取到n-3。
在上下界之間的數，應該都能取到，用我構造的那個圖族應該能湊出來。
值得一提的是，此圖四個框的點數都取奇數是能使得其為尤拉圖的。即n為奇數時，此圖可以是尤拉圖。而n為5的倍數時，考慮5圈blow-up也可知其為尤拉圖。
事實上，每部奇偶性相同就能做到，因此，對較大的n，都能使其尤拉化，而6、8(n≥5)兩個數就~( ︵` )~。
③圍長隨便反證一下就知道，此圖一定有(匯出的)5圈。因此圍長非4即5，顯然都可能取到。
④最長圈、最長路
這圖自然對部分n很容易有H圈、H路或者很長的圈，你可以考慮幾乎平衡的5圈blow-up。而想壓小最長圈/路，把我的例子中a、s、t都取1，這圖最大圈/路都只能是5。
⑤色數概率方法上不是有個可以同時增大色數和圍長的玩法嘛。你可以取這樣的圖，添邊至飽和，色數就可以要多大有多大了 |ω｀)。
⑥表象結構
一般情況下，這圖應該有大量匯出的4圈5圈，但硬湊也能湊出匯出的大一點的圈。而且，對這個圖的任意5圈，可證此圖的其他點必與此5圈點之一相連。我想稍微小心一點以這種想法隨便畫，很容易構造例子的。
特別地，Peterson圖就是乙個這樣的飽和圖，而它大概是5圈blow-up體系外的乙個典例(然後你可以blow up了Peterson圖，又是一堆例子(逃))。
2樓：「已登出」
這是很經典的Turan圖，不含三角形的極圖是完全平衡二部圖。考慮非二部圖G，並且取最短奇圈C，C的長度不小於5。可以證明對任意不在C上的頂點v到C上的鄰點不多於2個。
這樣極圖的構造就很簡單了。
考慮長度為5的圈 ，將G的頂點集分成三部分: ，滿足：
1.匯出子圖 是完全平衡二部圖。
2. 上的每個點和 中的 相鄰。
3. 中的每個點和 中的 相鄰。
可以證明這樣的圖就是符合題意的極圖。
這個極圖當然是唯一的.非正式的證明一下,引用乙個結論:
結論1:不含三角形的 階圖 的最大邊數是 ,當且僅當 時取等號.
現在設 是不含三角形的非二部極圖,考慮 中最短奇圈 ,設 的長度為 ,於是有: . 可以證明:
結論2: .
那麼來估計 的邊數:
匯出子圖 不含三角形,根據結論1:
根據結論2:
然後: ,
全部加起來求最大值,可知等號成立當且僅當 以及上面兩個不等式的等號成立,那麼即上面所構造的極圖.
3樓：fjdk eim
我寫了個程式列舉極大的、有n個點的、沒有三角形的非二部圖，然後從n=5到14都跑了一遍。這樣的圖非常多，數量大致是關於n指數級增長的。其中邊最少的圖有2n-5條邊，最多的有 條邊。
邊最少的例子： 。a,b,c,d,e構成乙個C5，每個 和a， 和c之間都有邊。
邊最多的例子： ，其中 。任取 ，使得 。 這些圖的結構和平衡的完全二部圖很相似。
以上結論我還沒有證明，只在n<=14時由計算機驗證過。
最後說一下我的程式怎麼寫的。先用nauty自帶的gtools裡面的geng程式生成所有n個點的、無三角形的、二連通圖，然後我寫了另乙個程式選出其中非二部的、任加一條邊會產生三角形的圖。
4樓：fffasttime
首先這樣的圖中不能有大於5的且環上沒有其他弦的環，不然在對角線上加一條邊無法構成三角形。換句話是任何誘導子圖都不同構於Cn(n>5)。另外因為是無三角形的非二部圖，圖中必須包含大於3的奇環。
因此圖中必須有C5（更大的奇環需要加弦變切成五元環）。此外，任何長度等於3路徑兩端未連線而且連線無法形成新的三角形，則這條邊必須相連。
考慮往五邊形ABCDE上繼續加點。不妨設五邊形上的某點A與環外一點P相連，則P不能與B或E有邊，否則構成三角形；另外P和C或D其中之一必須有邊，否則之後連PC無法形成三角形。以同樣的方式在A上繼續加P' ，構成的圖都滿足條件。
之後要是在P點上新增其他相鄰點Q，則Q必須與D或E之一相連，且Q和B必須相連。再對Q構造其他相鄰點也一樣。所以這樣構造出來的圖誘導子圖中至少有乙個C5，可以有多個C4或C5，沒有Cn(n>5)，且沒有度為1的點，任意兩點間的距離為1或2。
周長相等的三角形中，什麼三角形面積最大？
流數術 等邊三角形，理由如下。設想固定三角形任意兩個頂點，周長一定時，另一頂點軌跡是以固定兩點為焦點的橢圓，所以另一頂點在橢圓短軸兩端時面積最大，即三角形每個頂點都在另外兩頂點的中垂線上，易證三角形等邊。 自學生 用我發現了 時間生命是一對同在的自然法則 觀點看，內等邊三角形和外半徑週期形，是一對同...
正三角形的臉適合什麼髮型？？？
不請自來 首先不要留太長的頭髮，嘗試了好多年，目前發現下圖的比較合適。看，這寬大的咬肌，下顎角已經沒有角度了，直接圓著過去，哭暈也沒辦法。頭髮長度短了下巴會寬的明顯，太長了頭顯大，會很厚重，齊肩稍好點，髮尾盡量打碎，不要太整齊。拍照找角度，合照臉側著一點。另外，能不紮起來就不要扎，扎了缺點過分暴露，...
三角形穩定性的本質是什麼？
鴦寚礥蕋 我們已經知道SSS 三邊對應相等的三角形全等 所以當乙個三角形的三邊長度固定時，這個三角形的形狀和大小是唯一的，不可能有變化。這就是三角形的穩定性。 從方程的角度理解 已知三角形三條邊的長度，三角形有唯一的解 而已知四邊形的四條邊，能夠得到無數個四邊形的解 比方說正方形和各種菱形 所以實際...