高中数论
发布网友
发布时间：2023-07-20 14:02
共3个回答
热心网友
时间：2023-11-17 17:44
先证明一条引理：如果平面上已有n个点构成了连通图，新增一点P，则这n+1个点构成连通图的方法有 2^n－1种。这是因为，P点与前n个点中每一点都有连线与不连线两种选择，按乘法原理，有2^n种选择，只有P与前n个点都不连线这种情况使整个图不连通，所以连通方法为2^n－1种。
一．现在，假设平面上只有A，B，C三个点，则构成连通图的方法有4种：一种是构成三角形，另三种分别是构成缺一条边的三角形。
二．增加一点D，要构成连通图需要分三种情况讨论：（1）ABC连通，有4（2^3-1）=28种；（2）A，B，C中恰有两点连线，有3*(2^2-1)=9种；（3）A，B，C互不连线，有1种，即D与A，B，C都要连线。所以，4点连通的方法数为28+9+1＝38种。
三．再增加一点E，分五种情况讨论：（1）ABCD连通，有38(2^4-1)=570种；（2）A，B，C，D中恰有3点连通，有4*4*(2^3-1)=112种；（3）A，B，C，D四点不连通，但构成两条线段，有3*3*3=27种；（4）A，B，C，D中恰有一条线段，有6*3=18种；（5）A，B，C，D互不连线，有1种。所以，5点连通的方法数为570+112+27+18+1＝728种。
四．再增加一点F，分六种情况讨论：（1）ABCDE连通，有728(2^5-1)=22568种；（2）ABCDE中恰有四点连通，有5*38*(2^4-1)=2850种；（3）ABCDE中恰有三点连通，剩下两点也连线，有10*4*(2^3-1)(2^2-1)=840种；（4）ABCDE中恰有三点连通，且剩下两点不连线，有10*4*(2^3-1)＝280种；（5）ABCDE五点的分布是两条线段加一个孤立点，有5*3*(2^2-1)(2^2-1)=135种；（6）ABCDE中恰有一条线段，有10*3=30种；（7）ABCDE中每两点都不连线，有1种。所以，6点构成连通图的方法数为：22568+2850+840+280+135+30+1＝26704.
这就是答案。
热心网友
时间：2023-11-17 17:45
答案是不是算C(15,1)+..C(15,10)再减掉一些东西？ C(15,1)代表从15条线中去掉一条线的组合数
热心网友
时间：2023-11-17 17:45
