计算机科学

首页 > 计算机科学

图 (数学)

2018-07-27 09:57:50     所属分类:数据结构

在数学的分支图论中,Graph)用于表示物件与物件之间的关系,是图论的基本研究对象。一张图由一些小圆点(称为顶点结点)和连结这些圆点的直线或曲线(称为)组成。西尔维斯特在1878年首次提出“图”这一名词。

目录

  • 1 定义
    • 1.1 二元组的定义
    • 1.2 三元组的定义
  • 2 分类
    • 2.1 有向图和无向图
    • 2.2 简单图
    • 2.3 多重图
  • 3 基本术语
  • 4 图的存储表示
  • 5 图的遍历
  • 6 图的重要类型
  • 7 图的同构
  • 8 参考文献
    • 8.1 引用
    • 8.2 来源
  • 9 外部链接
  • 10 参见

定义

图有多种变体,包括简单图、多重图、有向图、无向图等,但大体上有以下两种定义方式。

二元组的定义

一张 是一个二元组,其中称为顶点集,称为边集。它们亦可写成的元素是一个二元组数对,用表示,其中

三元组的定义

一张 是一个三元组,其中称为顶集(Vertices set),称为边集(Edges set),不相交;称为关联函数,中的每一个元素映射到。如果那么称边连接顶点,而则称作的端点,此时关于相邻。同时,若两条边有一个公共顶点,则称关于相邻。

分类

有向图和无向图

如果给图的每条边规定一个方向,那么得到的图称为有向图,其边也称为有向边。在有向图中,与一个节点相关联的边有出边和入边之分,而与一个有向边关联的两个点也有始点和终点之分。相反,边没有方向的图称为无向图

简单图

一个图如果

  1. 没有两条边,它们所关联的两个点都相同(在有向图中,没有两条边的起点终点都分别相同);
  2. 每条边所关联的是两个不同的顶点
则称为简单图(Simple graph)。简单的有向图和无向图都可以使用以上的“二元组的定义”,但形如的序对不能属于E。而无向图的边集必须是对称的,即如果,那么

多重图

若允许两结点间的边数多于一条,又允许顶点通过同一条边和自己关联,则为多重图的概念。它只能用“三元组的定义”。

基本术语

在顶点1有一个环
  • (Order):图中顶集的大小称作图的阶。
  • 子图(Sub-Graph):图称作图的子图如果以及
  • 生成子图(Spanning Sub-Graph):指满足条件的子图
  • (Degree)是一个顶点的度是指与该顶点相关联的总边数,顶点的度记作。度和边有如下关系:
  • 出度(Out-degree)和入度(In-degree):对有向图而言,顶点的度还可分为出度和入度。一个顶点的出度为,是指有条边以该顶点为起点,或说与该点关联的出边共有条。入度的概念也类似。
  • 邻接矩阵
  • 自环(Loop):若一条边的两个顶点相同,则此边称作自环。
  • 路径(Path):从顶点u到顶点v的一条路径是指一个序列的起点终点为称作路径的长度;,称为路径的起点;,称为路径的终点。如果,称该路径是的,反之则称为的;如果两两不等,则称之为简单路径(Simple path,注意,是允许的)。
  • 行迹(Trace):如果路径中边各不相同,则该路径称为的一条行迹。
  • 轨道(Track):即简单路径。
  • 闭的行迹称作回路(Circuit),闭的轨道称作(Cycle)。(现存文献中的命名法并无统一标准。比如在另一种定义中,walk对应上述的path,path对应上述的track,trail对应上述的trace。)
  • 距离(Distance): 从顶点出发到顶点的最短路径若存在,则此路径的长度称作从的距离。若从根本不存在路径,则记该距离为无穷()。
  • 距离矩阵
  • (Bridge):若去掉一条边,便会使得整个图不连通,该边称为桥。

图的存储表示

  • 数组(邻接矩阵)存储表示(有向或无向)
  • 邻接表存储表示
  • 前向星存储表示
  • 有向图的十字链表存储表示
  • 无向图的邻接多重表存储表示

一个不带权图中若两点不相邻,邻接矩阵相应位置为0,对带权图(网),相应位置为∞。一个图的邻接矩阵表示是唯一的,但其邻接表表示不唯一。在邻接表中,对图中每个顶点建立一个单链表(并按建立的次序编号),第i个单链表中的结点表示依附于顶点vi的边(对于有向图是以顶点vi为尾的弧)。每个结点由两个域组成:邻接点域(Adjvex),用以指示与vi邻接的点在图中的位置,链域(Nextarc)用以指向依附于顶点vi的下一条边所对应的结点。如果用邻接表存放网(带权图)的信息,则还需要在结点中增加一个存放权值的域(Info)。每个顶点的单链表中结点的个数即为该顶点的出度(与该顶点连接的边的总数)。无论是存储图或网,都需要在每个单链表前设一表头结点,这些表头结点的第一个域data用于存放结点vi的编号i,第二个域firstarc用于指向链表中第一个结点。

图的遍历

图的遍历方法有深度优先搜索法和广度(宽度)优先搜索法。

深度优先搜索法是树的先根遍历的推广,它的基本思想是:从图G的某个顶点v0出发,访问v0,然后选择一个与v0相邻且没被访问过的顶点vi访问,再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问,依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问,则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w,从w出发按同样的方法向前遍历,直到图中所有顶点都被访问。其递归算法如下:

 1 Boolean visitedMAX_VERTEX_NUM; // 访问标志数组
 2 Status (*VisitFunc)(int v); // VisitFunc是访问函数,对图的每个顶点调用该函数
 3 void DFSTraverse (Graph G, Status(*Visit)(int v)) {
 4     VisitFunc = Visit;
 5     for (v = 0; v < G.vexnum; ++v)
 6         visitedv = FALSE; // 访问标志数组初始化
 7     for (v = 0; v < G.vexnum; ++v)
 8         if (!visitedv)
 9             DFS(G, v);  // 对尚未访问的顶点调用DFS
10 }
11 void DFS(Graph G, int v) { // 从第v个顶点出发递归地深度优先遍历图G
12     visitedv = TRUE;
13     VisitFunc(v);   // 访问第v个顶点
14     for (w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w))
15         // FirstAdjVex返回v的第一个邻接顶点,若顶点在G中没有邻接顶点,则返回空(0)。
16         // 若w是v的邻接顶点,NextAdjVex返回v的(相对于w的)下一个邻接顶点。
17         // 若w是v的最后一个邻接点,则返回空(0)。
18         if (!visitedw)
19             DFS(G, w);  // 对v的尚未访问的邻接顶点w调用DFS
20 }

图的广度优先搜索是树的按层次遍历的推广,它的基本思想是:首先访问初始点vi,并将其标记为已访问过,接着访问vi的所有未被访问过的邻接点vi1,vi2,…, vi t,并均标记已访问过,然后再按照vi1,vi2,…, vi t的次序,访问每一个顶点的所有未被访问过的邻接点,并均标记为已访问过,依次类推,直到图中所有和初始点vi有路径相通的顶点都被访问过为止。其非递归算法如下:

 1 Boolean visited MAX_VERTEX_NUM ; // 访问标志数组
 2 Status (* VisitFunc)(int v); // VisitFunc是访问函数,对图的每个顶点调用该函数
 3 
 4 void BFSTraverse(Graph G, Status(* Visit)(int v)) {
 5     VisitFunc = Visit;
 6     for (v = 0; v < G.vexnum; ++v)
 7         visitedv = FALSE;
 8     initQueue(Q); // 置空辅助队列Q
 9     for (v = 0; v < G.vexnum; ++v) {
10         if (!visitedv) {
11             visitedv = TRUE;
12             VisitFunc(v);
13             EnQueue(Q, v); // v入队列
14             while (!QueueEmpty(Q)) {
15                 DeQueue(Q, u); // 队头元素出队并置为u
16                 for (w = FirstAdjVex(G, u);
17                         w >= 0; w = NextAdjVex(G, u, w))
18                     if (!Visitedw) { // w为u的尚未访问的邻接顶点
19                         Visitedw = TRUE;
20                         VisitFunc(w);
21                         EnQueue(Q, w);
22                     }
23             }
24         }
25     }
26 }

图的重要类型

  • 补图:与G拥有相同的点的完全图删除原图G的边所得到的图成为G的补图
  • 树状图
  • 平面图
  • 连通图
    • 强连通图
    • 强连通分量
  • 有向无环图
    • AOV网
    • AOE网
  • 完全图:每一对不同顶点间都有边相连的的图,记作
  • 二分图:顶集,且每一条边都有一个顶点在中,而另一个顶点在中。
    • 完全二分图:二分图中若任意两个中的顶点都有边相连。若,则图记作
  • 正则图:如果图中所有顶点的度皆相等,则此图称为正则图
  • 欧拉图:存在经过所有边一次(可以多次经过点)的路径的图
  • 哈密顿图:存在经过所有点一次的路径的图

图的同构

对于图与图,若存在从的一一映射f,使任意,都有,则称同构

参考文献

引用

来源

书籍
  • Introduction To Graph Theory, by Gary Chartrand and Ping Zhang, McGraw Hill

外部链接

  • Graph Theory(可下载的书籍,英语)

参见

  • 图论
  • 邻接矩阵
版权声明:本文由北城百科网创作,转载请联系管理获取授权,未经容许转载必究。https://www.beichengjiu.com/computerscience/338656.html

相关推荐