第 10 章 图
# 第 10 章 图
# 10.1 图和图的模型
#
图的定义
图的分类
- 简单图
- 每条边都连接两个不同的顶点且没有两条不同的边连接一对相同顶点的图称为简单图
示例
- 多重图
- 可能会有多重边连接同一对顶点的图称为多重图
- 当有
条不同的边与相同的无序顶点对相关联时, 我们也说 是一条多重度为 的边 示例
- 伪图
- 包含环或存在多重边连接同一对顶点或同一个顶点的图, 称为伪图
示例
#
有向图的定义
-
- 在计算机网络中, 有些链接只可以对一个方向操作(这种边称为单工线路),要建立这样一个图模型, 则很有必要给这些边赋予方向
有向图的分类
- 简单有向图
- 当一个有向图不包含环和多重有向边时, 就称为简单有向图
- 多重有向图
- 从一个顶点指向第二个(也许是同一个)顶点有多重有向边的有向图称为多重有向图
- 当
条有向边中的每一条都与顶点有序对 相关联时, 我们称 是一条多重度为 的边 示例
- 混合图
- 既包含有向边又包含无向边的图称为混合图
图术语
- 图的术语没有规范化,描述图的术语可能区别很大, 但是以下三个问题能够帮助我们理解图的结构
- 图的边是有向的还是无向的(还是两者皆有)?
- 如果是无向图, 是否存在连接相同顶点对的多重边?如果是有向图, 是否存在多重有向边?
- 是否存在环?
# 10.1.1 图模型
# 社交网络
# 10.2 图的术语和几种特殊的图
# 10.2.1 引言
# 10.2.2 基本术语
# 10.2.3 一些特殊的简单图
# 10.2.4 二分图
# 10.2.5 二分图和匹配
# 10.3 图的表示和图的同构
# 10.3.1 引言
# 10.3.2 图的表示
# 10.3.3 邻接矩阵
# 10.3.4 关联矩阵
# 10.3.5 图的同构
# 10.3.6 判定两个图是否同构
# 10.4 连通性
# 10.4.1 引言
# 10.4.2 通路
# 10.4.3 无向图的连通性
# 10.4.4 图是如何连通的
# 10.4.5 有向图的连通性
# 10.4.6 通路与同构
# 10.4.7 计算顶点之间的通路数
# 10.5 欧拉通路与哈密顿通路
# 10.5.1 引言
# 10.5.2 欧拉通路与欧拉回路
# 10.5.3 哈密顿通路和哈密顿回路
# 10.5.4 哈密顿回路的应用
# 10.6 最短通路问题
# 10.6.1 引言
# 10.6.2 最短通路算法
# 10.6.3 旅行商问题
# 10.7 平面图
# 10.7.1 引言
# 10.7.2 欧拉公式
# 10.7.3 库拉图斯基定理
# 10.8 图着色
# 10.8.1 引言
# 10.8.2 图着色的应用
编辑 (opens new window)