图论 （全60讲）【理工学社】

基本知识点： 
一、图的基本定义： 
平凡图：只有一个顶点无边的图。            非平凡图：其他所有图。 空图：边集合为空的图。 
简单图：既没有环也没有重边的图。            复合图：其他所有的图。 同构图：顶点集合之间存在双射（一一对应关系），对应边重数和端点对应相等。 
标定图：给图的点和边标上符号。           非标定图：不标号。非标定图代表一类相互同构的图。 
完全图：每两个不同顶点之间都有一条边相连的简单图。N个顶点的完全图只有一个，记为
nK。 
偶图（二部图）：具有二分类(,)XY的图，他的点集可以分解为两个（非空）子集X和Y，使得每条边的一个端点在X中，另一个端点在Y中。 
完全偶图 ：指具有二分类(,)XY的简单偶图，其中X的每个顶点与Y的每个顶点相连。若
,XmYn，则这样额完全偶图记为：,mnK。 
k—正则图：设(,)GVE为简单图，如果对所有的结点vV，有()dvk，称G为k—正则图。 完全图和完全偶图,nnK 均是正则图。 
图划分：若一个n阶简单图G各点的度为id，则分正整数k为n个部分的划分id称为是图划分。 子图：边集合和点集合均是原图的子集，且待判定图中的边的重数不超过原图中对应的边的重数。 
生成子图：点集合相等，边集合为原图子集的图。 
导出子图：由顶点集为原图G真子集的所有点，及两端点均在该集合中的边的全体组成的
子图V‘
。 
'
[]GV 和Gv。 
 
边导出子图：由原图G边的真子集，该图中边的断点全体为顶点组成的子图E‘
。 
'
[]GE 和{}Ge。 
图的运算： 
并，交，差，对称差，联图，积图，合成图，极图  
路与图的联通性： 途径： 
迹：边互不相同的途径。 
路：边和点都互不相同的途径。 连通的：两个顶点之间存在路。 
连通图：每一对顶点之间都有一条路。 


连通分支：将V划分为一些等价类12,,...kVVV。两个顶点u和v是连通的当且仅当他们属于同一个子集iV，称子图()iGV为连通分支。 
闭的：一条途径如果有正的长，且起点和终点相同。 回路：闭途径。 
圈：起点和内部顶点互不相同的闭迹。k圈、奇圈、偶圈 
直径：联结u和v中长度最短的途径的长度称为u与v的距离。记为(,)duv。
()max{(,)|,}dGduvuvV为图G的直径。 
 
赋权图：对图的每条边e赋以一个实数()e称为权。G连同它边上的权称为赋权图。  
邻接矩阵：表示点与点之间的关系。nn  n为点数，m为边数。 关联矩阵：表示点与边之间的关系。nm  
树的等价命题：            1.连通无圈图。 
                          2.任意两顶点之间有且仅有一条路相连。                           3.G是连通的，且1mn。                           4.G中无圈，且1mn。                           5.G中无圈，任意两顶点之间增加一条边就得到唯一的一个圈。 非平凡无向图G是树的充要条件是G为最小连通图。          非平凡无向图G是树的充要条件是当且仅当他的每条边均为割边。

内容版权声明：除非注明，否则皆为本站转载文章。文章及图片版权归原作者所有，如有侵权请联系我们，我们立刻删除。