✏️ 纠错
第 183 题 / 共 201 题
7. 下列关于树和图的说法,错误的是()。
你真棒!
📝 题目解析
答案:D
知识点:树与图的转换
解析:有向图的生成树仅保证弱连通(任意两节点存在路径,不要求方向),但不一定强连通(任意两节点双向可达,D错误);A、B、C均正确。
A. 树是无向连通、无环的。若节点指向父节点,将无向边转为有向边后,无向视角下仍连通,故为有向弱连通图(弱连通指“有向边无向化后连通”),正确。
B. 树的父子关系是“单向、无环”的,节点指向子节点的有向边不会形成环,故为有向无环图(DAG),正确。
C. 连通无向图的生成树是“包含所有节点、边数最少的连通子图”,根据定义,每个连通无向图必然存在生成树(可通过Prim、Kruskal等算法构造),正确。
D. 反例:有向图含两个顶点A和B,仅一条有向边A→B。该图本身是生成树(树状结构,覆盖所有顶点),但从B到A无路径,因此不是强连通(强连通要求任意两顶点互相可达),错误。
知识点:树与图的转换
解析:有向图的生成树仅保证弱连通(任意两节点存在路径,不要求方向),但不一定强连通(任意两节点双向可达,D错误);A、B、C均正确。
A. 树是无向连通、无环的。若节点指向父节点,将无向边转为有向边后,无向视角下仍连通,故为有向弱连通图(弱连通指“有向边无向化后连通”),正确。
B. 树的父子关系是“单向、无环”的,节点指向子节点的有向边不会形成环,故为有向无环图(DAG),正确。
C. 连通无向图的生成树是“包含所有节点、边数最少的连通子图”,根据定义,每个连通无向图必然存在生成树(可通过Prim、Kruskal等算法构造),正确。
D. 反例:有向图含两个顶点A和B,仅一条有向边A→B。该图本身是生成树(树状结构,覆盖所有顶点),但从B到A无路径,因此不是强连通(强连通要求任意两顶点互相可达),错误。