图

无向图

定义

1. 图是由一组顶点和一组能够将两个顶点相连的边组成。
2. 路径、环、度，连通
3. 如果从任意一个顶点都存在一条路径到达另一个任意顶点，我们成这幅图为连通图。一幅非连通图由若干连通的部分组成，它们都是其极大连通子图。
4. 树是一幅无环连通图。互不相连的树组合成的集合成为森林。连通图的生成树是它的一幅子图，它含有图中的所有顶点且是一棵树。图的生成树森林是它的所有连通子图的生成树的集合。

图的密度是指已经连接的顶点对占所有可能被连接的顶点对的比例。密度小的是稀疏图，密度大的是稠密图。

二分图是一种能够将所有节点分为两部分的图，其中图的每条边所连接的两个顶点都分别属于不同的部分。

有向图