复旦大学：《离散数学》课程教学讲义（图论）图论应用、图论算法

8.1图论简介 一、案例

 内容1：图的定义  内容2：图的应用  内容3：图的表示  内容4：图的同构

• 欧拉图 • 哈密顿图 • 最短路问题与货郎担问题

第一节 图 第二节 通路、回路、图的连通性 第三节 图的矩阵表示和运算

欧拉图 哈密顿图 二部图与匹配 平面图 着色

§4.1 Euler 图 §4.2中国邮递员问题（Chinese Postman Problem） §4.3Hamilton 图 §4.4 旅行商问题(Travelling Salesman Problem,TSP)

图论的基本概念 一、 图 的 概 念 1、图的定义 2、顶点的次数 3、子图 二、 图 的 矩 阵 表 示 1、 关联矩阵 2、 邻接矩阵

 一、握手定理的应用  二、平面图、欧拉公式的应用  三、图的基本概念与应用  四、欧拉图和哈密顿图  五、图的着色

图的基本概念 欧拉图与哈密顿图 树 平面图 支配集、覆盖集、独立集、匹配与着色 第一节 图 第二节 通路、回路、图的连通性 第三节 图的矩阵表示和运算