具有不同权重的公共边的图的联合

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的更高成本路径将是城市大道。

希望能够对此问题有所了解。