求幾何平面圖（無向圖）的所有最小閉合環?

知乎使用者2016-11-22 11:43:59

對每一條邊的兩個頂點， 去除此邊之後， 找到起點到終點的最短路徑（用廣度遍歷就可以了啊）。

mathfinder2016-11-22 13:01:48

瀉藥：

恕我冒昧，可能是我的化學知識儲備不夠，不知道題主的問題是怎麼轉化的，可以把原題的連結發一下嗎？

假設題主的轉化沒錯的話，題主想知道的是，求特定一條邊所在的最小的環（首先我不知道問題中化學鍵有沒有距離的概念，既然給了點的幾何位置，我就假設最後構的圖邊是有權的吧，化學不好就按我的理解來吧）。構好圖以後，就可以像第一個回答那樣，對每一條邊，刪掉它，求這條邊兩頂點的最短路就可以了，由於邊有權，就不能廣搜啊，直接上個最短路演算法的模板就好了。

ps。最好發一下原題連結，讓我這些，不懂化學的人能看懂。

nullsirzh2016-11-27 01:28:29

@Chan ijasmine

已經給了一種簡單粗暴的演算法了啊。

還是不太明白你的問題為啥需要找最小環。

匿名使用者2018-12-01 19:20:00

圖論中這個叫 minimum cycle basis（mcb）， Google scholar搜這個關鍵詞就行，有不少相關演算法，比如horton，de pina等。由於mcb不是唯一的（比如對於立方烷，任意5個面環都是mcb），不太推薦這種環了。可以考慮union of all mcb（umcb）（對於立方烷，umcb為6個面環，又叫relevant cycle），umcb是唯一的。可以先計算horton candidate cycle，然後在高斯消除就行了。horton candidate cycle 也可以直接高斯消除得到mcb，或著用de pina的方法也可以得到mcb。

瘋狂紳士2019-07-16 10:39:50

這個幾年前的問題，我自己回答一下吧。

裡面是雙鍵要分辨環，以方便內側的一根鍵往裡畫。

求環的思路如下

這是一個最小環最小集的問題 即 SSSR

1、去掉葉子節點即所有的不在環裡的點

2、去掉所有不在環裡的邊

3、廣度遍歷，求最小生成樹

4、把剩餘的邊補回去，每當補回一條邊就是能構成一個迴路

效果舉例

http：//

data。huaxuejia。cn/showc

as_pic。php？casid=153-18-4

http：//

data。huaxuejia。cn/showc

as_pic。php？casid=17000-55-4

3D扯蛋效果

扯蛋