图论中,n个点连线的问题,要使图形不含三角形,最多连几条边

图论中,n个点连线的问题,要使图形不含三角形,最多连几条边
平面上有n个点,任意3个点都不共线(可以认为这n个点在一个圆上);对着n个点用线段进行连接,问:要使连成的图形中不含三角形,最多能够连 几个线段?
图论里面题目,给出通项式也行(估计难),用算法实现也行(时间复杂度不要太高)吗,
n=6时,最多可以画9条
阿Max 1年前 已收到2个回答 举报

wtornadow 幼苗

共回答了12个问题采纳率:91.7% 举报

m

1年前

2

被爱情遗忘的天使 幼苗

共回答了2个问题 举报

我没学过图论,我把它当几何题来做了下,感觉应该是正确的,如果错了,请批评指教!
设对着题设的n个点用线段进行连接时,要使连成的图形中不含三角形,最多能够连接的线段数为An!
显然,A1=0,A2=1,A3=2。
当n>=4时,n个点可以顺次连接成n边形,即n条线段。由于要求不含三角形,且考虑到要求最多的线段数,那么在这个n边形里就只可能含四边形和五边形,而且在这个n边形里最...

1年前

3
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 17 q. 0.131 s. - webmaster@yulucn.com