大同住房与城乡建设厅网站,网站建设图片流程,手工制作粽子,西安市招标投标信息网一#xff0c;基本概念
1.基本定义
#xff08;1#xff09;图的定义 顶点集不可以是空集#xff0c;但边集可以是空集。
#xff08;2#xff09;
有向图的表示#xff1a; 圆括号 无向图的表示#xff1a; 尖括号 简单图、多重图#xff1a; 简单图#xff1a;…一基本概念
1.基本定义
1图的定义 顶点集不可以是空集但边集可以是空集。
2
有向图的表示 圆括号 无向图的表示 尖括号 简单图、多重图 简单图
1不存在重复边2不存在从顶点到自身的边
多重图
1图G中某两个节点之间的边数多于一条
2允许通过同一条边与自己关联则G为多重图
数据结构只探讨简单图 三顶点的度。入度出度 对于无向图 顶点v的度是指依附于该顶点的边的条数记为TD(V)
无向图的全部顶点的度的和等于边数的两倍 对于有向图 入度是以顶点v为终点的有向边的数目记为IDv
出度是以顶点v为起点的有向边的数目记为ODv
顶点的度是其入度和出度之和。
四顶点与顶点的关系描述
1路径——两个不同的顶点之间的顶点序列。
2简单路径在路径序列中顶点不重复出现的路径称为简单路径。
3点到点的距离从顶点u出发到顶点v最短路径若存在则此路径的长度称为从u到v的距离,若不存在此路径距离记为无穷。 无向图中若从顶点v到顶点w有路径存在则称v和w是连通的。
有向图中中若从顶点v到顶点w和顶点w和顶点v之间都有路径存在则称v和w之间是强连通的。
这里的路径可以是很多条。 比如说A和B之间就是强连通的而B和E之间就不是。 连通图和强连通图
1特指无向图 2特指有向图 常见考点
1对于n个积极点的无向图G
若G是连通图则最少有n-1条边
若G是非联通图则最多可能有 EP:
当有5个顶点的情况下 地下四个顶点两两相连
上面一个顶点只要与下面任意一个顶点相连就可以使之为连通图 2 接下来我们学习子图研究图的局部 1理解子图的概念首先必须是个图
2包含原图所哟有的vertex记为生成子图。顶点集不可以是空集边集可以是空集 连通分量 1连通 2)极大包含尽可能多的顶点和边 生成树 若图中的顶点数为n则它的生成树含有n-1条边。对于生成树若看去他的一条边则会变成非联通树若加上一条边则会形成一个回路。 与生成树对应得是生成森林 实际应用 几种特殊形态的图: 树和森林 n个顶点的树必有n-1条边
n得顶点的图若边数大于n-1则是有回路的那就不是树了。
