1樓：baoxiaozhai
經過近1年的時間，我覺得我終於得到了解答，中間想了很多走不通的辦法，最終的思路突破是翻到了組合數學教材中的乙個定理。下面簡要描述一下解答的關鍵點，假設[ ]表示向上取整：
第一、顯然這是乙個圖論的問題而不是組合幾何問題，平面中的點就是圖論的點，平面的線段就是圖論的邊，線段的長度是圖論邊的權重。題目目標是證明存在長度至少是[2m/n]的尤拉路徑，每條邊的權重遞增。
第二、把這個無向圖可以轉換為有向圖更為方便，無向圖的每條邊轉換為正反兩個方向的有向邊，有向邊的權重和無向圖的邊的權重一樣，轉換有向圖後一共2m條有向邊。題目目標是證明存在長度至少是[2m/n]的有向尤拉路徑，每條邊的權重遞增。
第三、從組合數學中的Dilworth定理去思考，有向圖中的兩條邊，從一條邊如果存在權重遞增的方向一致的有向尤拉路徑到達另一條邊，則認為兩條邊之間是乙個偏序關係，有向尤拉路徑並且邊的權重遞增則認為是各邊組成的乙個鏈，為了使用Dilworth定理，需要證明有向圖中的反鏈最多n條有向邊。如果證明了這個結論，則根據Dilworth定理，有向圖可以最少拆為n個鏈，必然有乙個鏈的長度至少是[2m/n]，即使這個鏈裡的邊在圖中不相鄰，補充上路徑中中間的邊，還是滿足要求的有向尤拉路徑，長度至少是[2m/n]，權重遞增
第四、為了證明反鏈最多n條有向邊，只需要證明任意n+1條無向邊的圖中，轉換為2n+2條有向邊的有向圖之後，任意取n+1條有向邊，必然存在兩條邊滿足偏序關係，只需要證明把2n+2條有向邊可以分拆為n條權重遞增的有向尤拉路徑即可，也就是拆為n條鏈，在證明這個結論的時候，推廣一下就可以證明直接可以把2m條轉換後的有向邊的圖直接拆分為n條有向尤拉路徑，權重遞增。關鍵的簡單情況是無向圖中度數是3的點轉換有向圖後，怎麼把這個點的這些有向邊拆為鏈。
第五、轉換後的有向圖，一共n個點，每個點的所有出邊中，比如任取點A，有乙個權重最小的出邊，這條權重最小的出邊作為尤拉路徑的起始邊，這條邊的另乙個點比如對於點B是入邊，點B也有出邊，這些出邊中，權重恰好比AB大的作為尤拉路徑的第二條邊，比如是BC，對於點C，BC是入邊，再從C點的所有出邊中，找恰好比BC大的作為尤拉路徑的第三條邊，最終，某個點的入邊權重就是當前點所有邊的最大值，這條尤拉路徑拆分結束，一共n個點，可以按照上面的思路可以證明拆分出n條尤拉路徑，每條尤拉路徑的邊互不重疊，2m條邊種每條邊恰好是某個點發起的尤拉路徑，這個證明並不困難，所以必然存在一條有向尤拉路徑，長度至少是[2m/n]，權重遞增。
各國數學 物理 化學奧林匹克競賽的意義是什麼？
edulerp 作為乙個曾近參加過化競的同學，我談一些感想。我對晶體，結構之類的問題比較感興趣，開始看的是一本類似科普讀物的 結構與物性 後來讀過 無機化學 多個版本 高無機上的晶體圖會畫的不少還自學了 結晶化學導論 之類的。有機在我的哥們影響下也還行，福山組的題目c類的也差不多會，我記得當時好像省...
中學階段解出一道很難的數學題和在數學研究領域做出重大突破的區別在哪？
一袋貓糧 區別就在於你做的這道數學題，無論他多麼難，你都知道他一定是有答案的，只是這個答案你還沒有解出來而已。但是要在研究領域做出突破，如同獨自在漆黑的夜裡走迷宮，你不知道前方有什麼，你不知道你手裡這道題有沒有答案，你有可能投入了幾年幾十年才發現自己一開始走的就是死路。這就是最大的區別。 墨知 前者...
解答一道關於賣鞋的數學題，群裡有人問，結果100個人有100個答案？
dovisutu 令王老闆進鞋錢財產p 0 指零點 那麼，進鞋後，p 30.顧客買鞋，由後文知是假的，不計入收入。找朋友借50，此時p 20.要給顧客找錢，所以此時p 10.然而錢是假的又要賠給鄰居，此時p 60.故，虧了60元。 方法工廠 王師傅用成本30元的鞋子 找給顧客的30元等價交換了實際價...