图
定义
由顶点的有穷非空集合和顶点间的边的集合组成的
通常记为G(v,e)，G表示一个图，v是G中顶点集合，e是边的集合
即V(G)和E(G)分别成为G的点集和边集
必须有顶点，但可以没有边
无向图与有向图
有向图用有序对表示，视为集合\(V\)上的一个二元关系\(R\subseteq V\times V\)
无向图用无序对表示，视为集合\(V\)上的对称二元关系，即\((u,v)\in R\)必有\((v,u)\in R\)
简单图与多重图
简单图：
- 图中不能有顶点到自身的边
- 同一条便在途中不能出现两次及以上
不满足上述条件的成为多重图
完全图
具有最多边数的图
对于一个具有n个顶点的无向完全图，边数量的最大值为\(\frac{n(n-1)}{2}\)
对于一个具有n个顶点的有向完全图，边数量的最大值为\(n(n-1)\)
路径与路径长度
路径：从一个顶点开始，经过一系列的边到达另一个顶点形成的顶点序列
路径长度：路径上边的条数
回路（环）：起点与终点相同的路径
简单路径：如果路径中不出现相同顶点，则成为简单路径
简单回路：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路
度
对于无向图，顶点的度指的是与顶点相关联边的数目
入度：有向图中，箭头指向顶点v的边的数目
出度：有向图中，从该顶点出发的边的数目
与边的关系：
- 图中所有顶点度之和等于边数的两倍
- 对于有向图，所有顶点的出度与入度之和相等，弧数量也相等
子图
图G的子图H，满足\(V(H)\)是\(V(G)\)子集且\(E(H)\)是\(E(G)\)子集
连通图
连通图：在无向图中，如果顶点v到顶点w有路径，则称顶点v到顶点w是连通的。如果对于图中任意两个顶点都是连通的，则称此图为连通图
极大连通子图：在这个子图中任意两个顶点都是连通的，而且不能通过添加更多顶点或边来扩大这种连通性
连通分量：无向图中的极大连通子图称为连通分量
强连通图：在有向图中，对于每一对顶点v和w，从v到w和从w到v都有路径，则称该有向图是强连通图。
强连通分量：有向图中的极大强连通子图称为有向图的强连通分量
生成树
含有图中全部顶点的极小联通子树
包含所有顶点n，但只有足以构成一棵树的n-1条边
边权和网
权：在一个图中，每条边可以标注上一个代表某种含义的数值，该数值称为这个边的权值
网：边上带权值的图，也称为带权图
例
若无向图\(G=(v,e)\)中含有七个顶点，要保证图G在任何情况下连通，则需要边数最少是
即6个顶点的最多边数+1即为7个顶点最少边数
用公式\(\frac{n(n-1)}{2}\)