下载文档原格式
离散图论知识点总结一、基本概念图（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 图定义设A,B是两个集合，称{{a,b}|a∈A,b∈}B 为A与B的无序积，记为A&B；{a,b}称为无序对。
后面，把{a,b}记为(a,b)，且允许a=b；对无序对(a,b)，有(a,b)=(b,a)。
定义设G =〈V,E〉是一个序偶，其中(1) V是非空集合(2) E⊆V&V，（E中元素可重复出现）则称G是一个无向图。
此时，称V为G的顶点集，记为V(G)，V中的元素称为G的顶点；称E为G的边集，记为E(G)，E中的元素称为G的无向边。
定义设D=〈V,E〉是一个序偶，其中(1) V是非空集合(2) E⊆V×V（E中元素可重复出现）则称G是有向图。
此时，称V为D的顶点集，记为V(D)，V中的元素称为D的顶点；称E为D的边集，记为E(D)，E中的元素称为D的有向边。
图的图示注①有时G既表示无向图又表示有向图，可统称为图。
②若V(G),E(G)均为有穷集，则称G为有限图。
对有限图G，称|V(G)| 为G的阶数。
③对e∈E(G)，称e出现的次数为e的重数，这些相同的边称为平行边（或重边）。
④当V(G)=∅时，称G为空图，记为∅。
⑤ 当E (G )= ∅时，称G 为零图，n 阶零图记为N n ；特别地，称N 1为平凡图。
⑥ 用u ,v ,v 1,v 2,"表示顶点，用e ,e 1,e 2,"表示边，称这样的图为标定图。
否则，称为非标定图。
⑦ 把无向图G =〈V ,E 〉的每条无向边确定一个方向后得到一个有向图D ，称D 为G 的定向图。
反之，去掉有向图D =〈V ,E 〉的每条有向边的方向后得到一个无向图G ，称G 为D 的基图。
⑧ 设G 是一个图，e ∈E (G )。
若e =(v i ,v j ) 或e =〈v i ,v j 〉，则称v i ,v j 为e 的端点，称v i ，v j 与e 是关联的。
当v i ≠v j 时，称e 与v i 或e 与v j 的关联次数为1；当v i =v j 时，称e 为环，e 与v i 的关联次数为2；对 (), ,l l i l j v V G v v v v ∈≠≠，称e 与v l 的关联次数为0。
图论是离散数学的一个分支，研究图的性质和图上的问题。
图是由结点和边组成的一种抽象数据结构，可以用来描述现实世界中的各种关系和连接。
本文将介绍一些图的基本概念和算法。
在图中，结点表示实体，边表示结点之间的关系。
一张图可以用G=(V, E)表示，其中V为结点的集合，E为边的集合。
边可以有方向（有向图）或没有方向（无向图），也可以有权重（带权图）或没有权重（不带权图）。
图的基本概念中，最常见的是路径和回路。
路径是图中的一条边的序列，每个边连接两个结点。
回路是一条路径，起点和终点相同。
如果一条路径中没有重复的结点，那么它就是一条简单路径。
连接结点之间的路径可以通过深度优先搜索（DFS）和广度优先搜索（BFS）来寻找。
DFS以栈为数据结构，先找到一个结点，然后再找它的邻居结点，如此往复，直到找到目标结点或者所有结点都被访问过。
BFS以队列为数据结构，先找到一个结点，然后找它的所有邻居结点，如此往复，直到找到目标结点或者所有结点都被访问过。
除了DFS和BFS，图中还有其他一些重要的算法和问题。
最短路径算法是用来找到两个结点之间最短路径的算法，其中最著名的是狄克斯特拉算法和弗洛伊德算法。
狄克斯特拉算法适用于没有负权边的图，通过不断更新起点到每个结点的最短距离来寻找最短路径。
弗洛伊德算法适用于任意有向图，通过不断更新任意两个结点之间的最短距离来寻找最短路径。
最小生成树算法是用来找到一个无环且连通的子图，该子图包含所有结点并且边的权重之和最小的算法。
其中最著名的是普里姆算法和克鲁斯卡尔算法。
普里姆算法从一个起始结点出发，每次选择与该结点最近的未访问结点，直到所有结点都被访问过。
克鲁斯卡尔算法一开始将每个结点都看作一个独立的树，然后每次选择权重最小的边，如果该边连接的两个结点不在同一棵树中，就将它们合并为一棵树。
图的基本概念和算法在离散数学中起到了至关重要的作用。
图论不仅仅可以用于计算机科学领域，还可以应用到物流规划、社交网络分析、电路设计等各个领域。
离散数学中的图论基础知识讲解图论是离散数学中的一个重要分支，研究的是图的性质和图中的关系。
图论在计算机科学、网络科学、运筹学等领域有着广泛的应用。
本文将从图的基本概念、图的表示方法、图的遍历算法以及一些常见的图论问题等方面进行讲解。
一、图的基本概念图是由顶点和边组成的一种数学结构。
顶点表示图中的元素，边表示元素之间的关系。
图可以分为有向图和无向图两种类型。
1. 无向图：无向图中的边没有方向，表示的是两个顶点之间的无序关系。
如果两个顶点之间存在一条边，那么它们之间是相邻的。
无向图可以用一个集合V表示顶点的集合，用一个集合E表示边的集合。
2. 有向图：有向图中的边有方向，表示的是两个顶点之间的有序关系。
如果从顶点A到顶点B存在一条有向边，那么A指向B。
有向图可以用一个集合V表示顶点的集合，用一个集合E表示有向边的集合。
二、图的表示方法图可以用多种方式进行表示，常见的有邻接矩阵和邻接表两种方法。
1. 邻接矩阵：邻接矩阵是一个二维数组，其中的元素表示两个顶点之间是否存在边。
如果顶点i和顶点j之间存在边，那么矩阵的第i行第j列的元素为1；否则为0。
邻接矩阵适用于表示稠密图，但对于稀疏图来说，会造成空间浪费。
2. 邻接表：邻接表是一种链表的数据结构，用来表示图中的顶点和边。
每个顶点对应一个链表，链表中存储与该顶点相邻的顶点。
邻接表适用于表示稀疏图，节省了存储空间。
三、图的遍历算法图的遍历是指按照某一规则访问图中的所有顶点。
常见的图的遍历算法有深度优先搜索（DFS）和广度优先搜索（BFS）。
1. 深度优先搜索：深度优先搜索是一种递归的搜索算法。
从某个顶点出发，首先访问该顶点，然后递归地访问与它相邻的未访问过的顶点，直到所有的顶点都被访问过。
2. 广度优先搜索：广度优先搜索是一种迭代的搜索算法。
从某个顶点出发，首先访问该顶点，然后依次访问与它相邻的所有未访问过的顶点，再依次访问与这些顶点相邻的未访问过的顶点，直到所有的顶点都被访问过。
