求交叉数:用Python海龟绘制二部图

Question

首先，我必须说我来自数学背景，而且我对Python编程的知识很少。我的工作是绘制完全二部图与的最低过境数。例如：K(4，4)，是下图中给出的具有8个顶点的完全二部图(分组为4-4)。

​

图有交叉数 = 4，我想用高顶点数(例如K(9,9)，有18个顶点的完全二部图)画这样的图。我寻找了不同的编码和理论。我发现Python有可以在这件事上帮助我的海龟包。我计划使用一种算法:我将从一个顶点开始海龟的旅程，然后在另一个顶点上停下来，在旅程之间我将收集它所走过的路径的坐标，然后在不与任何其他边缘重合的情况下重复这个过程，如果这发生了，那么就选择有最少交叉口的路径。

目前，我正在研究海龟及其命令。任何关于如何解决这个问题的想法，任何关于使用更合适的软件(付费或开源)的建议，对算法的帮助，对书籍或研究论文的建议都是非常感谢的。

我使用yED (免费提供)制作了这个图表，但是对于更高数量的顶点，手工工作是非常辛苦的。

提前感谢！

Answer 1

对不起，我没有完全回答这个问题，重新绘制海龟图形。既然你是数学家，难道你不使用LaTeX吗？如果是这样的话，下面是一个让您开始的小程序：

from string import Template

DOC = Template("""
\\documentclass{article}
\\usepackage{tikz}
\\begin{document}
\\begin{tikzpicture}
$drawing\\end{tikzpicture}
\\end{document}
""")

class GraphDrawing(object):

  def __init__(self, node_count: int):
    self.node_count = node_count;

  def Coord(self, i: int):
    c = self.node_count
    offset = 1 - c if c % 2 == 0 else - c
    return offset + 2 * i

  def Draw(self):
    r = ''
    for i in range(self.node_count):
      for j in range(self.node_count):
        r += f'\\draw ({self.Coord(i)},0) -- (0,{self.Coord(j)});\n'

    for i in range(self.node_count):
      r += f'\\filldraw ({self.Coord(i)},0) circle (3pt);\n'
      r += f'\\filldraw (0,{self.Coord(i)}) circle (3pt);\n'

    print(DOC.substitute({'drawing' : r}))

GraphDrawing(8).Draw()

通过pdflatex运行，这会产生：

​

​

如果你真的需要海龟图形，它应该是非常简单的取代这个程序中的字符串构造与海龟移动。

Answer 2

正如图表所说，人们认为您提供的图表总是最优的。将一组放在垂直轴上，另一组放在水平方向上，向上/下均匀地分开，左/右。然后用直线连接。你不太可能找到比这更好的。

您可以看到https://mathworld.wolfram.com/ZarankiewiczsConjecture.html的更多信息，包括已确认的各种小型n病例。