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

Question

我有两个无向加权间隙 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 将是城市大道。

希望能对这个问题有所了解。