二手网站专业做附近人的有吗济南 网站建设

图论起源于欧拉对哥尼斯堡七桥问题的解决. 他构建的图模型将陆地用点来表示, 桥梁则用线表示, 如此一来, 该问题便转化为在图中能否不重复地遍历每条边的问题.

图论的应用

地图着色

在地图着色问题中, 我们用顶点代表国家, 将相邻国家之间用边相连. 这样, 问题就转化为用最少的颜色给图的顶点着色, 同时要保证相邻顶点的颜色不同. 四色定理表明, 任何地图都可以用四种颜色进行着色.

频率分配

以顶点表示发射机, 将干扰范围内的发射机之间用边相连. 频率分配问题就可以转化为给顶点标记数字, 使得相邻顶点标记的数字差值尽可能大.

燃气供应

利用平面图进行建模, 其中顶点表示路口, 边表示道路, 面表示区域. 通过寻找最小面生成子图, 能够确定铺设燃气管道的最优道路网络, 从而实现成本的最小化.

布局规划

在 VLSI(超大规模集成电路)和建筑布局规划中, 用图来表示模块或房间之间的连接关系. 通过对平面图进行三角剖分, 构建对偶图并绘制矩形图, 从而得到布局方案.

其他应用

图论还广泛应用于万维网社区发现, 生物信息学(如 RNA 结构描述), 软件工程(如控制流图用于软件测试)等诸多领域.

图的基本概念

图的定义

图(Graph)

一个图$G$由两个集合组成, 即顶点集$V(G)$和边集$E(G)$, 通常记为$G=(V,E)$. 顶点(Vertex, 也称为节点 Node)是图的基本元素, 用于表示研究的对象; 边(Edge)是连接两个顶点的线, 用于表示对象之间的关系. 若图中无自环边( 从 $v$ 到 $v$ ) 且无重边(两个节点之间存在多条边), 则为简单图, 反之则为多重图.

顶点(Vertex)

顶点是图中的基本元素, 即图的节点. 顶点可以有自己的属性, 例如在社交网络的图模型中, 顶点代表用户, 每个顶点可能包含用户的年龄, 性别等属性信息.

边(Edge)

边是连接两个顶点的线. 根据边是否有方向, 图可分为无向图和有向图. 在无向图中, 边没有方向, 若顶点$u$和$v$之间有边, 则表示为$(u,v)$, 且$(u,v)$和$(v,u)$表示同一条边; 在有向图中, 边有方向, 从顶点$u$指向顶点$v$的边表示为$(u,v)$, 它与从$v$指向$u$的边$(v,u)$是不同的边.

邻接(Adjacency)

在无向图中, 如果两个顶点$u$和$v$之间有一条边$(u,v)$, 则称顶点$u$和$v$是邻接的; 在有向图中, 如果存在一条从顶点$u$到顶点$v$的有向边$(u,v)$, 则称顶点$u$邻接到顶点$v$, 顶点$v$邻接自顶点$u$.

度(Degree)

对于无向图中的一个顶点$v$, 它的度是与该顶点相关联的边的数量, 记为$d(v)$; 在有向图中, 顶点的度分为入度和出度. 入度(In - degree)是指以该顶点为终点的有向边的数量, 记为$d^{-}(v)$, 出度(Out - degree)是指以该顶点为起点的有向边的数量, 记为$d^{+}(v)$, 顶点$v$的度等于其入度与出度之和, 即$d(v)=d^{-}(v)+d^{+}(v)$.

路径(Path)

在图中, 从一个顶点$v_0$开始, 依次经过一系列相邻的顶点$v_1,v_2,\cdots ,v_n$所形成的顶点序列, 其中$(v_{i-1},v_i)\in E$(对于无向图)或$(v_{i-1},v_i)\in E$(对于有向图, $i=1,2,\cdots ,n$), 这个顶点序列就称为从$v_0$到$v_n$的路径. 路径中边的数量称为路径的长度.

回路(Cycle)

在图中, 起点和终点相同的路径称为回路, 也叫环. 也就是说, 如果路径$v_0,v_1,\cdots ,v_n$满足$v_0=v_n$且$n\ge 1$, 则它是一个回路.

连通图(Connected Graph)

在无向图中, 如果对于图中的任意两个顶点$u$和$v$, 都存在一条从$u$到$v$的路径, 则称该图是连通图; 在有向图中, 如果对于图中的任意两个顶点$u$和$v$, 都存在从$u$到$v$的路径以及从$v$到$u$的路径, 则称该有向图是强连通图. 如果一个有向图不是强连通图, 但忽略边的方向后得到的无向图是连通图, 则称该有向图是弱连通图.

子图(Subgraph)

给定一个图$G=(V,E)$, 如果存在另一个图$G^{\prime }=(V^{\prime },E^{\prime })$, 其中$V^{\prime }\subseteq V$($V^{\prime }$是$V$的子集)且$E^{\prime }\subseteq E$($E^{\prime }$是$E$的子集), 并且$E^{\prime }$中的边所关联的顶点都在$V^{\prime }$中, 则称$G^{\prime }$是$G$的子图.

树(Tree)

无向连通且无回路的图称为树. 树中度数为 1 的顶点称为叶子节点, 其他顶点称为内部节点. 在树中, 任意两个顶点之间恰好存在一条路径. 有根树是一种特殊的树, 它有一个被指定为根的顶点, 从根到其他顶点有唯一的路径.

图的分类

正则图

所有顶点度相等的图是正则图, 当度为$k$时, 称为$k-$正则图. 例如, 零图是$0-$正则图, 简单循环是$2-$正则图, 彼得森图是$3-$正则图, 还有$5-$正则的甜甜圈图和$d-$维超立方体等.

子图

图$G=(V,E)$的子图$G^{\prime }=(V^{\prime },E^{\prime })$满足$V^{\prime }\subseteq V$且$E^{\prime }\subseteq E$. 可以通过删除顶点或边得到子图, 如$G-e$, $G-v$ . 还有顶点集或边集诱导的子图, 如$G[W]$ , $G[F]$ .

特殊图类

包括空图(边集为空, 记为$N_n$ ), 完全图(任意两顶点相邻, $K_n$有$n(n-1)/2$条边), 独立集和二分图(顶点集可分成两个独立子集, 完全二分图$K_{m,n}$有$m\times n$条边), 路径图($P_n$除端点外顶点度为 2 ), 循环图($C_n$所有顶点度为 2 ), 轮图($W_n$由$C_{n-1}$加新顶点连接所有$C_{n-1}$顶点得到).

图的操作

图的运算

• 集合运算: 图$G_1$和$G_2$的并集$G_1\cup G_2$顶点集为$V_1\cup V_2$ , 边集为$E_1\cup E_2$; 交集$G_1\cap G_2$顶点集为$V_1\cap V_2$ , 边集为$E_1\cap E_2$ .
• 其他运算: 图$G$的补图$\bar{G}$与$G$顶点集相同, 两顶点在$\bar{G}$中有边当且仅当在$G$中无边; 细分是删边并通过新顶点添加路径; 收缩边是删边并合并两顶点.

图同构

图$G_1$和$G_2$间存在一一对应关系, 使对应顶点间边数相等, 则两图同构, 记为$G_1\cong G_2$ . 同构关系是等价关系, 判断图同构目前尚无多项式时间算法.

度序列

图的度序列是顶点度的非增排列, 满足度和公式(和为偶数)的序列可能是图的度序列, 简单图的度序列叫图序列, 可通过递归算法判断.

数据结构与图的表示

邻接矩阵

邻接矩阵是$n\times n$矩阵, 元素为两顶点间边数, 简单图邻接矩阵元素为 0 或 1 , 主对角线为 0 , 空间复杂度$O(n^2)$ ; 关联矩阵是$n\times m$矩阵, 元素表示顶点与边是否关联, 空间复杂度$n\times m$ ; 邻接表是数组, 每个顶点对应一个包含其邻居记录的列表, 空间复杂度$O(n+m)$ .

邻接表

用数组存储顶点的邻接顶点列表, 空间复杂度$O(n+m)$ , 适用于边数较少的图.