中国结怎么画简单又漂亮(中国结怎么画)

昕阳小编 141 0

CSP2021真题1.6

6. 对于有n个顶点、m条边的无向联通图(m>n),需要删掉()条边才能使其成为一棵树。

A. n-1
B. m-n
C. m-n-1
D. m-n+1

趣谈:

小学生:连通图?一棵树?[晕][晕][晕]是要把中国联通的中国结标志改画成一棵树吗?最简单就是加一竖吧!

中国结怎么画简单又漂亮(中国结怎么画)-第1张图片-昕阳网

把联通图变成一棵“树”

基本概念:

什么是树:

树是一种数据结构,它是由n(n≥0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:

  1. 每个节点有零个或多个子节点;
  2. 没有父节点的节点称为根节点;
  3. 每一个非根节点有且只有一个父节点;
  4. 除了根节点外,每个子节点可以分为多个不相交的子树。
中国结怎么画简单又漂亮(中国结怎么画)-第2张图片-昕阳网

数据结构中一棵树的例子

什么是连通图

连通:图中从一个顶点到达另一顶点,若存在至少一条路径,则称这两个顶点是连通的。

无向:连线没有方向性,两个方向都通。

连通图:任意两个顶点之间都能够连通的就是连通图。

中国结怎么画简单又漂亮(中国结怎么画)-第3张图片-昕阳网

图1不是连通图,图2是连通图。


解题思路:

1)特例推理法

先找一个例子:边比顶点还多的图,2个顶点只有一条边不行,3个顶点全部互相连上也只有3条边,也不行。最少需要4个顶点,如果每个顶点在平面上互相连接,就是6条边:每个点可以连其他3个点,但是都重复了,所以有3*4/2=6条边。

把这个4个顶点的图变成一棵树,可以以任意一个点为根,拆掉叶子节点之间连接,变成鸡爪一样的图案。就是要拆掉3个边。

把n=4,m=6,删除边=3,代入选项查看,只有D符合。所以答案是D。

中国结怎么画简单又漂亮(中国结怎么画)-第4张图片-昕阳网

连通图变鸡爪树

2)计算法

一棵n个顶点的树,边就是n-1条。参考树的定义,一个叶子节点只有一个父节点。根节点没有父节点,所以就是n-1条。

已有的m条,保留n-1条,就是m-(n-1)=m-n+1条。

标签: 倒挂

抱歉,评论功能暂时关闭!