图论笔记

图论知识点摘要：图论是数学的一个分支，它研究图的性质和应用。

图由节点（或顶点）和连接这些节点的边组成。

本文将概述图论的基本概念、类型、算法以及在各种领域的应用。

1. 基本概念1.1 节点和边图由一组节点（V）和一组边（E）组成，每条边连接两个节点。

边可以是有向的（指向一个方向）或无向的（双向连接）。

1.2 路径和环路径是节点的序列，其中每对连续节点由边连接。

环是一条起点和终点相同的路径。

1.3 度数节点的度数是与该节点相连的边的数量。

对于有向图，分为入度和出度。

1.4 子图子图是原图的一部分，包含原图的一些节点和连接这些节点的边。

2. 图的类型2.1 无向图和有向图无向图的边没有方向，有向图的每条边都有一个方向。

2.2 简单图和多重图简单图是没有多重边或自环的图。

多重图中，可以有多条边连接同一对节点。

2.3 连通图和非连通图在无向图中，如果从任意节点都可以到达其他所有节点，则称该图为连通的。

有向图的连通性称为强连通性。

2.4 树树是一种特殊的连通图，其中任意两个节点之间有且仅有一条路径。

3. 图的算法3.1 最短路径算法如Dijkstra算法和Bellman-Ford算法，用于在加权图中找到从单个源点到所有其他节点的最短路径。

3.2 最大流最小割定理Ford-Fulkerson算法用于解决网络流中的最大流问题。

3.3 匹配问题如匈牙利算法，用于解决二分图中的匹配问题。

4. 应用4.1 网络科学图论在网络科学中有广泛应用，如社交网络分析、互联网结构研究等。

4.2 运筹学在运筹学中，图论用于解决物流、交通网络优化等问题。

4.3 生物信息学在生物信息学中，图论用于分析蛋白质相互作用网络、基因调控网络等。

5. 结论图论是数学中一个非常重要和广泛应用的领域。

它不仅在理论上有着深刻的内涵，而且在实际应用中也发挥着关键作用。

随着科技的发展，图论在新的领域中的应用将会不断涌现。

本文提供了图论的基础知识点，包括概念、图的类型、算法和应用。

基本知识点：一、图的基本定义：平凡图：只有一个顶点无边的图。

非平凡图：其他所有图。

空图：边集合为空的图。

简单图：既没有环也没有重边的图。

复合图：其他所有的图。

同构图：顶点集合之间存在双射（一一对应关系），对应边重数和端点对应相等。

标定图：给图的点和边标上符号。

非标定图：不标号。

非标定图代表一类相互同构的图。

完全图：每两个不同顶点之间都有一条边相连的简单图。

N 个顶点的完全图只有一个，记为n K 。

偶图（二部图）：具有二分类(,)X Y 的图，他的点集可以分解为两个（非空）子集X 和Y ，使得每条边的一个端点在X 中，另一个端点在Y 中。

完全偶图 ：指具有二分类(,)X Y 的简单偶图，其中X 的每个顶点与Y 的每个顶点相连。

若,X m Y n ==，则这样额完全偶图记为：,m n K 。

k —正则图：设(,)G V E =为简单图，如果对所有的结点v V ∈，有()d v k =，称G 为k —正则图。

完全图和完全偶图,n n K 均是正则图。

图划分：若一个n 阶简单图G 各点的度为i d ，则分正整数k 为n 个部分的划分i d ∑称为是图划分。

子图：边集合和点集合均是原图的子集，且待判定图中的边的重数不超过原图中对应的边的重数。

生成子图：点集合相等，边集合为原图子集的图。

导出子图：由顶点集为原图G 真子集的所有点，及两端点均在该集合中的边的全体组成的子图V ‘。

'[]G V 和G v -。

边导出子图：由原图G 边的真子集，该图中边的断点全体为顶点组成的子图E ‘。

'[]G E 和{}G e -。

图的运算：并，交，差，对称差，联图，积图，合成图，极图路与图的联通性：途径：迹：边互不相同的途径。

路：边和点都互不相同的途径。

连通的：两个顶点之间存在路。

连通图：每一对顶点之间都有一条路。

连通分支：将V 划分为一些等价类12,,...k V V V 。

两个顶点u 和v 是连通的当且仅当他们属于同一个子集i V ，称子图()i G V 为连通分支。

离散数学图论（图、树）常考考点知识点总结图的定义和表示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 ）最小的二元树称为最优树。

图论学习笔记⽬录图的概念简史欧拉与⼽尼斯堡七桥问题等价问题：“欧拉⼀笔画”\(\equiv\)与任⼀个顶点相关联的边必须是偶数条。

图的基本概念图⽆向图邻接与关联邻接与关联：\((p,q)\)图另⼀种表⽰⽅法：(p,q)图图相等与特殊的图图相等、特殊的图（平凡图、零图）有向图疑惑：⽆向图是集合反⾃反、对称的关系。

有向图中为保证反⾃反性，去掉了⾃⾝到⾃⾝的有向线段\(\{(v,v)|v \in V\}\)。

但是，图是不允许存在⾃⾝到⾃⾝的边吗？答案：是的。

图的表⽰图解法与邻接矩阵法图解法与邻接矩阵法：问题：关系的闭包在图中的意义是什么？图模型利⽤图建模现实问题，并⽤图的理论加以解决的能⼒。

例⼦：结婚问题、地图与导航⼦图⼦图概念⽣成⼦图特例：⽣成⼦图记号：去除顶点u，去除边{u,v}尤其地，注意去除边的记号不是去除u、v两个顶点。

导出⼦图（1）顶点导出⼦图：若V1⊆V(G)，则以V1为顶点集，以两个顶点均在V1中的边集组成的图，称为图G的顶点导出⼦图，记为G(V1)。

例如：求G(V1)，V1 ={1,3,5}则G(V1)为（2）边的导出⼦图：若E1⊆E(G),则以E1为边集，以E1中所有边的顶点为顶点集组成的图，称为图G的边的导出⼦图，记为G(E1)。

例如：求G(E1)，E1 = {13,24,35}则G(E1)为度度的概念定理1——握⼿定理【定理1】握⼿定理证明：每⼀条边对度数总和的贡献为2（每⼀条边对应两个顶点），由于共有q个边，故度数总和为2q。

推论1：握过奇数次数⼿的⼈为偶数个。

证明：将⼈分为两类，握奇数次⼿\(V_1\)和握偶数次⼿\(V_2\)，那么，\(V_1\)与\(V_2\)中顶点的度数总和为偶数（2q），同时，\(V_2\)的度数之和必然为偶数，那么，\(V_1\)的度数之和必然为偶数（偶数-偶数=偶数），同时，由于\(V_1\)中均是握奇数次⼿（\(V_1\)中各顶点度均为奇数），那么，\(V_1\)中顶点数必为偶数个（偶数个奇数之和=偶数）。