图中交集的数量

Question

我正在用 sagemath 做一个项目，我有一个这样的列表 [(0, 2), (1, 3), (2, 1), (3, 0)]。它在下面创建了一个图表，并使用该图表计算出交叉点的数量为 5（以紫色标记）

如何在不绘制图表的情况下计算该值？还是用图表？

Answer 1

我觉得这个问题很有趣。你能不能像这样解决问题：将你的图形点视为图层。让我们根据您左侧的起始点将它们命名为零到三。

然后从顶部开始循环图层并检查它下面的所有图层。如果从下面开始的每条线的终点比您的线的终点高一层，则每条线都会穿过您的线。

代码应该是这样的。

lines = [(0,3),(1,2),(2,0),(3,1)] #translated your cordinates.
cross = 0
lines.sort()  # we want order lines so upper starting point is first
for i in range(len(lines)):  #using index here, easier this time.
    my_start = lines[i][0]
    my_end = lines[i][1]
    for line_below in lines[i:]: # loop through lines below
         if line_below[0] == my_start:
              continue # We don't count crossing if we have the same starting point.
         if line_below[1] < my_end: 
           cross += 1 #if end point is higher than my end poi, we'll corss

我会像这样想象你的起点/终点，而不是右侧的随机顺序：

 0                      0
     
      
 1                      1
          

 2                      2 


 3                      3

但实际上，无论您的图表中有多少起点或终点，这种方法都有效。如果线在起点或终点相遇，或者两条线相同（相同的起点和终点），则代码不计算交叉。

Answer 2

下面给出的代码中，L是第二个变量的List。

所以对于上面的问题L = [2,3,1,0]

def Ans(L):
  NL=[]
  count=0
  for i in range(0,len(L)):
    for j in range(0,len(L)):
      ifL[j]==i:
        NL.append([i,j])
  for i in range(0,len(L)):
    forjinrange(0,i+1):
      if(NL[i][1]<NL[j][1]):
       count=count+1
  returncount

图中交集的数量

Nuimberof intersection in a graph

python

graph

sage