<学习笔记>关于图的理论知识

2018-06-17 21:37:00来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

什么是图|ω?`)

图G是一个有序二元组(V,E),其中V称为顶集(Vertices Set),E称为边集(Edges set),E与V不相交。它们亦可写成V(G)和E(G)。

E的元素都是二元组,用(x,y)表示,其中x,y∈V。 (摘自百度百科)

 

简单来说,图就是由点和边组成的东西。也可以理解为若干个元素之间关系的抽象表示,边即代表着对应顶点之间的相互关系。

图的分类|ω?`)

1.有向图与无向图:

如果我们给图中的每个边规定了方向,即边< x,y >中顶点x和y的顺序不能随便颠倒,那这个图就叫做有向图,反之即为无向图。

2.单图:

一个图如果任意两顶点之间只有一条边(在有向图中为两顶点之间每个方向只有一条边);边集中不含环,则称为单图。

3.连通图、非连通图与强连通图:

在无向图中,如果从顶点vi到顶点vj有路径,则称vi和vj连通。如果图中任意两个顶点之间都连通,则称该图为连通图,否则,将其中的极大连通子图称为连通分量。在有向图中,如果对于每一对顶点vi和vj,从vi到vj和从vj到vi都有路径,则称该图为强连通图;否则,将其中的极大连通子图称为强连通分量。
*没有环的有向图叫做DAG。

4.简单图与树:

如果对于任意的顶点x和y,最多只有一条边把他们相连,也就是说边集中不含两个或以上的(x,y),那么图G称为简单图。简单图可以用矩阵表示。
没有环的无向连通图叫做无向树。
如果把一个有向图变为无向图后成为无向树,那么称这个有向图为一棵有向树。
特别的:一个点也叫作一棵树,如果有很多树就叫做森林。
如果有向树中存在一个顶点x使得从x能够到达其余所有顶点,那么有向树G=(V,E)称为根在x的树形图。

有关图的定义|ω?`)

  • 阶(Order): 图G的顶集V的大小(即顶点的数量)。
  • 度(Degree):一个顶点的度是指与该顶点相连的边的条数,顶点v的度记作d(v)。

    *入度和出度:有向图中,一个点的入度为以该点为终点的路径数量,出度为以该点为起点的路径数量。

  • 子图(Sub-Graph):当图G’=(V’,E’) 其中V‘含于V,E’含于E,则G’称作图G=(V,E)的子图。每个图都是本身的子图。
  • 生成子图(Spanning Sub-Graph):如果图g的点集与G的点集相同,g的边集含于G的边集,那么称g为G的生成子图。特别的,如果g为无向树,那么称g为图G的生成树。
  • 导出子图(Induced Subgraph):顶集V1为V的非空子集,以两端点均在V1中的(E中的)全体边为边集的G的子图,称为V1导出的导出子图;边集E1为E的非空子集,以E1中边关联的顶点的全体为顶点集的G的子图,称为E1导出的导出子图。

    *可知,图G的任何子图,都可以看作是图G的某个导出子图的生成子图。

  • 路径(Path):从u到v的一条路径是指一个序列v0,e1,v1,e2,v2,…ek,vk,(A–1–>B–2–>C…),其中ei的顶点为vi及vi - 1,k称作路径长度。如果它的起止顶点相同,该路径是“闭”的,反之,则称为“开”的。如果这条路径除了u和w以外其余顶点都各不相等,那么称这条路径为简单路径。

    *路径长度: 一条路径所经过的边的数量。
    *长度:路径中所有边的权值的和(可能为负)。

  • 行迹(Trace):如果路径P(u,v)中的边各不相同,则该路径称为u到v的一条行迹。
  • 轨道(Track):如果路径P(u,v)中的顶点各不相同,则该路径称为u到v的一条轨道。
    *闭的行迹称作回路(Circuit),闭的轨称作圈(Cycle)
  • 环:如果一条路径的起点和终点相等,那么这条路径称为环(回路)。
  • 自环(Loop):若一条边的两个顶点为同一顶点,则此边称作自环。
  • 桥(Bridge):若去掉一条边,便会使得整个图不连通,该边称为桥。
  • 割点:若去掉一个点,便会使得整个图不连通,则该顶点成为割点。

(参考百度百科)

图的储存|ω?`)

1.列表:开三个数组分别记录每条边的起点,终点和权值。
2.邻接矩阵:f[i][j]=d表示一条从i到j的权值为d的边。
3.邻接表:用链表和结构体存每一条边,并记下每个点连出的边。
4.有向图的十字链表存储表示。
5.无向图的邻接多重表存储表示。

*一个不带权图中若两点不相邻,邻接矩阵相应位置为0,对带权图(网),相应位置为∞。一个图的邻接矩阵表示是唯一的,但其邻接表表示不唯一。

*在有向图中,通常将边称作弧,含箭头的一端称为弧头,另一端称为弧尾,记作< vi,vj >,它表示从顶点vi到顶点vj有一条边。若有向图中有n个顶点,则最多有n(n-1)条弧,我们又将具有n(n-1)条弧的有向图称作有向完全图。以顶点v为弧尾的弧的数目称作顶点v的出度,以顶点v为弧头的弧的数目称作顶点v的入度。

*在无向图中,边记作(vi,vj),它蕴涵着存在< vi,vj >和< vj,vi >两条弧。若无向图中有n个顶点,则最多有n(n-1)/2条弧,我们又将具有n(n-1)/2条弧的无向图称作无向完全图。与顶点v相关的边的条数称作顶点v的度。
(摘自百度百科)

图的遍历|ω?`)

深度优先搜索(dfs)和广度优先搜索(bfs)。

树中的边|ω?`)

    • 树边指的是从父节点找到子结点所用的边
    • 前向边指的是从祖先结点指向其子孙结点的非树边
    • 后向边指的是从子孙结点往回指向祖先结点的边
    • 横叉边指的是没有祖孙关系的两个结点之间的边,起点的遍历顺序在终点之后。

PS:就先整理这些吧,以后再补充2333ヾ?≧?≦)o

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:字符串hash入门

下一篇:第四章函数作业题,内置函数