第六章图论Graph

离散图论知识点总结

一、基本概念

图（Graph）是离散数学中的一个重要概念，它由顶点集合V和边集合E组成。一般用G（V，E）来表示，其中V={v1,v2,…,vn}是有限非空集合，E是V中元素的无序对的集合。图分为有向图和无向图。无向图中的边是无序的，有向图中的边是有序的。图中存在一些特殊的图，比如完全图、树、路径、回路等。

二、图的表示方法

1. 邻接矩阵

邻接矩阵是一种常见的图的表示方法，它使用一个二维数组来表示图的关系。对于一个n个顶点的图，邻接矩阵是一个n*n的矩阵A，其中A[i][j]表示顶点i到顶点j之间是否存在边。对于无向图，A[i][j]=1表示顶点i与顶点j之间存在边，A[i][j]=0表示不存在。对于有向图，A[i][j]=1表示i指向j的边存在，A[i][j]=0表示不存在。

2. 邻接表

邻接表是另一种常见的图的表示方法。它将图的信息储存在一个数组中，数组的每个元素与图的一个顶点相对应。对于每个顶点vi，数组中储存与该顶点邻接的顶点的信息。邻接表可以用链表或者数组来表示，链表表示的邻接表比较灵活，但是在查找某个边的相邻顶点时需要遍历整个链表。

三、图的性质

1. 度

图中每个顶点的度是与其相邻的边的数目。对于无向图，顶点的度等于与其相邻的边的数目；对于有向图，则分为入度和出度。

2. 连通性

对于无向图G，若图中任意两个顶点都有路径相连，则称图G是连通的。对于有向图G，若从任意一个顶点vi到任意一个顶点vj都存在路径，则称G是强连通的。

3. 路径和回路

路径是指图中一系列的边，连接图中的两个顶点；回路是指起点与终点相同的路径。路径的长度是指路径中边的数目。

4. 树和森林 一个无向图，如果是连通图且不存在回路，则称为树。一个无向图，若它不是连通图，则称为森林。

四、图的常见算法

1. 深度优先搜索（DFS）

深度优先搜索是一种用于图的遍历的算法，它从图的某个顶点vi出发，访问它的所有邻接顶点，再对其中未访问的顶点继续深度优先搜索。

图论基础知识的名词解释

图论是数学的一个分支，研究图的属性和关系。图是由节点和节点之间的边组成的抽象模型，被广泛应用于计算机科学、网络分析、医学和社会科学等领域。下面，我们将解释一些图论中常用的基础概念和术语。

1. 图 (Graph)

图是图论研究的基本对象，由一组节点和连接这些节点的边组成。节点也被称为顶点 (Vertex)，边则是节点之间的连接线。图可以分为有向图 (Directed Graph) 和无向图 (Undirected Graph) 两种类型。在有向图中，边有方向，从一个节点指向另一个节点；而在无向图中，边没有方向，节点之间的关系是双向的。

2. 顶点度数 (Degree of a Vertex)

顶点度数指的是一个顶点与其他顶点相邻的边的数量。在无向图中，顶点度数即与该顶点相连的边的数量；在有向图中，则分为入度 (In-degree) 和出度 (Out-degree)。入度表示指向该节点的边的数量，而出度表示从该节点出发的边的数量。

3. 路径 (Path)

路径指的是通过边连接的一系列节点，形成的顺序序列。路径的长度是指路径上边的数量。最短路径 (Shortest Path) 是指连接两个节点的最短长度的路径。最短路径算法被广泛应用于计算机网络中的路由选择和地图导航系统中的路径规划。

4. 连通图 (Connected Graph)

连通图是指图中的任意两个节点之间都存在路径的图。如果一个图不是连通图，那么它可以被分割为多个连通分量 (Connected Component)。连通图在社交网络分析和传感器网络等领域中具有重要的应用。

5. 完全图 (Complete Graph) 完全图是指任意两个节点之间都存在边的图。在完全图中，每对节点之间都有一条边相连。n个节点的完全图有n(n-1)/2条边。完全图经常用于描述需要互相交流的问题，如计算机网络中的通信。

6. 树 (Tree)

基本概念

图（graph）是数学关系的表示，由非空节点集V和有限边集E组成。

不同节点组成的无序对称作边（edge）。

设图G，若令V={v1,v2,...,vn}是包含n个节点的集合，其m条边的集合E={e1,e2,...,em}，其中，每一条边都是集合V的二元素子集{vi,vj}，简记为vivj或vjvi。

集合V(G)中的基数n表示图的阶（rank）。

集合E(G)中的基数m表示图的规模（size）。

若vi∈V(G)，vj∈V(G)，且vivj组成的节点对vivj∈E(G)，或者说vivj是图G的边，则称vi和vj邻接（adjacency），否则，称vi和vj不邻接（unadjacency）。

结点的度（degree）是指与v邻接的节点数，记作deg(v)，若特指图G的结点v的度就写作degG(v)。

边vivj与vi和vj相关联（relevancy）。

度为零的点称作孤立点（isolated point）。

度为1的结点称为端结点（end point），若是一个很像树的图，度为1的结点又称为叶子（leaf）。

图G的最小度（min degree）是指所有结点中的最小度数，记作δ(G)。 图G的最大度（max degree）是指所有结点中的最大度数，记作Δ(G)。

若图G的所有结点有相同的度数，那么δ(G)=Δ(G)，图G称为正则图（regular graph）。

若图G的所有结点的度都是r，则图G称为r-正则图（r-regular

graph）。

基本定理

欧拉定理 在任何图中，结点度的总和等于边数的两倍。

推论 在任何图中，结点度的总和是一个非负偶数。

图论介绍（GraphTheory）

1 图论概述

1.1 发展历史

第⼀阶段：1736：欧拉发表⾸篇关于图论的⽂章，研究了哥尼斯堡七桥问题，被称为图论之⽗

1750：提出了拓扑学的第⼀个定理，多⾯体欧拉公式：V-E+F=2

第⼆阶段（19~20世纪）：1852: Francis Guthrie提出四⾊问题

1856: Thomas P. Kirkman & William R.Hamilton研究了哈密尔顿图

1878: Alfred Kempe给出给出四⾊定理证明

1890: 希伍德（Heawood）推翻原有四⾊定理证明

1891: 彼得森（Petersen 丹麦）给出关于图论的理论知识的第⼀篇论⽂

1936: 哥尼格(Dénes Kőnig Hungarian), 写出第⼀本图论专著《有限图与⽆限图的理论》，图论成为了⼀门独⽴学科

第三阶段（现代图论）：1941: F. P. Ramsey开创 Extremal graph theory

1959: Erd˝os and Rényi 引⼊随机图理论 （边的存在的概率为p）

1976: Kenneth Appel & Wolfgang Haken使⽤计算机最终证明了四⾊问题

1.2 参考教材

Graph Theory with Application - J.A. Bondy and U.S.R. Murty, Elsevier, 1976

《图论及其应⽤》 经典教材，吴望名译，有电⼦版Graph theory - J.A. Bondy and U.S.R. Murty, Springer, 2008

《图论》GTM244，可以认为是 “Graph Theory with Application” 的第⼆版，推荐教材Graph Theory, 5th - Reinhard Diestel, Springer, 2017

《图论》GTM173，有电⼦版Introduction to Graph Theory, 2nd- Douglas B. West, 2017