graph - 異なる重みを持つ共通のエッジを持つグラフの結合

Question

2つの無向加重ギャップ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 の間に 2 つのエッジがある場合

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

ここで、c はパス コスト関数です。

これら 2 つのグラフの結合が可能かどうかを尋ねているようです。答えはイエスです。交差点と同じように、いつでもグラフでユニオン操作を実行できます（集合論と同じように、グラフの最初の原則の定義を思い出してください。それらはすべて、頂点とエッジのセットを含むタプルです）。

「エッジ」DC が 4 と 7 の重みを同時に持っているということではなく、DC の間を走る 2 つの異なるエッジであり、一方の重みが 4 で、もう一方の重みが 7 であるということです。これらのグラフは都市の地図を表すものであり、重み付けされたパス 4 は「高速」の分割された高速道路であり、コストが高いパス 7 は都市の大通りになります。

問題に光を当てることを願っています。