关于树的节点的度数
  • 板块学术版
  • 楼主lzm0107
  • 当前回复8
  • 已保存回复8
  • 发布时间2024/6/1 16:25
  • 上次更新2024/6/1 18:46:39
查看原帖
关于树的节点的度数
555994
lzm0107楼主2024/6/1 16:25

参加市赛,看到一道题:

一棵 nn 个节点的树,树上所有节点的度数总和是()。

这篇博客说,树中一个结点的孩子个数称为该结点的度。但根据 OI-Wiki 上的这个页面,无根树属于无向图,而有根树则是无根树+指定根结点。

我认为,既然无根树是无向图,那么根据握手定理,结点的度数和就应当为 2n−22n-2。而有根树指定的根不影响图的有向/无向与度数,所以题目答案应为 2n−22n-2。

求本题答案和依据。

2024/6/1 16:25
加载中...