由四个没有区别的点构成的简单无向连通图的个数

2021年8月20日 | 分类: 【编程】

【题目】

由四个没有区别的点构成的简单无向连通图的个数是()。

A.6
B.7
C.8
D.9

【解析】

1. 四个没有区别的点,意味着以下的图形为相同形状。

用 \(d=[1,2,2,1]\) 表示对应点的度,则以上的图的d数组都是一样的。

2. 而以下的图形则是不同的另外一个形状,其 \(d=[1,3,1,1]\) 。

题目要求,实际就是找出不同的d数组的个数。

3. 根据边数来分类判断:

小于3条边,不构成连通,排除掉。0 种。
3条边:\(d=[1,2,2,1]\) 和 \(d=[1,3,1,1]\) ;2种。
4条边:\(d=[2,2,2,2]\) 和 \(d=[1,3,2,2]\) ;2种。
5条边:\(d=[2,2,3,3]\) ;1种。
6条边:\(d=[3,3,3,3]\) ;1种。

所以一共有6种不同的图形,答案是A。

总结:简单图指没有平行边和自环,不要被它误导。
总结:从6条边往下减边,会更加容易分析。

参考:https://www.sohu.com/a/274745863_100066352