algorithm - 当图形转换为相应的折线图时，节点的成本会发生什么变化？

Question

我有一个图G。我想将图形转换为其对应的 Line Graph .图 G 具有与其节点相关的成本。我想知道当图形转换为折线图时节点的成本会发生什么变化。

Answer 1

给定一个图(与 () 括号中的每个顶点相关的成本:

1 (8) ------ 2 (7)
 |  \         |
 |   \        |
 |   3 (9)    |
 |   /        |
 |  /         |
4 (6) ------ 5 (10)

您可以通过为对偶图中的边提供与顶点关联的成本来将成本关联到对偶图:

          (8)
  [1,2] ------- [1,3]
    | \         /   \
    |  \ (8)   /(8)  \ (9)
    |   \     /       \
(7) |    [1,4] ----- [3,4]
    |         \  (6)  /
    |      (6) \     / (6)
    |           \   /
  [2,5] ------- [4,5]
          (10)

因此 [1,4] 到 [3,4] 的连接通过顶点 4，其相关成本为 6 所以对偶中的边表示它的成本为 6。