Graph|Graph Theory 离散数学第五章


离散数学Ⅰ(图论)期末复习第一篇

  • 写这个时的感想
  • 第五章 图的基本概念
    • 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
类似的,无向图也可以有邻接矩阵和可达矩阵!
即每一条无向边都可以看作一对方向相反的有向边
显然,无向图的邻接矩阵和可达矩阵都是对称的
5.4 最短路径、关键路径和着色 Dijkstra算法
项目网络图
着色

    推荐阅读