图

图的定义

图:由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E),
—-G表示一个图，V是图G中顶点的集合，E是图G中边的集合
| | 线性表 | 树 | 图 |
| ————- |:—————-:| —————–:|
| 数据元素 | 元素 | 结点 | 顶点 |
| 没有数据元素 | 空表 | 空树 | 不能没有顶点，有穷非空 |
| 数据元素间关系 | 相邻之间:线性关系| 相邻两层:层次关系 | 任意两个顶点之间都可能有关系顶点之间逻辑关系用边表示，边集可以是空的|
无向边：顶点Vi到Vj之间的边没有方向,用无序偶(Vi,Vj)表示
有向边/弧：顶点Vi到Vj之间的边有方向,用有序偶<Vi,Vj>表示,Vi称为弧尾，Vj称为弧头
简单图：在该类图结构中，不存在顶点到其自身的边(自己指向自己)且同一条边不重复出现
无向完全图:在该类图结构中，任意两个顶点之间都存在边，含n个顶点的无向完全图有n(n-1)/2条边
有向完全图:在该类图结构中，任意两个顶点之间都存在方向互为相反的两条弧，含n个顶点的有向完全图有n(n-1)条边
稀疏图：边或弧数小于nlogn(n是顶点的个数)
稠密图：边或弧数大于nlogn(n是顶点的个数)
权：图的边或弧带有的与它相关的数字
网：带权的图
子图：图G1(V1,E1),和G2(V2,E2),如果V2 \subseteq V1，E2 \subseteq E1 ,V2 属于 V1，E2 属于 E1则称G2为G1的子图
http://blog.csdn.net/sanqima/article/details/48576361
邻接点：无向图G=(V,E),如果边(V1,V2)属于E，则称顶点V1和V2互为邻接点，即V1和V2相邻接
——-边(V1,V2)依附于顶点V1和V2，或者说边(V1,V2)与顶点V1和V2相关联
顶点V的度：和顶点V相关联的边的数目，记为TD(V)
邻接：有向图G=(V,E),如果边<V1,V2>属于E，则称顶点V1邻接到顶点V2,顶点V2邻接自顶点V1
顶点V的入度:以顶点V为头的弧的数目，记为 ID(V)
顶点V的出度:以顶点V为尾的弧的数目，记为 OD(V)
TD(V) = ID(V) + OD(V);
路径:图G=(V,E)中从顶点V1到顶点V2的路线叫从顶点V1到顶点V2的路径，注意有向图和无向图的区别
路径的长度：路径上边/弧的数目
回路/环：第一个顶点和最后一个顶点相同的路径
简单路径：序列中顶点不重复出现的路径
简单回路/简单环:除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路
连通：在无向图G中，如果顶点V1到顶点V2有路径则称V1和V2是连通的
连通图：图中任意两个顶点Vi和Vj都是连通的，则称G是连通图
连通分量：无向图中的极大连通子图
—-连通的子图
—-连通子图含有极大顶点数
—-具有极大顶点数的连通子图包含依附于这些顶点的所有边
强连通图：在该类有向图G中，每一对Vi到Vj都存在路径
强连通分量：有向图中的极大强连通子图
非强连通图有强连通分量，强连通分量不止属于强连通图
连通图的生成树：极小的连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边
有向树：如果一个有向图恰有一个顶点入度为0，其余顶点入度为1，则该图将生成有向树，从而构成森林