离散数学图论（图、树）常考考点知识点总结图的定义和表示1.图：一个图是一个序偶＜V , E ＞，记为G =< V ，E >，其中：① V ={V1,V2,V3,…, Vn}是有限非空集合，Vi 称为结点，V 称为节点集② E 是有限集合，称为边集，E中的每个元素都有V中的结点对与之对应，称之为边③与边对应的结点对既可以是无序的，也可以是有序的表示方法集合表示法，邻接矩阵法2.邻接矩阵：零图的邻接矩阵全零图中不与任何结点相邻接的结点称为孤立结点，两个端点相同的边称为环或者自回路3.零图：仅有孤立节点组成的图4.平凡图：仅含一个节点的零图无向图和有向图5.无向图：每条边都是无向边的图有向图：每条边都是有向边的图6.多重图：含有平行边的图(无向图中，两结点之间包括结点自身之间的几条边；有向图中同方向的边)7.线图：非多重图8.重数：平行边的条数9..简单图：无环的线图10.子图，真子图，导出子图，生成子图，补图子图：边和结点都是原图的子集，则称该图为原图的子图真子图（该图为原图的子图，但是不跟原图相等）11.生成子图：顶点集跟原图相等，边集是原图的子集12.导出子图：顶点集是原图的子集，边集是由顶点集在原图中构成的所有边构成的图完全图（任何两个节点之间都有边）13.完全图：完全图的邻接矩阵主对角线的元素全为0，其余元素都是114.补图：完全图简单图15.自补图：G与G的补图同构，则称自补图16.正则图：无向图G=<V,E>,如果每个顶点的度数都是k，则图G称作k-正则图17.结点的度数利用邻接矩阵求度数：18.握手定理：图中结点度数的总和等于边数的两倍推论：度数为奇数的结点个数为偶数有向图中，所有结点的入度=出度=边数19.图的度数序列：出度序列+入度序列20.图的同构：通俗来说就是两个图的顶点和边之间有双射关系，并且每条边对应的重数相同（也就是可任意挪动结点的位置，其他皆不变）21.图的连通性及判定条件可达性：对节点vi 和vj 之间存在通路，则称vi 和vj 之间是可达的22.无向图的连通性：图中每两个顶点之间都是互相可达的23..强连通图：有向图G 的任意两个顶点之间是相互可达的判定条件：G 中存在一条经过所有节点至少一次的回路24.单向连通图：有向图G 中任意两个顶点之间至少有一个节点到另一个节点之间是可达的判定条件：有向图G 中存在一条路经过所有节点25.弱连通图：有向图除去方向后的无向图是连通的判定条件：有向图邻接矩阵与转置矩阵的并是全一的矩阵26.点割：设无向图G=<V,E>为联通图，对任意的顶点w  V,若删除w及与w相关联的所有边后，无向图不再联通，则w称为割点；27.点割集：设无向图G=<V,E>为连通图，若存在点集 ，当删除 中所有顶点及与V1顶点相关联的所有边后，图G不再是联通的；而删除了V1的任何真子集 及与V2中顶点先关的所有边后，所得的子图仍是连通图，则称V1是G的一个点割集设无向图G=<V,E>为连通图，任意边e  E,若删除e后无向图不再联通，则称e 为割边，也成为桥28.边割集：欧拉图，哈密顿图，偶图（二分图），平面图29.欧拉通路（回路）：图G 是连通图，并且存在一条经过所有边一次且仅一次的通路（回路）称为拉通路（回路）30.欧拉图：存在欧拉通路和回路的图31.半欧拉图：有通路但没有欧拉回路32.欧拉通路判定：图G 是连通的，并且有且仅有零个或者两个奇度数的节点欧拉回路判定：图G 是连通的，并且所有节点的度数均为偶数有向欧拉图判定：图G 是连通的，并且所有节点的出度等于入度33.哈顿密图：图G 中存在一条回路，经过所有点一次且仅一次34..偶图：图G 中的顶点集被分成两部分子集V1,V2，其中V1nV2= o ,V1UV2= V ，并且图G 中任意一条边的两个端点都是一个在V1中，一个在V2中35.平面图：如果把无向图G 中的点和边画在平面上，不存在任何两条边有不在端点处的交叉点，则称图G 是平面图，否则是非平面图36.图的分类树无向树和有向树无向树：连通而不含回路的无向图称为无向树生成树：图G 的某个生成子图是树有向树：一个有向图，略去所有有向边的方向所得到的无向图是一棵树最小生成树最小生成树：设G -< V . E 是连通赋权图，T 是G 的一个生成树，T 的每个树枝所赋权值之和称为T 的权，记为W ( T . G 中具有最小权的生成树称为G 的最小生成树最优树（哈夫曼树）设有一棵二元树，若对所有的树叶赋以权值w1,w2… wn ，则称之为赋权二元树，若权为wi 的叶的层数为L ( wi )，则称W ( T )= EWixL ( wi ）为该赋权二元树的权，W ）最小的二元树称为最优树。
离散数学图论整理总结第⼋章图论8.1 图的基本概念8.1.1 图定义8.1―1 ⼀个图G 是⼀个三重组〈V (G ),E (G ),ΦG 〉,其中V (G )是⼀个⾮空的结点(或叫顶点)集合,E (G )是边的集合,ΦG 是从边集E 到结点偶对集合上的函数。
⼀个图可以⽤⼀个图形表⽰。
定义中的结点偶对可以是有序的,也可以是⽆序的。
若边e 所对应的偶对〈a ,b 〉是有序的,则称e 是有向边。
有向边简称弧,a 叫弧e 的始点,b 叫弧e 的终点,统称为e 的端点。
称e 是关联于结点a 和b 的,结点a 和结点b 是邻接的。
若边e 所对应的偶对(a ,b )是⽆序的,则称e 是⽆向边。
⽆向边简称棱,除⽆始点和终点的术语外,其它术语与有向边相同每⼀条边都是有向边的图称为有向图。
每⼀条边都是⽆向边的图称为⽆向图。
有向图和⽆向图也可互相转化。
例如,把⽆向图中每⼀条边都看作两条⽅向不同的有向边,这时⽆向图就成为有向图。
⼜如,把有向图中每条有向边都看作⽆向边,就得到⽆向图。
这个⽆向图习惯上叫做该有向图的底图。
在图中,不与任何结点邻接的结点称为弧⽴结点。
全由孤⽴结点构成的图称为零图。
关联于同⼀结点的⼀条边称为⾃回路。
在有向图中,两结点间(包括结点⾃⾝间)若同始点和同终点的边多于⼀条,则这⼏条边称为平⾏边。
在⽆向图中,两结点间(包括结点⾃⾝间)若多于⼀条边,则称这⼏条边为平⾏边。
两结点a 、b 间互相平⾏的边的条数称为边［a ,b ］的重数。
仅有⼀条时重数为1,⽆边时重数为0。
定义8.1―2 含有平⾏边的图称为多重图。
⾮多重图称为线图。
⽆⾃回路的线图称为简单图。
仅有⼀个结点的简单图称为平凡图。
定义 8.1―3 赋权图G 是⼀个三重组〈V ,E ,g 〉或四重组〈V ,E ,f ,g 〉,其中V 是结点集合, E 是边的集合,f 是定义在V 上的函数,g 是定义在E 上的函数。
8.1.2 结点的次数定义 8.1―4 在有向图中,对于任何结点v ,以v 为始点的边的条数称为结点v 的引出次数(或出度),记为deg +(v );以v 为终点的边的条数称为结点v 的引⼊次数(或⼊度),记为deg -(v );结点v 的引出次数和引⼊次数之和称为结点v 的次数(或度数),记作deg (v )。
离散数学中常用的图论算法简介图论是高等数学中的一个分支，主要涉及在图中寻找什么样的路径，以及什么样的点之间有什么样的关系。
在计算机科学中，图论的应用越来越广泛。
因为所有的计算机程序都是基于数据结构的，而图是一种最基本的数据结构之一。
离散数学中的图论算法大致可以分为两类：一类是针对稠密图的算法，另一类是针对稀疏图的算法。
稠密图指的是一种图，其中每对顶点都有一条边相连，而稀疏图则是指只有一部分顶点之间相连的图。
以下是一些常见的图论算法的简介。
1. Dijkstra算法Dijkstra算法是一种用于求图中最短路径的算法，也是最常用的图论算法之一。
Dijkstra算法的主要思想是通过贪心策略，从起点出发，逐步扩展最短路径的范围，直到找到终点。
Dijkstra算法可以用来解决单源最短路径问题。
如果图中有n个顶点，算法的时间复杂度为O（n²）。
2. Kruskal算法Kruskal算法是一种用于求最小生成树的算法。
最小生成树指的是，通过连接图中一些顶点形成一棵树，使得这些顶点之间的总权重最小。
Kruskal算法的主要思想是将图中的所有边按照权重进行排序，然后依次加入到生成树中，如果新加入的边会形成环，则不将其加入到生成树中。
如果图中有n个顶点，那么算法的时间复杂度为O（nlogn）。
3. Floyd算法Floyd算法用于求图中任意两个点之间的最短路径。
如果图中所有的权重都是正的，那么Floyd算法的时间复杂度为O（n的三次方），但是如果存在负权重，那么该算法不适用。
关于负权环的处理，可以通过Bellman-Ford算法进行解决。
4. Prim算法Prim算法是一种用于求最小生成树的算法。
与Kruskal算法不同的是，Prim算法是基于顶点集来实现，而不是基于边集。
Prim 算法首先找到一个起点，将其加入到生成树中，然后找到与其相连的边中权重最小的那一条，将其相连的顶点加入到生成树中，重复这一步骤直至所有顶点都被加入到生成树中。
