Graph|Graph Theory 离散数学第五章 GraphTheory离散数学第五章

离散数学Ⅰ（图论）期末复习第一篇

写这个时的感想
第五章图的基本概念

5.1 有向图和无向图
5.2 通路、回路和图的连通性
5.3 图的矩阵表示
5.4 最短路径、关键路径和着色

写这个时的感想第一篇博客！！！
小激动！
深刻怀疑这些题目是要考的（判断与应用）；
唉，还有一些定理、结论性的东西（证明类）；
到时候再写罢……
【Graph|Graph Theory 离散数学第五章】基于老师的ppt和清华大学出版社的《离散数学（第五版）》
第五章图的基本概念 5.1 有向图和无向图

握手定理
- 求边，求点。
- 给一个度数列，判断其能不能构成一个图
子图
- 哪些是边导出子图，哪些是点导出子图
- 这是不是点导出子图，这是不是边导出子图
- 请画出某图的：
  生成子图（包含所有的顶点、边不一定有）
  子图（相比生成子图，点也不一定全有）
  点导出子图
  边导出子图
同构
- 这几幅图同构吗，为什么
  如果同构，记得要写出点、边的一一对应关系。
  如果不同构，要写出原因
- 记得图的数学表达（等考完前几场试我再补充）
- 补图
  请画出某图的补图

5.2 通路、回路和图的连通性

通路与回路
- 存在通路吗？写出来
  简单通路（所有边都不一样、点无所谓）
  复杂通路（有重复边出现）
  初级通路（所有边都不一样，所有点都不一样）
- 存在回路吗？写出来
  （如上）
连通
- 有多少个连通分支？
- 这个点集是不是点割集？
- 这个边集是不是边割集？
有向图当中
- 弱连通吗？
  看基图连不连通就好了
- 强连通吗？
  当且仅当图中存在经过每一个顶点至少一次的回路
- 单向连通吗？
  当且仅当图中存在经过每一个顶点至少一次的通路

5.3 图的矩阵表示

无向图的关联矩阵
- 怎么写
  行是边，列是点，mij是顶点vi和边ej的关联次数。
  关联次数有三种取值：
  0（vi与ej不关联）
  1（vi与ej关联一次）
  2（vi与ej关联两次，也就是ej是以vi为顶点的环！）
- 性质
  每一列恰好有两个1：每条边关联两个顶点
  每一列恰好有一个2：环关联的两个顶点重合
  第i行的元素之和：即vi的度数
  所有元素之和：边数的二倍（握手定理）
  vi是孤立点时：当且仅当第i行全部为0
  ej和ek是平行边时：第j列和第k列相同
（没有环的）有向图的关联矩阵
- 怎么写
  行是边，列是点
  但是！mij的取值和之前无向图的不太一样
  1 ：vi是ej的始点
  0 ：vi与ej不关联
  -1：vi是ej的终点
- 性质
  每一列恰好有一个+1和一个-1；
  每行中 +1 的个数：对应的点的出度
  每行中 -1 的个数：对应的点的入度
有向图的邻接矩阵（可以有环了！）
- 怎么写
  每行每列都代表了点。
  mij的取值：vi邻接到vj的边的条数
- 性质
  第i行的元素之和：vi的出度
  第j列的元素之和：vj的入度
  所有的元素之和 = 边数
  噢还有一个很重要的定理：
  Al中的元素aij是vi到vj长度为l的通路数
  Al中所有元素和是有向图中长度为l的通路（包括回路）的总数
  其中对角线上的元素和是图中长度为l的回路总数
  就……先不在这里证明了
有向图的可达矩阵
- 怎么写
  若vi可达vj，元素pij=1；反之，元素pij=0
- 性质
  对角线上元素都是1