一个平面上的N个点...

平面上给出n个点，一笔将这些点连接起来(连接线可以交叉，但每个点只能经过一次)，那么一共有这样不同的回路几条？

(比如N==3的话只有一条...)

小弟不才，这个问题困扰了我好久......唉
望达人指点一二

12 个解决方案

#1

深度优先~

#2

可以给出一个具体的公式吗？... 编程只有总数啊

#3

数学问题好像。。
(n-1)!/2难道是。

排列一共有n!个，但是围成一个圈就有n个是重复的，再加上没有首尾，所以再除以2

#4

阶乘级别的啊？～

我再想想哈～

#5

如果存在3个点以上在同一条直线上的情况,答案会有不同吧!

#6

LZ对于“不同回路”的定义到底是什么？从描述上来看，似乎是图的同构问题？即：一个有N个点，N条边的连通图，其有多少种不同的同构。

具体的么。。。记不清了@@，图论部分的东西忘得差不多了0,0

#7

恩。。。差不多就是同构的意思～～

好像真的是N！级别的... 
不然哈密尔顿回路和旅行商问题就不是NP的了...

再想想...

#8

N个点的圆排列的总的数目为(n-1)!
在lz的这个题中（比如N==3的话只有一条），每个圆排列由顺时针转换成逆时针还是同一个回路,即每个回路对应有两个圆排列；

所以总的回路数目为：(n-1)!/2;

#9

啊，太难了。

题目都没看懂啊。

一笔将这些点连接起来，而后又有几个回路，什么意思啊？

#10

应该是(n-1)!/2吧~~

#11

全排列问题

#12

如果出现如5楼所说的情况怎么办呢？
有可能在从a点连向b点的途中路过c点的情况呢
这种连法就要排除吧
除非约定任意3点不共线？