图论基础知识

（1）有向图、无向图、加权图；

（2）连通图、非连通图：

（3）图的生成树和最小生成树：

 （4）bipartite graph-偶向图：

关于二分图的匹配：

（1）定义：一个「匹配」（matching）是一个边的集合，其中任意两条边都没有公共顶点。例如，下图 3、图 4 中红色的边就是图 2 的匹配。