一些初赛要用的图论知识
0x01 无向图与连通图
n个顶点的无向图有n-1个边(以及以上)被称为连通图,而刚好n-1就是一棵树了
0x02 简单图的定义
没有重边和自环的无向连通图被认为是简单图,知道简单图的顶点数可以计算可能的情况。(利用排列组合,也可以暴力手算)
0x03 让连通图变成一棵树
树是n-1,所以需要m-n+1
0x04 环 (ver) (ring)
当每个顶点的度数都是2,就构成环。
0x05 最小生成树
什么是最小生成树?
它可以用Prim和Kruskal得到
作为初赛,我们其实只要掌握就可以了