第十章 图

离散数学第十章 图论思维导图，总结了图的术语和几种特殊的图、图的表示和图的同构、欧拉通路和哈密顿通路等详细知识点。

第十章 图

• 图和图模型 G=(V,E)
  • 顶点的非空集V和边集E
  • 简单图：每条边都连接两个不同的顶点且 没有两条不同的边连接一对相同顶点的图
  • 伪图：包含环或存在多重边连接同一对顶点 或同一个顶点的图
  • 有向图
    • 简单有向图：不包含环和多重有向边
    • 有向多重图
  • 混合图：既包含有向边又包含无向边的图
  • 图模型：社交网络、通信网络、软件设计应用生态网、语义网络、锦标赛
• 图的术语和几种特殊的图
  • 邻接
  • 顶点v的所有相邻顶点的集合记作N(v)，称为顶点v的邻居
  • 顶点的度deg(v)，环为顶点的度做双倍贡献
    • 出度=入度=边数
    • 度=出度+入度=边数*2
    • 握手定理：设G=(V,E)是有m条边的无向图，则2m=∑deg(v)
  • 无向图有偶数个度为奇数的顶点
  • 完全图：Kn
    • 没有割点、不可分割图
  • 圈图：Cn
  • 轮图：Wn
  • n立方体图：Qn
  • 完全二分图：Km,n
    • 匹配
      • 最大匹配不一定是完美匹配，如果存在完美匹配那么完美匹配一定是最大匹配
      • 如果一个图的某个匹配中所有顶点都是匹配点，那么它是一个完美匹配
  • 从旧图构造新图
    • 子图
    • 导出的子图
• 图的表示和图的同构
  • 邻接表
  • 邻接矩阵
  • 关联矩阵
  • 图的同构
• 连通性
  • 通路
  • 连通分支
  • 点连通性
    • 点连通度：点割集中最小的顶点数，记作k(G)
      • 0<=k(G)<=n-1
      • k(G)越大，G的连通性越好
  • 边连通性
    • 边连通度：边割集中的最小边数，记作λ(G)
      • 0<=λ(G)<=n-1
      • k(G)<=λ(G)<=min deg(v)
  • 强连通
    • 在有向图G中，如果对于每一对vi、vj，vi≠vj， 从vi到vj和从vj到vi都存在路径，则称G是强连通图
  • 弱连通
    • 若在有向图的基本无向图中，任何两个顶点之间都有通路，则该有向图是弱连通的
  • 计算顶点之间的通路数
    • 可以利用邻接矩阵来确定
• 欧拉通路和哈密顿通路
  • 欧拉图
    • 欧拉通路
      • 如果存在一条通路包含此图中所有的边， 则该通路成为欧拉通路，也称欧拉路径（一笔画）
        • 连通多重图具有欧拉通路但无欧拉回路 当且仅当它恰有2个度为奇数的顶点
    • 欧拉回路
      • 如果欧拉路径是一条回路，那么称它为欧拉回路
        • 每个顶点必有偶度数
        • G是若干个边不相交的圈的并
  • 哈密顿图
    • 哈密顿通路
      • 设G=<V,E>为一图（无向图或有向图）.G中经过每个顶点 一次且仅一次的通路称作哈密顿通路
    • 哈密顿回路
      • 在一个图中通过图的每个顶点恰好一次且仅一次， 并最终回到起始顶点的闭合回路
        • 带有度为1的顶点的图没有哈密顿回路
        • 若图中有度为2的顶点，则关联这个顶点的 两条边属于任意一条哈密顿回路
        • 当n>=3时，Kn有哈密顿回路
        • 狄拉克定理：如果 G 是有 n 个顶点的简单图，其中 n ≥3， 并且 G 中每个顶点的度都至少为 n /2，则 G 有哈密顿回路。
        • 欧尔定理：如果 G 是有 n 个顶点的简单图，其中 n ≥3， 并且对于 G 中每一对不相邻的顶点 u 和 v 来说，都有 deg ( u )+ deg ( v )≥ n ，则 G 有哈密顿回路
• 最短通路问题
  • 加权图
  • 迪克斯特拉算法
• 平面图
  • 若可以在平面中画出一个图而边没有任何交叉（其中边的交叉 是表示边的直线或弧线在它们的公共端点以外的地方相交）， 则这个图是平面图。这种画法称为这个图的平面表示。
  • 欧拉公式：设 G 是带 e 条边和 v 个顶点的连通平面简单图。 设 r 是 G 的平面图表示中的面数。则 r = e - v +2。
  • 推论1 若 G 是 e 条边和 v 个顶点的连通平面简单图，其中 v ≥3，则 e ≤3v-6。 推论2 若 G 是连通平面简单图，则 G 中有度数不超过5的顶点。 推论3 若连通平面简单图有 e 条边和 v 个顶点， v ≥3并且没有长度为3的回路，则 e ≤2v-4.
  • 库拉图斯基定理
    • 若一个图是平面图，则通过删除一条边｛ u , o }并且添加一个新顶点 w 和两条边 ｛ u , w ）与( w , v ）获得的任何图也是平面图。这样的操作称为初等细分。 若可以从相同的图通过一系列初等细分来获得图 G =( V , E ）和图G2=(V2,E2)， 则称它们是同胚的。
    • 定理二 一个图是非平面图当且仅当它包含一个同胚于 K3,3 或 K5 的子图。
• 图着色
  • 四色定理 平面图的着色数χ(G)不超过4