Chap14 图

核心知识点

顶点集V、边集E

基图

有向边改为无向边

握手定理

所有顶点度数之和等于边数的2倍

可图化

定理：度数序列可图化 当且仅当 度数和为偶数

图的同构

存在双射函数，映射后相同（在空间上移动点及其关联边）

k-正则图

每个顶点的度数均为k的无向简单图

生成子图

子图的顶点集等于母图的顶点集

关联矩阵、邻接矩阵、可达矩阵

二部图（二分图、偶图）

一般知识点

导出子图

补图（相对于完全图）

自补图：G与其补图同构

连通分支（连通分量）

极大连通子图

满足三个特点：极大；连通；子图

点割集、割点、边割集、割边

图的运算

参考书籍：离散数学（第2版）--屈婉婷、耿素云、张立昂