Skip to content

Latest commit

 

History

History
385 lines (192 loc) · 10 KB

离散数学5 图论.md

File metadata and controls

385 lines (192 loc) · 10 KB

离散数学5 图论


[TOC]


第14章 图

图的基本概念

  • 无序积:

  • 无向图

  • 有向图

  • 图的表示:

  • :无向图和有向图统称为图。人们只关心点之间是否有连线,而不关心点的位置以及连线的曲直,这是图论中的图与集合中的图的本质区别。

  • 阶 n阶图

  • 零图 平凡图:

  • 空图:

  • 标定图,非标定图:

  • 基图:

关联、环、相邻、孤立点

  • 无向图的关联:

  • 有向图的关联:

  • 孤立点:

平行边、多重图、简单图

入度、出度、顶点的度数

握手定理

图的同构

无向简单图、 n阶无向完全图、n阶有向简单图、竞赛图、k-正则图

母图、子图

补图

删除边,删除顶点,加新边

图的连通性

通路与回路

通路与回路的主要性质

无向图的连通性

  • 连通

  • 连通分支

  • 短程线与距离

无向图的连通程度

  • 割点、割边

  • 点连通度

  • 边连通度

  • 性质

有向图的连通性

  • 顶点之间的可达关系

  • 短程线、距离

  • 弱连通图、强连通图

强连通图与单向连通图的判别定理

二部图

概念

判别

图的矩阵表示

无向图的关联矩阵

有向图的关联矩阵

有向图的邻接矩阵

定理

图的可达矩阵

图的运算

第15章 欧拉图与哈密顿图

欧拉图

哥尼斯堡七桥问题

欧拉图的判定

求欧拉回路

  • 逐步插入回路法
  • Fleury法

哈密顿图

周游世界问题

哈密顿图的判别

最短路问题

带权图

最短路径

Dijkstra算法

旅行商问题

第16章 树

无向树

生成树

最小生成树

Kruskal算法

根树

根树的分类

最优树

哈夫曼算法

最佳前缀编码

二叉树遍历

波兰符号法与逆波兰符号法

第17章 平面图

平面图概念

欧拉定理

平面图的判断

平面图的对偶图

对偶图性质

第18章 支配集、覆盖集、独立集、匹配与着色

支配集

独立集

覆盖集

边覆盖集

匹配

二部图中的匹配

完备匹配

着色

四色猜想与四色定理

点着色

地图着色

边着色