计算树中所有奇数路径

Question

我的任务是，给定一个非循环非直接图，计算由奇数条边连接的节点对。

我的问题是为什么我应该从那些具有奇数度数的顶点开始搜索图？或者说，没关系吗？

Answer 1

非循环连通图是一棵树。如果不相连，那么它就是一片森林，是树木的集合。

我假设它已连接，但如果没有，请将其应用于每棵树。

选择任意节点。
从节点开始运行 BFS，计算距起始节点偶数和奇数距离的节点数，并将起始节点包含在距其偶数距离的节点计数中。
返回（奇数距离节点的数量）*（偶数距离节点的数量）

---

那么，为什么这会起作用？

假设 X 是我们在第一个项目符号中选择的节点，Y 和 Z 是任意两个其他节点。由于我们的图是一棵树，因此 X 和 Y 之间、X 和 Z 之间以及 Y 和 Z 之间只有一条路径。

假设 X-Y 路径为 X, p1, p2, ..., pk, Y。 假设 X-Z 路径为 X, q1, q2, ..., qt, Z。

这些路径之间可能没有重叠，但它们也可能重叠。假设前 r 个节点重叠，因此 pi == qi 对于 1

<= i <= r.

那么，Y & Z 之间的路径为：pk, p(k-1), p(k-2), ..., pr == qr, q(r+1), q(r+2), ...，qt。

其奇偶校验为偶数 IFF qr 和 qt 之间的路径奇偶校验与 pr 和 pt 之间的路径奇偶校验相同。但是，由于 pr == qr，这些奇偶校验相同，IFF X-qt 和 X-pk 的奇偶校验相同。