图 (数学)

✍ dations ◷ 2024-12-22 23:37:15 #Pages using deprecated source tags,自2020年5月需要从英语维基百科翻译的条目,图论,数据结构

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

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

一张图 $G {\displaystyle G}$ $G$ 是一个二元组 $(V,E)$ $(V,E)$ ，其中 $V {\displaystyle V}$ $V$ 称为顶点集， $E {\displaystyle E}$ $E$ 称为边集。它们亦可写成 $V(G)$ $V(G)$ 和 $E(G)$ $E(G)$ 。 $E {\displaystyle E}$ $E$ 的元素是一个二元组数对，用 $(x,y)$ $(x,y)$ 表示，其中 $x,y\in V$ $x,y \in V$ 。

一张图 $G {\displaystyle G}$ $G$ 是一个三元组 $(V,E,I)$ $(V,E,I)$ ，其中 $V {\displaystyle V}$ $V$ 称为顶集（Vertices set）， $E {\displaystyle E}$ $E$ 称为边集（Edges set）， $E {\displaystyle E}$ $E$ 与 $V {\displaystyle V}$ $V$ 不相交； $I {\displaystyle I}$ $I$ 称为关联函数， $I {\displaystyle I}$ $I$ 将 $E {\displaystyle E}$ $E$ 中的每一个元素映射到 $V\times V$ $V\times V$ 。如果 $I(e)=(u,v)(e\in E,u,v\in V)$ $I(e)=(u,v) (e\in E, u,v \in V)$ 那么称边 $e {\displaystyle e}$ $e$ 连接顶点 $u, v {\displaystyle u,v}$ $u,v$ ，而 $u, v {\displaystyle u,v}$ $u,v$ 则称作 $e {\displaystyle e}$ $e$ 的端点， $u, v {\displaystyle u,v}$ $u,v$ 此时关于 $e {\displaystyle e}$ $e$ 相邻。同时，若两条边 $i, j {\displaystyle i,j}$ $i,j$ 有一个公共顶点 $u {\displaystyle u}$ $u$ ，则称 $i, j {\displaystyle i,j}$ $i,j$ 关于 $u {\displaystyle u}$ $u$ 相邻。

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

一个图如果

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

一个不带权图中若两点不相邻，邻接矩阵相应位置为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 visited; // 访问标志数组 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         visited = FALSE; // 访问标志数组初始化 7     for (v = 0; v < G.vexnum; ++v) 8         if (!visited) 9             DFS(G, v);  // 对尚未访问的顶点调用DFS10 }11 void DFS(Graph G, int v) { // 从第v个顶点出发递归地深度优先遍历图G12     visited = 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 (!visited)19             DFS(G, w);  // 对v的尚未访问的邻接顶点w调用DFS20 }

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

 1 Boolean visited; // 访问标志数组 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         visited = FALSE; 8     initQueue(Q); // 置空辅助队列Q 9     for (v = 0; v < G.vexnum; ++v) {10         if (!visited) {11             visited = TRUE;12             VisitFunc(v);13             EnQueue(Q, v); // v入队列14             while (!QueueEmpty(Q)) {15                 DeQueue(Q, u); // 队头元素出队并置为u16                 for (w = FirstAdjVex(G, u);17                         w >= 0; w = NextAdjVex(G, u, w))18                     if (!Visited) { // w为u的尚未访问的邻接顶点19                         Visited = TRUE;20                         VisitFunc(w);21                         EnQueue(Q, w);22                     }23             }24         }25     }26 }

图的重要类型

补图：与G拥有相同的点的完全图删除原图G的边所得到的图成为G的补图
树状图
平面图
连通图
- 强连通图
- 强连通分量
有向无环图
- AOV网
- AOE网
完全图：每一对不同顶点间都有边相连的的图，记作 $K_{n}$ $K_n$ 。
二分图：顶集 V = X ∪ Y ( X ∩ Y = ϕ ) {\displaystyle V=X\cup Y(X\cap Y=\phi )} ，且每一条边都有一个顶点在 X {\displaystyle X} 中，而另一个顶点在 Y {\displaystyle Y} 中。
- 完全二分图：二分图 $G {\displaystyle G}$ $G$ 中若任意两个 $X {\displaystyle X}$ $X$ 和 $Y {\displaystyle Y}$ $Y$ 中的顶点都有边相连。若 $\left|X\right|=m,\left|Y\right|=n$ $\left|X\right|=m,\left|Y\right|=n$ ，则图 $G {\displaystyle G}$ $G$ 记作 $K_{m,n}$ $K_{m,n}$ 。
正则图：如果图中所有顶点的度皆相等，则此图称为正则图
欧拉图:存在经过所有边一次（可以多次经过点）的路径的图
哈密顿图:存在经过所有点一次的路径的图
加权图（weighted graph）：一个加权图在图中的每条边上给出一个值（权重）

图的同构

对于图 $G(V,E)$ $G(V,E)$ 与图 $G'(V',E')$ $G'(V',E')$ ，若存在从 $V {\displaystyle V}$ $V$ 到 $V^{'} {\displaystyle V'}$ $V'$ 的一一映射f，使任意 $(u,v)\in E$ $(u,v) \in E$ ,都有 $(f(u),f(v))\in E'$ $(f(u),f(v))\in E'$ ，则称 $G {\displaystyle G}$ $G$ 与 $G^{'} {\displaystyle G'}$ $G'$ 同构