宋庄网站建设,腾和企业网站管理系统,个人网站制作网站,卖域名图的定义和基本术语1.图的定义2.图的基本术语3.图的分类1.图的定义
图是由顶点和有穷非空集合和顶点边的集合吗#xff0c;表示为G(V,E)。 G表示一个图#xff0c;V是图G的顶点#xff08;数据元素#xff09;的集合#xff0c;E是图G中顶点之间边的集合。在图中#xf…
图的定义和基本术语1.图的定义2.图的基本术语3.图的分类1.图的定义
图是由顶点和有穷非空集合和顶点边的集合吗表示为G(V,E)。 G表示一个图V是图G的顶点数据元素的集合E是图G中顶点之间边的集合。在图中顶点个数不能为零但可以没有边。
2.图的基本术语
结点图中的顶点 结点间的关系图中顶点之间的连线 无向图顶点之间的连线没有方向用v,w表示 有向图顶点之间的连线有方向用 v,w 表示。v称为弧尾w称为弧头。 v的入度有向图中以顶点v为弧头弧的数目。 v的出度有向图中以顶点v为弧尾弧的数目。 v的度无向图中有光联的边有向图中出度和入度之和。 路径从一个顶点到另一个顶点之间的路径。 路径长度无向图路径上边的数目就是长度有向图路径上权重之和就是长度。 简单路径路径中的结点不重复。 简单回路简单路径中第一个结点和最后一个结点是相同的一个顶点。 子图边和顶点都是子集。
3.图的分类
1.从图中的方向性以及边上是否有权划分 有向图边有方向无权。有向网边有方向、有权。 无向图边没有方向无权。无向网边没有方向有权 2.从图中的边弧数e和顶点数n之间的关系划分 无向完全图对于n个顶点任意两个顶点之间都有边en * n-1/2 有向完全图对于n的结点任意结点都能直接互相到达en * n-1 稀疏图e nlogn 稠密图e nlogn 3.从连通性上划分 1无向图 连通性若从顶点vi到顶点vj有路径则称vi和vj连通。 连通图任意两个结点都是连通。 连通分量极大连通子图含有极大顶点数如果多加1个顶点子图就不连通了和依附于这些顶点的所有边。 2有向图 强连通性从顶点vi到顶点vj有路径则vj到vi也有路径。 强连通图任意两个顶点都是强连通的。 强连通分量极大强连通子图 3生成树和生成森林 生成树极小连通子图包含图中的全部顶点和连接全部顶点的n-1条边。如果多出一条边就出现回路。少一条边就非连通。生成树不唯一 生成森林非连通图中存在若干个连通分量每一个连通分量对于一棵生成树这些连通分量的生成树组成了一个非连通图的生成树。
