图论知识综合

图论的知识终于坑完了。。。要疯狂刷题了。。。

图
顶点：图中的数据元素。V是顶点的有穷非空集合。
弧：<v,w>表示从v到w的一条弧，v为弧尾，w为弧头。VR是两个顶点关系的集合。
无向图：若<v,w>∈VR，必有<w,v>∈VR，则此图为无向图。
有向图：无上述关系的图。
边：(v,w)表示无向图中顶点v和顶点w之间的一条边。

完全无向图和完全有向图
n表示顶点数，e表示弧或边的数，则对于无向图，e的取值范围为0~n(n-1)/2。对于有向图，e的取值范围为0~n(n-1)。完全无向图：有n(n-1)/2条边的无向图。完全有向图：有n(n-1)条弧的有向图。

稀疏图：弧或边较少的图。(e<nlogn)
稠密图：弧或边较多的图。
权(Weight)：与图的边和弧相关的数。权可以表示从一个顶点到另一个顶点的距离或耗费。

子图：若图G=(V,{E})和G’=(V’,{E’})存在关系：V’ÍV且E’ÍE，则称G’为G的子图。

邻接，度，入度，出度：
对于无向图G=(V,{E})，若边(v,v’)∈E，则v和v’互为邻接点，该边依附于v和v’，或称边与两点相关联。顶点v的度TD(v)为和v相关联的边的数目。
对于有向图G=(V,{A})，若弧<v,v’>∈A，则v邻接到v’，v’邻接自v，弧与两点相关联。以v为头的弧的数目成为v的入度ID(v)，以v为尾的弧的数目成为v的出度OD(v)，顶点v的度为入度和出度之和。
弧或边的数目e和度TD的关系：e=1/2 (TD(v1)+TD(v2)+…+TD(vn))

路径(Path)、路径长度、回路(Cycle)：
对无向图G=(V，E)，若从顶点vi经过若干条边能到达vj，称顶点vi和vj是连通的，又称顶点vi到vj有路径。
对有向图G=(V，A)，从顶点vi到vj有有向路径，指的是从顶点vi经过若干条有向边(弧)能到达vj。
路径上边或弧的数目称为该路径的长度。
在一条路径中，若没有重复相同的顶点，该路径称为简单路径；第一个顶点和最后一个顶点相同的路径称为回路(环)；在一个回路中，若除第一个与最后一个顶点外，其余顶点不重复出现的回路称为简单回路(简单环)。

连通图、图的连通分量：
对无向图G=(V，E)，若”vi ，vj ÎV，vi和vj都是连通的，则称图G是连通图，否则称为非连通图。若G是非连通图，则极大的连通子图称为G的连通分量。
对有向图G=(V，A)，若”vi ，vj ÎV，都有以vi为起点， vj 为终点以及以vj为起点，vi为终点的有向路径，称图G是强连通图，否则称为非强连通图。若G是非强连通图，则极大的强连通子图称为G的强连通分量。
“极大”的含义：指的是对子图再增加图G中的其它顶点，子图就不再连通。

生成树、生成森林：
一个连通图(无向图)的生成树是一个极小连通子图，它含有图中全部n个顶点和只有足以构成一棵树的n-1条边，称为图的生成树。
关于无向图的生成树的几个结论：
a)        一棵有n个顶点的生成树有且仅有n-1条边；
b)        如果一个图有n个顶点和小于n-1条边，则是非连通图；
c)        如果多于n-1条边，则一定有环；
d)       有n-1条边的图不一定是生成树。
有向图的生成森林是这样一个子图，由若干棵有向树组成，含有图中全部顶点。有向树是只有一个顶点的入度为0 ，其余顶点的入度均为1的有向图。
网：每个边(或弧)都附加一个权值的图，称为带权图。带权的连通图(包括弱连通的有向图)称为网或网络。