离散数学5 图论
第14章 图
图的基本概念
图
-
无序积：
-
无向图：
-
有向图：
-
图的表示：
-
图 ：无向图和有向图统称为图。人们只关心点之间是否有连线，而不关心点的位置以及连线的曲直，这是图论中的图与集合中的图的本质区别。
-
阶 n阶图：
-
零图 平凡图：
-
空图：
-
标定图，非标定图：
-
基图：
关联、环、相邻、孤立点
-
无向图的关联：
-
有向图的关联：
-
孤立点：
平行边、多重图、简单图
入度、出度、顶点的度数
握手定理
图的同构
无向简单图、 n阶无向完全图、n阶有向简单图、竞赛图、k-正则图
母图、子图
补图
删除边，删除顶点，加新边
图的连通性
通路与回路
通路与回路的主要性质
无向图的连通性
-
连通
-
连通分支
-
短程线与距离
无向图的连通程度
-
割点、割边
-
点连通度
-
边连通度
- 性质
有向图的连通性
-
顶点之间的可达关系
-
短程线、距离
-
弱连通图、强连通图
强连通图与单向连通图的判别定理
二部图
概念
判别
图的矩阵表示
无向图的关联矩阵
有向图的关联矩阵
有向图的邻接矩阵
定理
图的可达矩阵
图的运算
第15章 欧拉图与哈密顿图
欧拉图
哥尼斯堡七桥问题
欧拉图的判定
求欧拉回路
- 逐步插入回路法
- Fleury法
哈密顿图
周游世界问题
哈密顿图的判别
最短路问题
带权图
最短路径
Dijkstra算法
旅行商问题
第16章 树
无向树
生成树
最小生成树
Kruskal算法
根树
根树的分类
最优树
哈夫曼算法
最佳前缀编码
二叉树遍历
波兰符号法与逆波兰符号法
第17章 平面图
平面图概念
欧拉定理
平面图的判断
平面图的对偶图
对偶图性质
第18章 支配集、覆盖集、独立集、匹配与着色
支配集
独立集
覆盖集
边覆盖集
匹配
二部图中的匹配
着色
四色猜想与四色定理
点着色
地图着色
边着色
