问题标签 [planar-graph]

我现在正在练习我的递归技巧，遇到了 6 色定理：

每个平面图都可以用 6 种颜色着色。

该定理源于观察到每个平面图G都有一个顶点 v，其度数小于或等于 5。

这个想法很简单：选择度数小于或等于 5 的 v。对 Gv 进行归纳着色。对 v使用第 6^种颜色。

我试图在伪代码中递归地实现该定理：

这个伪代码是否正确，我可以将每个归纳证明转换为递归算法吗？

我想保存图表的外部节点。为此，我有以下代码（我正在展示我认为与问题相关的部分，我确实有所有#include 标头等......）：

到目前为止，代码在小图（节点数 < 8）上正常工作，但它在 n = 9 时开始失败，我不明白为什么。例如，对于邻接表

它返回

这是没有意义的。正确的外表面应为 0 7 3 1 5 2 4。

对于发现问题的任何帮助，我将不胜感激。谢谢！

我有一个我自己创建的平面图。我想找到这张图的面孔，但我找不到这样做的有效算法。到目前为止，我所做的是使用一种算法来查找图中的所有循环，但这给了我所有可能的循环，我已经尝试过但没有找到一种方法来只对面进行排序。我的一个想法是使用 Path2Dscontains方法来查看另一个形状是否重叠，但由于面共享节点，这不起作用。下图展示了我想要的内容，之后的代码展示了我的可复制示例。

运行上述代码后的结果是：

我解决此问题的最佳尝试之一是使用以下代码。坐标来自顶部的图片。

此处列出了使用的多边形方法。

这段代码给了我下面的结果，不需要第 2-4 个。

以立方体为例，有8个节点，12条边，每个节点连接3个节点。

使用networkx，我必须手动输入所有边缘。例如，下面的代码是构建一个包含二十面体所有边的图（12 个节点，30 个边，每个节点 5 个相邻节点）。

我的问题是如何在不手动编写的情况下获得所有可能的边缘。每个节点的名称可以随机初始化。

据我所知， igraph中的 Erdős-Rényi 模型无法约束相邻节点。

我正在处理以下任务：

我有 6 个鱼眼相机，想生成 360 度拼接图像。

在使用 findChessboardCorners、calibrateCamera 执行校准程序后，我获得了内在和外在矩阵。从6张带鱼眼效果的图像开始，通过fisheye.initUndistortRectifyMap函数，得到了6张平面图像。下面报告了上面的两个平面图像。

现在我应该进行拼接以获得 360 度图像。

我尝试使用 cv2.createStitcher 函数来做到这一点，但这并不总是有效，我也想访问单应矩阵来确定系统的静态矩阵。

所以我尝试计算单应矩阵，通过 SIFT 算法识别两幅图像之间的共同关键点，并保持最佳匹配的关键点。

然后我使用 warpPerspective 函数缝合了这两个图像。

我相信直到计算关键点的过程都是正确的，但我不明白为什么最终结果不好。

实际上，在尝试拼接第二张图像时，第二张图像在透视上完全变形/改变，失去了正确的图像。

这里有代码：

我正在尝试从 pd 框架中绘制一些数据的平面图：

这将返回(True, <networkx.algorithms.planarity.PlanarEmbedding at 0x11fa6d1f0>)，所以我认为它是合法的平面。

然后我尝试绘制它：

此时draw_planar()将永远不会完成（没有例外或任何事情）。

只是draw()工作正常。

有什么我想念的吗？

我正在寻找一种在 C# 中生成随机平面图的方法。我研究了一些算法，如 Voronoi 图、Delaunay 三角剖分和凸包算法。它们不再有用，我设法生成了一个图表，但我面临一些我还没有解决的边缘情况。请记住，我有 2 个主要约束：最小/最大边长和最小/最大角度（在任何 2 条边之间），目标顶点/边数有错误是可以的。

我认为有两种方法可以生成该图： A. 有所有可能的平面图的来源，我需要一个小的，所以这对我有用，但我不知道如何在没有交叉点的计划上绘制它。B. 从几何角度生成它，这是我最了解的。

我发现一些论文旨在非常快速地生成大图，所以对我来说很复杂。我可以接受经过测试的慢速算法/库/代码。