加载中…
个人资料
_陌上花开7_
_陌上花开7_
  • 博客等级:
  • 博客积分:0
  • 博客访问:68,244
  • 关注人气:29
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

图的基本知识

(2013-07-18 15:56:39)
标签:

森林

分类: 数据结构

图的定义和基本的术语

顶点:在图中的数据元素

:由顶点的有穷非空集合和顶点之间的边的集合组成,通常表示为G=(V,E),其中G表示一个图,V表示顶点的集合,E表示图G中顶点之间边的集合。如果图的任意两个顶点之间的边都是无向边,则成该图是无向图,否则称该图为有向图

在图中,吐过不存在顶点到自身的边,且同一条边不重复出现,则称这样的图为简单图

在无向图中,对于任意两个顶点vi和vj,若存在边(vi,vj),则称顶点vi和vj互为邻接点,同时称边(vi,vj)依附于顶点vi和vj。

在有向图中,对于任意两个顶点vi和vj,若存在弧,,则称顶点vi邻接到vj,顶点vj邻接自vi,同时称弧依附于顶点vi和vj。通常成vj是vi的邻接点。

无向完全图:在无向图中,任意两个顶点之间都存在边。含有n个顶点的无向完全图有n*(n+1)/2条边。

              在有向图中,任意两顶点间都存在方向相反的两条弧。含有n个顶点的有向完全图有n*(n+1)条边

              显然,在完全图中,边(或者弧)的数目达到最大。

 

顶点的度、入度、出度

在无向图中顶点v的度是指依附于该顶点的边的个数,记为TD(V).在具有n个订单e条边的无向图中TD(V)求和是2e有向图中出度的个数OD(V)和入度的个数ID(V)分别求和结果相等都等于e。

权、网

权通常是指对边赋予的有意义的数值量。边上带权的图称为网或网图。

路径、路径长度、回路

路径上边的数目称为路径长度。第一个顶点和最后一个顶点相同的路径称为回路或者环。

简单路径、简单回路

在路径序列中,顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路称为简单回路

连通图、连通分量

在无向图中,若任意顶点vi和vj之间有路径,则称该图是连通图。非连通图的极大连通子图称为连通分量,极大的含义是指包括所有连通的顶点以及和这些顶点相关联的所有边。

强连通图、强连通分量

在有向图中,对任意顶点vi和vj,若从顶点vi和vj均有路径,则称该有向图是强连通图。非强连通图的极大请连同的极大强连通子图称为强连通分量

生成树、生成森林

具有n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图。连通图的生成树是一个自由树,可以再生成树中任意指定一个顶点为树的根节点。在生成树中添加任意一条属于原图中的边必定会产生回路,因为新添加的边使其所依附的两个顶点之间游离第二天路径;在生成树中减少任意一条边,则必然成为非连通。所以一颗具有n个顶点的生成树有且仅有n-1条边。具有n个顶点的有向图G的生成树是包含G中全部顶点的一个子图,且子图中只有一个入度为零的顶点,其他顶点的入度均为1。

在非连通图中,由每个连通分量都可以得到一棵生成树,这些连通分量的生成树构成了非连通图的生成森林

 

 

 

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有