图论

1. 设$G$为一个$n(n\ge 5)$阶图，且$G$的任意$n-2$阶子图的边数为一定值$3^{k}(k\in \mathbb{N_{+}})$。求$n$的所有可能取值。

图论

二分图

定义

二分图又称双分图、二部图、偶图，指顶点可以分成两个不相交的集$U$和$V$，$U$和$V$皆为独立集（即同一个集内的顶点没有共同边）的图。（摘自维基百科）

什么叫传递闭包

“传递闭包”这个名字听起来很吓人，其实它不难理解。

给定一个有向图$G$，那么“传递闭包”就是指“图上一点$i$能否到达另一点$j$”。