我想知道有一些算法可以将图形变成平面图吗？我在谷歌搜索我没有找到可以帮助我的东西
问问题
3774 次
2 回答
3
有一个适用于每个平面图的欧拉定理。
定义：平面图是可以在平面上绘制的图，这样边不会相互交叉。任何平面图都将平面划分为许多不相交的区域，称为图的面。
欧拉定理：V-E+F=2 其中：
- – V 是顶点数，
- – E 是边数，
- - F 是面数
但是，我无法在 java 中提供解决方案，因为它不清楚您想要实现它的方式。例如，如果要将图转换为平面图；在视觉上，您可能需要重新排列画布和元素，这将是一种复杂的实现。一般来说，明智地考虑算法，首先在伪代码中创建解决方案。
例如，由于我们有适用于每个平面图的欧拉定理，因此您需要找到一种方法将该定理应用于现有的非平面图，然后对其进行测试。
步骤：（可能其中一些需要坐标）
- 确定什么是顶点
- 确定什么是边缘
- 确定什么是面
- 找到一种计算顶点的方法
- 找到一种计算边缘的方法
- 找到一种计算人脸的方法
- 重新排列画布中的所有内容
- 测试定理，如果它适用，那么你的图是平面的，否则，重新排列。
- 请注意，通过使用坐标，您可以从一开始就确定图形是否可以绘制为平面，但是，当您绘制它时，您不应允许任何线边相交。
于 2014-01-02T20:57:05.053 回答
3
评论太长了。所以请原谅我提供一个答案。
你的问题我不清楚。图形是否是平面的，是图形本身的函数，而不是它的绘制方式。“在图论中，平面图是可以嵌入到平面中的图，也就是说，它可以在平面上以这样一种方式绘制，即它的边只在端点处相交。” 来自http://en.wikipedia.org/wiki/Planar_graph）。
您是否需要计算/检查图形是否是平面的？
您需要以平面形式绘制它吗？
在您提供的示例中，为什么第二张图比第一张图更正确？仅仅是因为它们没有相交的边吗？
假设您需要对其他图表执行此操作，使用什么规则来确定某些表示是否比其他表示更好，您的图表如何推广到其他图表？
你为什么做这个？重点是什么？如果是作业，问题陈述究竟是什么？如果它是真实的，也许对你真正想要做的事情的解释会有所帮助。
于 2014-01-03T02:57:57.453 回答