图形变换 - 将顶点转化为边，将边转化为顶点

Question

20

是否有一种算法或者转换方法，可以将图中的边变成顶点，将顶点变成边？我们能够通过这种方式得到新的图形或者解决类似于这个问题的任何东西吗？我不确定这是否有意义，但如果您能给我任何关于这个问题的提示，我会很高兴的。

- krajol

3

你想在哪里添加新的边？是在旧边在顶点处相遇的地方吗？http://en.wikipedia.org/wiki/Edge_graph - John Dvorak

2

在我看来，这种类型的任何转换都可能呈指数级时间复杂度，因为它可以用于将哈密顿回路问题归约到欧拉回路问题。 - Imre Kerr

@jan-dvorak 是的，Edge graph 就是我要找的，谢谢。现在我知道如何将有向图转换为其有向线图，但您是否知道是否有一种方法将其转换回原始图形？ - krajol

@krajol 请查看维基百科文章。您需要找到一种方法，用团（完全子图）覆盖线图，以便每个顶点都是两个团的一部分。 - John Dvorak

如果您只将inedges连接到outedges，则需要找到相应图形（完全二分）。这种特殊情况可能比无向情况更容易：线图中所有入边都属于一个完全二分子图，所有出边都属于另一个相关的完全二分。 - John Dvorak

@ImreKerr 这并不一定是这样的，对吧？因为图中顶点的数量将不等于等效线图/边图中的边数。想想一个带有1个中心顶点和3个相邻顶点（由3条边组成）的星形图。相应的边图只是一个三角形，有3个顶点。所以不能建立对应关系。 - Hirak Sarkar

4个回答

3

LineGraph是Wolfram语言中的内置函数:

它的功能如下:

- Vitaliy Kaurov

3

你有没有考虑过基于模式的图形转换？就像你会：

在图形转换文献中，这两个步骤被称为图形转换规则的左侧和右侧。

该领域有大量的科学文献可供参考，例如：http://www.springer.com/de/book/9783319211442

还有专门针对图形转换的开发解决方案，如Soley Studio。

希望这能帮到你。

- brgn

-1

我相信你可以很容易地使用以下Python库将边缘转换为顶点：http://networkx.lanl.gov/

您可以获取边缘列表、节点列表并交换两者以构建新图。您只需要一些（基本的）Python知识。

- Francesco Turci

4

- yehudahs

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Chidi · Accepted Answer

你所需要的是一条线图。你可以使用networkx的line_graph函数来创建一个给定图形的线图或对偶图。然而，请注意，该函数不会传播原始图形的数据，因此如果需要数据，您将不得不在这方面进行处理。