无向树是否存在？图论中树的定义与无向图环判定疑问

你的困惑本质是混淆了不同语境下的树定义，以及无向图中环的严格判定标准，具体拆解如下：

• 「树是DAG的特例、每个顶点仅有一个前驱」是有向根树的专属定义：这类树是有向图的一种，通常指定一个根节点，所有边从父节点指向子节点（或反向），除根节点入度为0外其余节点入度均为1，天然满足有向无环的要求，因此属于DAG的子集。
• 无向树是无向图语境下的独立定义：只要无向连通图满足「连通、边数为$|V|-1$、无环」三个性质中的任意两个，就可以判定为无向树，第三个性质可由前两个推导得出，不需要给边赋予方向。

你之前认为「无向图单条边往返走就能回到起点，因此构成环」是对环定义的误解，图论中无向环的判定必须同时满足三个条件：

• 路径长度至少为3
• 除起点和终点为同一顶点外，路径上其余所有顶点不重复
• 路径中不会重复使用同一条边

两个节点间的单条边如果走往返路径u-v-u，本质是重复使用了同一条边(u,v)，完全不符合无向环的判定规则，因此不会让无向图成为有环图。

补充：有向图的环判定同样要求路径不重复使用边、除首尾顶点外其余顶点不重复，只是要求边的遍历方向和有向边的指向一致，不存在「顺着边往返就算环」的规则。

所有有向根树去掉边的方向后得到的无向基图，一定符合无向树的定义；但反过来，给无向树的边随意指定方向，不一定能得到属于DAG的有向根树——只有当边的方向满足「单根入度为0、其余节点入度为1、无反向指向祖先的边」时，才是符合DAG要求的有向树。

内容的提问来源于stack exchange，提问作者Rohit Pandey