algorithm - 图 K11,12 中有多少条长度为 2 的路径？

Question

K11,12 中有多少长度为 2 的路径？

以及如何找出 Kx,y 中有多少长度为 2 的路径？（一般情况）

谢谢你。

标签： algorithmgraphpathgraph-theorygraph-algorithm

Answer 1

_,是一个完全二分图，即它的 + 节点可以分为两个不同的组，分别由 和 节点组成，并且它的边都是连接两个不属于同一组成员的节点的边。

该图中有边。大小为 2 的路径要么在第一组开始和结束，要么在第二组开始和结束。在计算有向路径时，我们必须除以二来表示路径的方向不相关。所以这样的路径的数量是：

        (-1)/2 + (-1)/2

...这是：

        (+y−2)/2

对于_11,12，这给了我们 11⋅12(11+12−2)/2 个这样的路径，即 1386。