n个点，任意三点不共线，最多连接多少条线段且不存在以这些点为顶点的三角形
(2017-06-09 09:38:37)
- 图论，分组
-
空间有100个点,任4点不共面,用若干条线段连结这些点,如果不存在三角形,最多可连结_____条线段? 把100个点分为A、B两组,每组50个点
A组每个点和B组的每个点连成线段,共可以连成50*50=2500条.(同一组的两个点不连) 则这2500条任意三条没有连成线段.
又因为若再连一条线段,这条线段的两个端点在同一组,所以必形成一个三角形.
所以空间有100个点，任4点不共面，用若干条线段连结这些点，如果不存在三角形，最多可连结2500条线段
-
-
空间有2n个点，用n*n+1条线段连接这些点，证明至少出现一个三角形.
-
鸽笼原理。将2n个点随意分为两组,每组n个点,一组染成红色,一组染成蓝色.一组每个点分别向另一组各个点引一条线段,共有n*n条线段,剩下一条线段只能在某同色组之间相连,这样连接这条线段的两点与另外一组的任意一点构成一三角形.前提是这2n点任三点不共线。
喜欢
0
赠金笔
加载中，请稍候......
喜欢
加载中…