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

图论导引

(【录播】图论导引1(45分钟) 【录播】图论导引2(43分钟) 免费试学 【录播】图论导引3(43分钟) 【录播】图论导引4(43分钟) 【录播】图论导引5(41分钟))

图论导引II

(【录播】图论导引6(44分钟) 【录播】图论导引7(43分钟) 【录播】图论导引8(45分钟) 【录播】图论导引9(45分钟) 【录播】图论导引10(44分钟))

二分图中的匹配

(【录播】二分图中的匹配1(44分钟) 【录播】二分图中的匹配2(46分钟) 【录播】二分图中的匹配3(43分钟) 【录播】二分图中的匹配4(45分钟) 【录播】二分图中的匹配5(43分钟))

二分图中的匹配II

(【录播】二分图中的匹配6(46分钟) 【录播】二分图中的匹配7(43分钟) 【录播】二分图中的匹配8(46分钟) 【录播】二分图中的匹配9(42分钟) 【录播】二分图中的匹配10(44分钟))

树

(【录播】树1(46分钟) 【录播】树2(45分钟) 【录播】树3(44分钟) 【录播】树4(46分钟) 【录播】树5(44分钟))

树II

(【录播】树6(41分钟) 【录播】树7(46分钟))

有向图及网络

(【录播】有向图及网络1(43分钟) 【录播】有向图及网络2(43分钟) 【录播】有向图及网络3(45分钟) 【录播】有向图及网络4(42分钟) 【录播】有向图及网络5(42分钟))

有向图及网络

(【录播】有向图及网络6(42分钟))

再论图

(【录播】再论图1(43分钟) 【录播】再论图2(44分钟) 【录播】再论图3(45分钟) 【录播】再论图4(44分钟) 【录播】再论图5(46分钟))

再论图II

(【录播】再论图6(46分钟) 【录播】再论图7(43分钟) 【录播】再论图8(43分钟) 【录播】再论图9(44分钟) 【录播】再论图10(44分钟))

再论图III

(【录播】再论图11(46分钟) 【录播】再论图12(45分钟) 【录播】再论图13(45分钟) 【录播】再论图14(45分钟) 【录播】再论图15(35分钟))

再论图IV

(【录播】再论图16(44分钟) 【录播】再论图17(44分钟) 【录播】再论图18(44分钟))

polya计数法

(【录播】polya计数法1(46分钟) 【录播】polya计数法2(43分钟) 【录播】polya计数法3(44分钟) 【录播】polya计数法4(42分钟) 【录播】polya计数法5(46分钟))

polya计数法II

(【录播】polya计数法6(44分钟) 【录播】polya计数法7(46分钟) 【录播】polya计数法8(42分钟) 【录播】polya计数法9(35分钟))

基本知识点： 
一、图的基本定义： 
平凡图：只有一个顶点无边的图。            非平凡图：其他所有图。 空图：边集合为空的图。 
简单图：既没有环也没有重边的图。            复合图：其他所有的图。 同构图：顶点集合之间存在双射（一一对应关系），对应边重数和端点对应相等。 
标定图：给图的点和边标上符号。           非标定图：不标号。非标定图代表一类相互同构的图。 
完全图：每两个不同顶点之间都有一条边相连的简单图。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是树的充要条件是当且仅当他的每条边均为割边。

免责声明：本站部分内容来自互联网收集整合，目的在于信息传递与分享，并不代表本网站观点，本站不为其版权负责。如侵犯了您的权益，请来电或致函告之，本站将及时给予删除等相关处理。