图论基础知识点

loading 分享 2026-11-20 下载文档

基本知识点:

一、图的基本定义:

平凡图:只有一个顶点无边的图。 非平凡图:其他所有图。 空图:边集合为空的图。

简单图:既没有环也没有重边的图。 复合图:其他所有的图。 同构图:顶点集合之间存在双射(一一对应关系),对应边重数和端点对应相等。

标定图:给图的点和边标上符号。 非标定图:不标号。非标定图代表一类相互同构的图。

完全图:每两个不同顶点之间都有一条边相连的简单图。N个顶点的完全图只有一个,记为

Kn。

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

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

X?m,Y?n,则这样额完全偶图记为:Km,n。

k—正则图:设G?(V,E)为简单图,如果对所有的结点v?V,有d(v)?k,称G为k—正则图。 完全图和完全偶图Kn,n 均是正则图。

图划分:若一个n阶简单图G各点的度为di,则分正整数k为n个部分的划分?di称为是图划分。 子图:边集合和点集合均是原图的子集,且待判定图中的边的重数不超过原图中对应的边的重数。

生成子图:点集合相等,边集合为原图子集的图。

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

‘

子图V。

G[V] 和G?v。

'

‘

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

G[E] 和G?{e}。

'图的运算:

并,交,差,对称差,联图,积图,合成图,极图

路与图的联通性: 途径:

迹:边互不相同的途径。

路:边和点都互不相同的途径。 连通的:两个顶点之间存在路。

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

连通分支:将V划分为一些等价类V1,V2,...Vk。两个顶点u和v是连通的当且仅当他们属于同一个子集Vi,称子图G(Vi)为连通分支。

闭的:一条途径如果有正的长,且起点和终点相同。 回路:闭途径。

圈:起点和内部顶点互不相同的闭迹。k圈、奇圈、偶圈

直径:联结u和v中长度最短的途径的长度称为u与v的距离。记为d(u,v)。

d(G)?max{d(u,v)|u,v?V}为图G的直径。

赋权图:对图的每条边e赋以一个实数?(e)称为权。G连同它边上的权称为赋权图。

邻接矩阵:表示点与点之间的关系。n?n n为点数,m为边数。 关联矩阵:表示点与边之间的关系。n?m

树的等价命题: 1.连通无圈图。

2.任意两顶点之间有且仅有一条路相连。 3.G是连通的,且m?n?1。 4.G中无圈,且m?n?1。 5.G中无圈,任意两顶点之间增加一条边就得到唯一的一个圈。 非平凡无向图G是树的充要条件是G为最小连通图。 非平凡无向图G是树的充要条件是当且仅当他的每条边均为割边。


图论基础知识点.doc 将本文的Word文档下载到电脑
搜索更多关于: 图论基础知识点 的文档
相关推荐
相关阅读