php网站开发实例教程下载,网站建设和优化那本书好,家在深圳罗湖,织梦的手机端网站模板目录 1. 定义2. 有向图2.1 定义2.2 举个例子 3. 无向图4. 完全图5. 出度6. 入度7. 度8. 路径9. 简单路径10. 回路 1. 定义
1.图#xff08;Graph#xff09;是由顶点的有穷非空集合和顶点之间边的集合组成#xff0c;图G是由集合V和E构成的二元组#xff0c;记作G(VE)2.V是… 目录 1. 定义2. 有向图2.1 定义2.2 举个例子 3. 无向图4. 完全图5. 出度6. 入度7. 度8. 路径9. 简单路径10. 回路 1. 定义
1.图Graph是由顶点的有穷非空集合和顶点之间边的集合组成图G是由集合V和E构成的二元组记作G(VE)2.V是图中顶点的非空有限集合E是图中边的有限集合3.从数据结构的逻辑关系角度来看图中任一顶点都有可能与其他顶点有关系而图中所有顶点都有可能与某一顶点有关系4.在图中数据元素用顶点表示数据元素之间的关系用边表示5.边集可以是空的即图中可以没有边
2. 有向图
2.1 定义
1.若图中每条边都是有方向的那么顶点之间的关系用vi,vj表示它说明从vi到vj有一条有向边(也称为弧)2.vi是有向边的起点称为弧尾3.vj是有向边的终点称为弧头4.所有边都有方向的图称为有向图5.有向图中vi,vj与vj,vj分别表示两条边
2.2 举个例子
1.一个简单的城市交通网络包含四个交叉路口A、B、C和D。在这个网络中有以下单向道路A-BB-C, C-D, D-A从而形成一条环路。2.这个交通网络可以用一个有向图来表示。在这个有向图中顶点集合V {A, B, C, D}代表四个交叉路口边集合E {A, B, B, C, C, D, D, A}代表单向道路及其方向。
3. 无向图
1.若图中的每条边都是无方向的顶点vi和vj之间的边用vi,vj表示2.在无向图中vi,vj与vj,vi表示的是同一条边
4. 完全图
1.若一个无向图具有n个顶点而每一个顶点与其他n-1个顶点之间都有边称之为无向完全图2.含有n个顶点的无向完全图共有n(n-1)/2条边3.有n个顶点的有向完全图中弧的数目为n(n-1)即任意两个不同顶点之间都有方向相反的两条弧存在
5. 出度
1.顶点的出度指以该顶点为起点的有向边的数目分别记为OD(v)
6. 入度
2.顶点的入度指以该顶点为终点的有向边的数目分别记为ID(v)
7. 度
1.顶点v的度是指关联于该顶点的边的数目记作D(v)2.若G为有向图顶点的度表示该顶点的入度和出度之和3.若G为无向图顶点的度表示与该顶点相连的边的数量
8. 路径
1.在无向图中路径指的是从一个顶点出发沿着边依次访问其他顶点并最终到达另一个顶点的过程。路径中的边和顶点形成了一个序列序列中的顶点和边依次相连且没有重复的顶点和边2.在有向图中路径是指从一个顶点出发沿着有向边依次访问其他顶点并最终到达另一个顶点的过程。有向图的边具有方向性因此路径中的边必须按照其方向进行遍历。3.路径长度是路径上边的数目。假设有一个有向图G其中包含顶点A、B、C和D以及有向边AB、BC和CD。从顶点A到顶点D的路径可以是A→B→C→D这条路径的长度为3因为它包含了3条边。
9. 简单路径
1.简单路径指的是路径中的顶点均不相同的路径即没有重复的顶点。2.简单路径能够清晰地描述顶点之间的直接关系避免了由于顶点重复而导致的路径冗余3.假设有一个无向图G顶点集V(G) {A, B, C, D, E}边集E(G) {(A, B), (B, C), (C, D), (D, E), (E, A)}。在这个图中一条从顶点A到顶点D的简单路径可以是A→B→C→D。这条路径中每个顶点A、B、C、D都只出现一次没有重复因此它是一条简单路径。4.假设有一个有向图H顶点集V(H) {X, Y, Z, W}边集E(H) {(X, Y), (Y, Z), (Z, W), (W, X)}。在这个有向图中一条从顶点X到顶点W的简单路径可以是X→Y→Z→W。这条路径中每个顶点X、Y、Z、W都按照有向边的方向遍历且只出现一次没有重复因此它也是一条简单路径。
10. 回路
1.第一个顶点和最后一个顶点相同的路径称为回路或环2.它指的是从某个顶点出发沿着有向边经过一系列顶点最终回到起始顶点的路径3.回路的起始顶点和结束顶点是相同的形成了一个闭环4.回路中的边必须按照其方向进行遍历形成一条合法的有向路径
