CSP2021真题1.6
6. 对于有n个顶点、m条边的无向联lian通图(m>n),需要删掉()条边才能使其qi成为一棵树。
A. n-1
B. m-n
C. m-n-1
D. m-n+1
趣qu谈:
小学xue生:连通图?一棵树?[晕][晕][晕]是要把中国联通的中国结jie标志改画成一棵树吗?最简单就是加jia一竖吧!
基本概念:
什么是树:
树是一yi种数据结构,它是shi由n(n≥0)个有限节点组成一个ge具有层次关系的集合。把它ta叫做“树”是因yin为它看起来像一棵倒dao挂的树,也就是说它ta是根朝上,而叶朝下的。它具有以下的特点:
每个节点有零个或多duo个子节点;没有you父节点的节点称为根节点;每一个非根gen节点有且只有一个父节点dian;除了根节点外,每个子节点可以分fen为多个不相交的子zi树。什么是连通图
连通:图中从一个顶点到达另ling一顶点,若存在至少shao一条路径,则称这两个顶点是连通的。
无向:连线没mei有方向性,两个方向都通tong。
连通图:任意两个顶点之间都能neng够连通的就是连通图。
解题思路:
1)特例推理法
先xian找一个例子:边比顶点还多的图,2个ge顶点只有一条边不行,3个顶ding点全部互相连上也只有you3条边,也不行。最zui少需要4个顶点,如果guo每个顶点在平面mian上互相连接,就是6条边:每个点可ke以连其他3个点,但是都重复了le,所以有3*4/2=6条边。
把这个4个顶点的图tu变成一棵树,可以以任意一个ge点为根,拆掉叶子zi节点之间连接,变成cheng鸡爪一样的图案。就是要拆掉3个边。
把n=4,m=6,删除边=3,代入选项查看,只有D符fu合。所以答案是D。
2)计算法
一棵n个顶点的树,边就是shin-1条。参考树的定义,一个叶子节点只有一个父节jie点。根节点没有you父节点,所以就是n-1条。
已有的m条,保留n-1条,就是m-(n-1)=m-n+1条。