【数理知识】第8章-图-《离散数学及其应用》Kenneth H. Rosen

第8章-图-《离散数学及其应用》Kenneth H. Rosen

• • 8.1 概述
  • • • 表 8-1
  • 8.2 图的术语
  • 8.3 图的表示和图的同构
  • • 8.3.3 邻接矩阵
    • 8.3.4 关联矩阵
    • 8.3.5 图的同构
    • • 定义1 同构 (isomorphism)
  • 8.4 连通性
  • • 8.4.4 有向图的连通性
    • • 强连通的
      • 弱连通的
      • 强连通分支
  • 8.5 欧拉通路与哈密顿通路
  • 8.6 最短通路问题
  • 8.7 可平面图
  • 8.8 图着色

8.1 概述

表 8-1

类型边允许多重边允许环

简单图	无向	否	否
多重图	无向	是	否
伪图	无向	是	是
有向图	有向	否	是
有向多重图	有向	是	是

8.2 图的术语

8.3 图的表示和图的同构

8.3.3 邻接矩阵

8.3.4 关联矩阵

8.3.5 图的同构

定义1 同构 (isomorphism)

设 $G_1=(V_1,E_1)$ 和 $G_2=(V_2,E_2)$ 是简单图，若存在一对一的和映上的从 $V_1$ 到 $V_2$ 的函数 $f$，且 $f$ 具有这样的性质：对 $V_1$ 里所有的 $a$ 和 $b$ 来说，$a$ 和 $b$ 在 $G_1$ 里相邻当且仅当 $f(a)$ 和 $f(b)$ 在 $G_2$ 里相邻，就说 $G_1$ 和 $G_2$ 是同构的。这样的函数 $f$ 称为同构。

8.4 连通性

8.4.4 有向图的连通性

强连通的

若每当 a 和 b 都是一个有向图的顶点时，就有从 a 到 b 和从 b 到 a 的通路，则该图是强连通的。

弱连通的

若在有向图的底图里，任何两个顶点之间都有通路，则该有向图是弱连通的。

强连通分支

有向图 G 的子图是强连通的而不包含在更大的强连通子图中，即极大强连通子图，可称之为 G 的强连通分支或强分支。

8.5 欧拉通路与哈密顿通路

8.6 最短通路问题

8.7 可平面图

8.8 图着色

总结

以上是生活随笔为你收集整理的【数理知识】第8章-图-《离散数学及其应用》Kenneth H. Rosen的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。