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

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.

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

What happens to the cost of the nodes when the graph is converted to its corresponding Line Graph?

algorithm

graph

nodes

graph-theory

edges