首页 > 笔记 > 图论知识综合

图论知识综合

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

图的储存

图的遍历

图的最短路

图的最小生成树

图的强连通分量

图的最大流


顶点:图中的数据元素。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的有向图。
网:每个边(或弧)都附加一个权值的图,称为带权图。带权的连通图(包括弱连通的有向图)称为网或网络。

 


2 COMMENTS

  1. ShallWe2016-09-07 下午7:27

    年轻人,未来是你的,,, :smile:

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×