图论基础知识点

基本知识点：

一、图的基本定义：

平凡图：只有一个顶点无边的图。 非平凡图：其他所有图。word/media/image1.gif

空图：边集合为空的图。

简单图：既没有环也没有重边的图。 复合图：其他所有的图。word/media/image2.gif

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

标定图：给图的点和边标上符号。 非标定图：不标号。非标定图代表一类相互同构的图。word/media/image3.gif

完全图：每两个不同顶点之间都有一条边相连的简单图。N个顶点的完全图只有一个，记为word/media/image4.gif。

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

完全偶图 ：指具有二分类word/media/image5.gif的简单偶图，其中X的每个顶点与Y的每个顶点相连。若word/media/image6.gif，则这样额完全偶图记为：word/media/image7.gif。

k—正则图：设word/media/image8.gif为简单图，如果对所有的结点word/media/image9.gif，有word/media/image10.gif，称G为k—正则图。 完全图和完全偶图word/media/image11.gif均是正则图。

图划分：若一个n阶简单图G各点的度为word/media/image12.gif，则分正整数k为n个部分的划分word/media/image13.gif称为是图划分。

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

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

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

word/media/image14.gif和word/media/image15.gif。 word/media/image16.gif

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

word/media/image17.gif和word/media/image18.gif。

图的运算：

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

路与图的联通性：

途径：

迹：边互不相同的途径。

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

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

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

连通分支：将V划分为一些等价类word/media/image19.gif。两个顶点u和v是连通的当且仅当他们属于同一个子集word/media/image20.gif，称子图word/media/image21.gif为连通分支。

闭的：一条途径如果有正的长，且起点和终点相同。

回路：闭途径。

圈：起点和内部顶点互不相同的闭迹。word/media/image22.gif圈、奇圈、偶圈

本文来源：https://www.2haoxitong.net/k/doc/8ef6ff5ae518964bcf847c29.html