图的定义
通俗来说一堆顶点被一堆线连在一起，这一坨顶点与线的集合
目录
就是图。
图的严格定义如下：
图G由顶点集 和边集 E组成，记为 G=(V,E)，其中 V(G)表示图 G中顶点的有限非空集;E(G)表示图 G中顶点之间的关系(边)集合。若V={v1,v2...，vn}，则用表示图G中顶点的个数，E={(u,v)|u
V,v
V}，用
表示图G中边的条数。
术语
有向图与无向图
有向图：
若E是有向边(也称弧)的有限集合，则图G为有向图。弧是顶点的有序对，记为<v,w>其中v,w是顶点，v称为弧尾，w称为弧头，<v,w>称为从v到w的弧，也称v邻接到w。
E1={<2,1>}
无向图：
若E是无向边(简称边)的有限集合，则图G为无向图。边是顶点的无序对，记为（v,w）或(w,v)。可以说w和v互为邻接点。边(v,w)依附于w和v，或称边(v,w)和v,w 相关联。
E2={(2,1)}
说人话就是无向图的边没有箭头，有向图的边有箭头。
简单图与多重图
如果一个图 G满足以下两个条件：① 任意两顶点之间最多只有一条边；② 没有任何顶点通过边与自身相连，那么这个图称为简单图。
如果一个图 G允许两个顶点之间存在多条边，同时允许顶点通过一条边与自身相连，则称为多重图。
度、入度与出度
对于无向图，顶点的度指的是依附于顶点的边的条数，记为TD(v)。
对于有向图，顶点的入度指的是以该顶点为终点的有向边的数目（被箭头指向），记为ID(v)；出度指的是以该顶点为起点的有向边的数目，记为OD(v)；顶点的度为入度与出度之和。
无向图中顶点的度为顶点数的两倍（一个边连着两个顶点），有向图中所有顶点入度之和=出度之和=边数（一个弧有一个头和一个尾）。
路径与回路
顶点v1到v2的路径指的是能够从v1出发到达v2不中断的途径中所有的顶点与边。第一个顶点与最后一个顶点相同的路径称为回路或者环。
顶点不重复出现的路径称为简单路径；除了最后一个顶点和第一个顶点以外，其余顶点不重复出现的回路称为简单回路。
若图的边数大于顶点数-1，则图一定有环。
路径长度与距离
路径包含的边的数目为路径长度，顶点之间最短路径称为距离。如果顶点v1到达不了顶点v2，记两者距离为无穷。
子图
如果G1的顶点是G2顶点的子集，G1的边也是G2的边的子集，称G1是G2的子图。如果G1顶点完全继承G2，但是G1的边不一定完全继承G2，称G1为G2的生成子图。
这种情况G1不是G2的子图，因为G1不满足图的定义。
连通、连通图与连通分量
无向图中：
如果v与w有路径存在，称v与w连通。
如果一个无向图所有顶点之间都连通，则称该图为连通图。
一个图里的极大连通子图称为连通分量。
极大连通子图的极大指的是是尽量包含多的顶点和边。对于下面这张图，虽然123也是连通的，但是比1234少一个顶点，所以123不是图连通分量，1234是图的连通分量。
当然按照定义，一个孤立的顶点也是一个连通分量。
强连通、强连通图与强连通分量
有向图中：
如果v与w有路径存在，w与v有路径存在，称v与w强连通。
如果一个有向图所有顶点之间都强连通，则称该图为强连通图。
一个图里的极大强连通子图称为强连通分量。
完全图
对于无向图，如果任意一个顶点都与其他所有的顶点相连，则这样的图称为完全图。完全图的边数等于n+(n-1)+...+1=。对于有向完全图，则要求每个顶点有来去两条边相连，所以数目是无向完全图的两倍。
生成树与生成森林
连通图的生成树是包含图中全部顶点的一个极小连通子图。包含图中全部顶点的极小连通子图，只有生成树满足这个极小条件，对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。在非连通图中，连通分量的生成树构成了非连通图的生成森林。
这里的极小连通子图的极小指的是包含尽可能少的边。
权、网与带权路径长度
在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。这种边上带有权值的图称为带权图，也称网。
例题
1、含n个顶点的非连通图最多有几条边？
答：包含n-1个顶点的完全图和一个孤立顶点。边数为(n-1)(n-2)/2。
2、含n个顶点的强连通图最少要有几条边？
答：一个环，边数为n。