培玉 · 一试
一试训练题
F3填空题组合计数综合
如图，在某海岸的附近有三个岛屿，计划建立三座独立大桥，将这四个地方连起来，每座桥只连接两个地方，且不出现立体交叉形式，则不同的连接方式有种。
作答
分数写 a/b，根号写 √ 或 sqrt，π 写 pi 也可以。
标准答案：
解析
提示
把地方看成顶点、桥看成边，先利用桥数和连通性确定图的类型。
思路
计出全部标号树后，再按图中的真实位置排除交叉；桥在端点相接属于连通，不应误删为交叉。
解答
四点用三条边连通，必为树。树要么是一点连向另外三点的星形，共4种；要么是一条经过四点的链，共种（正反方向同一条链）。图中只有与交叉，同时含二者时，第三条边必须连接这两个分离的边，有4种。这四种均为链且不合法，故所求。
复核
六条可能连接边中任选三条共有20组；其中4组是三点成环而另一点孤立，余下16组才是树。在凸四边形位置上，真正交叉只能是两条对角线同时出现，它们再配四条边之一即得4组坏树。两次扣除针对不同类型，与星形加路径的分类相符。
方法总结
平面连接题应先区分图论条件和几何条件：连通且边数少迫使成为树，不能交叉再由具体点位判定。若允许弯桥或跨越，模型会改变；本图按平面直接连接且不交叉的解释计数。
为什么评为 F3（会透露解法方向）
需识别三桥连通四点的结构并排除全部交叉链
已记下，谢谢！