具有不同權重的公共邊的圖的聯合

Question

我有兩個無向加權gaphs G1和G2，它們之間有2個公共頂點C和D.

是否有可能在G1中的邊緣CD具有權重4並且在G2相同的邊緣具有權重7？ 如果是，這些圖的聯合是什麼？

Answer 1

好讓我盡我所能來這裏記得我的圖論......

答案是肯定的，得到的圖形會像

  3 
    A---------B 
    | 4 | 
    5 | _______ | 8 
    |/  \| 
    D---------C 
    \ 7 /
    \ /
    6 \ /5 
     \/
     \/ 
     E 
     G1 U G2 

在哪裏頂點D和C在它們之間具有兩個邊緣

c(DC) = 4 and c(DC') = 7

其中c是路徑成本函數。

你似乎在問這兩個圖表上的聯合是否可能。答案是肯定的，你總是可以在圖上執行聯合操作，就像你可以交集一樣（它就像集合論，回想你第一個圖的原理定義，它們都是包含頂點和邊集的元組）。

它不是「邊緣」DC如何同時具有4和7的權重，它們是在DC之間運行的兩個不同的邊緣，一個權重爲4，另一個權重爲7。您將這些圖形想象爲代表城市地圖，4的加權路徑將是「更快的」分開的高速公路，而7的更高成本路徑將是城市大道。

希望能夠對此問題有所瞭解。