本帖子讨论图的基本概念，这一章，我们将利用有序对和二元关系的概念定义图。图分为了无向图和有向图，他们有共性也有区别，请大家注意体会，用联系和辩证的观点去认识。
1、无向图和有向图
注意无向图和有向图的表示，最大区别在于边的集合的表示，无向图中边集为无序集V&V的子集， 有向图中边集为有序集VXV的子集。
1）无向图
2）有向图
2、几类特殊的图
通常用 G表示无向图, D表示有向图,V(G)、 E(G)、V(D)、E(D)、分别是G和D的顶点集, 边集。
n 阶图: n个顶点的图
有限图: V, E都是有穷集合的图
零图: E=
空图: V=
平凡图： 一阶零图
简单图：既无平行边也无环的图.
n阶无向完全图Kn: 每个顶点都与其余顶点相邻的n阶无向简单图。边数m=n(n-1)/2, 出/入度=n-1
n阶有向完全图: 每对顶点之间均有两条方向相反的有向边的n阶有向简单图。边数m=n(n-1), D=d=2(n-1)。完全图举例如下：
补图：设G=<V,E>为n阶无向简单图，以V为顶点集,所有使G成为完全图Kn的添加边组成的集合为边集的图，称为G的补图
3、图的度数
1）无向图顶点的度数
2）有向图顶点的度数
3）图的度数列
4、握手定理
1）握手定理
任意无向图和有向图的所有顶点度数之和都等于边数的2倍, 并且有向图的所有顶点入度之和等于出度之和等于边数。
2）握手定理推论
在任何无向图和有向图中，奇度顶点的个数必为偶数.
3）应用
5、图的连通性
1）通路与回路
下面复杂的概念让人头晕，其实就是我们常规理解的能走的通的路，只不过是用数学语言表达出来了 ，将结点和与结点相邻的边连起来。
2）无向图的连通性
对于无向图中的任何两个结点都是有通路的，那么此图连通，即：
更进一步的，我们可以将连通关系，定义为等价关系，等价关系具有自反性，对称性，传递性。因为具有传递性必然连通。平凡图是一阶零图，它的关系矩阵表示，就是一个全1矩阵，因此也是连通图。
当我们对连通关系做等价划分的时候，有几个等价类，就有几个连通分支。
3）有向图的连通性
设有向图D=<V,E> ，u可达v: u到v有通路. 规定u到自身总是可达的，可达具有自反性和传递性。
有向图的连通性包括了三种：
- D弱连通(连通): 基图为无向连通图
- D单向连通: ，u可达v 或v可达u
- D强连通:，u与v相互可达
强连通单向连通弱连通
6、图的矩阵表示
图的矩阵表示，有三种方式：关联矩阵、邻接矩阵、可达矩阵。三者的区别在于，关联矩阵讨论的是顶点与边的关联次数、邻接矩阵讨论的是顶点之间的邻接边的条数、可达矩阵关注的是顶点之间是否可达，因此表达这些关系的矩阵尺寸是不同的，比如关注顶点与边之间的关系的矩阵，矩阵的行数就是顶点数，列数就是边数。
1）关联矩阵
2）邻接矩阵
3）可达矩阵
7、最短路径
我们把有向图的定义进行扩展，使得图不仅包含顶点集、边集、还包括边上的权值集合W，称为带权图。
给定两个顶点，我们用dijstra算法求解最短路径。dijstra算法是一种单源多目标的算法。
文章来源：https://www.toymoban.com/news/detail-483953.html
文章来源地址https://www.toymoban.com/news/detail-483953.html
到了这里，关于离散数学：图的基本概念的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
