图论基础知识点资格考试证券从业资格考试.pdf

《图论基础知识点资格考试证券从业资格考试.pdf》由会员分享，可在线阅读，更多相关《图论基础知识点资格考试证券从业资格考试.pdf（2页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、基本知识点：一、图的基本定义：平凡图：只有一个顶点无边的图。非平凡图：其他所有图。空图：边集合为空的图。简单图：既没有环也没有重边的图。复合图：其他所有的图。同构图：顶点集合之间存在双射（一一对应关系），对应边重数和端点对应相等。标定图：给图的点和边标上符号。非标定图：不标号。非标定图代表一类相互同构的图。完全图：每两个不同顶点之间都有一条边相连的简单图。N 个顶点的完全图只有一个，记为nK。偶图（二部图）：具有二分类(,)X Y的图，他的点集可以分解为两个（非空）子集 X和 Y，使得每条边的一个端点在 X中，另一个端点在 Y中。完全偶图：指具有二分类(,)X Y的简单偶图，其中 X的每个顶点

2、与 Y的每个顶点相连。若,Xm Yn，则这样额完全偶图记为：,m nK。k正则图：设(,)GV E为简单图，如果对所有的结点vV，有()d vk，称 G 为 k正则图。完全图和完全偶图,n nK 均是正则图。图划分：若一个 n 阶简单图 G 各点的度为id，则分正整数 k为 n 个部分的划分id称为是图划分。子图：边集合和点集合均是原图的子集，且待判定图中的边的重数不超过原图中对应的边的重数。生成子图：点集合相等，边集合为原图子集的图。导出子图：由顶点集为原图 G 真子集的所有点，及两端点均在该集合中的边的全体组成的子图 V。G V 和Gv。边导出子图：由原图 G 边的真子集，该图中边的断点全

3、体为顶点组成的子图 E。G E 和 Ge。图的运算：并，交，差，对称差，联图，积图，合成图，极图 路与图的联通性：途径：迹：边互不相同的途径。路：边和点都互不相同的途径。连通的：两个顶点之间存在路。连通图：每一对顶点之间都有一条路。连通分支：将 V划分为一些等价类12,.kV VV。两个顶点 u 和 v 是连通的当且仅当他们属于同一个子集iV，称子图()iG V为连通分支。闭的：一条途径如果有正的长，且起点和终点相同。回路：闭途径。圈：起点和内部顶点互不相同的闭迹。k圈、奇圈、偶圈 直径：联结 u 和 v 中长度最短的途径的长度称为 u 与 v 的距离。记为(,)d u v。()max(,)|

4、,d Gd u vu vV为图 G 的直径。赋权图：对图的每条边 e 赋以一个实数()e称为权。G 连同它边上的权称为赋权图。邻接矩阵：表示点与点之间的关系。nn n 为点数，m 为边数。关联矩阵：表示点与边之间的关系。nm 树的等价命题：1.连通无圈图。2.任意两顶点之间有且仅有一条路相连。3.G 是连通的，且1mn。4.G 中无圈，且1mn。5.G中无圈，任意两顶点之间增加一条边就得到唯一的一个圈。非平凡无向图 G 是树的充要条件是 G 为最小连通图。非平凡无向图 G 是树的充要条件是当且仅当他的每条边均为割边。环也没有重边的图复合图其他所有的图同构图顶点集合之间存在双射一一对应关系对应边重数和端点对应相等标定图给图的点和边标上符号非标定图不标号非标定图代表一类相互同构的图完全图每两个不同顶点之间都有一条边相连边的一个端点在中另一个端点在中完全偶图指具有二分类的简单偶图其中的每个顶点与的每个顶点相连若则这样额完全偶图记为正则图设为简单图如果对所有的结点有称为正则图完全图和完全偶图均是正则图图划分若一个阶简单图数不超过原图中对应的边的重数生成子图点集合相等边集合为原图子集的图导出子图由顶点集为原图真子集的所有点及两端点均在该集合中的边的全体成的子图和边导出子图由原图边的真子集该图中边的断点全体为顶点成的子图和