图 - 尧

定义

图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为:G(VE)，其中，G 表示一个图，V 是图G中顶点的集合，E是图G中边的集合。

无向图

　无向边:若顶点到之间的边没有方向，则称这条边为无向边 (Edge)，用无序偶对 (viv) 来表示。如果图中任意两个顶点之间的边都是无向边，则称该图为无向图(Undirected graphs)。图7-2-2就是一个无向图，由于是无方向的，连接顶点A与D的边，可以表示成无序对 (A,D)，也可以写成(D,A)。

有向图

　有向边:若从顶点到v的边有方向，则称这条边为有向边，也称为弧(Arc)。用有序偶来表示，称为弧尾(Tail)，称为弧头(Head)。如果图中任意两个顶点之间的边都是有向边，则称该图为有向图 (Directed graphs)。图 7-2-3就是一个有向图。连接顶点A到D的有向边就是弧，A 是尾，D 是弧头，<A，D>表示弧注意不能写成<D，A>。

总结

　图按照有无方向分为无向图和有向图。无向图由顶点和边构成，有向图由顶点和弧构成。弧有弧尾和弧头之分。
　图按照边或弧的多少分稀疏图和稠密图。如果任意两个顶点之间都存在边叫完全图，有向的叫有向完全图。若无重复的边或顶点到自身的边则叫简单图。
　图中顶点之间有邻接点、依附的概念。无向图顶点的边数叫做度，有向图顶点分为入度和出度。
　图上的边或弧上带权则称为网。
　图中顶点间存在路径，两顶点存在路径则说明是连通的，如果路径最终回到起始点则称为环，当中不重复叫简单路径。若任意两顶点都是连通的，则图就是连通图有向则称强连通图。图中有子图，若子图极大连通则就是连通分量，有向的则称强连通分量。
　无向图中连通且 n 个顶点 n-1 条边叫生成树。有向图中一顶点入度为0其余顶点入度为1的叫有向树。一个有向图由若干棵有向树构成生成森林