1
我有許多節點,每個節點都有多個邊。 例如節點A有3條邊,B有2條,C有2條,D有1條。我正在尋找一種算法,以找到兩個節點之間沒有多條邊的可能無向圖。 對於這個簡單的例子的一種可能的解決辦法是:查找具有給定數量的節點和邊的圖的算法
A
/|\
/| \
B--C D
所以A與其他3個節點,因爲它有3個連接,B連接到A和C連接,d與A.連接 所有的邊緣所有節點必須滿足。 又如:
A(3),B(3),C(2),d(1),E(1)
溶液:
A-----D OR: A-----E
/\ /\
/ \ / \
C-----B-----E C-----B-----D
所以,有時也有多種解決方案但也有可能,比沒有解決方案,例如 A(2),B(2),C(1)
沒有辦法用這3個節點及其給定的邊數做一個圖。
現在,我正在尋找一種算法來找到這個問題的可能解決方案。有沒有這樣的已知問題? 我很樂意提供任何形式的幫助或提示。