11.1 图模型、表示方法与度
第 10 章研究了树：既连通又不含环的结构。树其实是图（graph）的一种特殊情况。现在我们取消“无环”限制，让网络能够拥有备用路线、反馈回路和稠密连接。
本节先建立描述一般网络的语言，再学习用三种方式保存同一张图。
顶点与边
一张图是有序对
其中， 是非空有限顶点集， 是边集。顶点表示对象，边表示两个对象之间的关系。
在无向图中，边没有方向。顶点 与 之间的边是无序对
由于顺序不重要，。我们常把这条边简写为 ；若 与 之间有边，就写成 ，并称两者相邻。
例如，令
因为 ，所以 与 相邻；因为 ，所以 与 不相邻。
边 的两个端点是 和 。一条边与它的任一端点之间称为关联。
先说清楚图在表示什么
只有明确了对象与关系，图模型才有意义。假设四座火车站之间存在直达轨道，可以约定：
- 一个顶点表示一座车站；
- 一条无向边表示一段双向直达轨道；
- 没有边只表示“不直达”，不代表无法经过中间站到达。
同一个现实系统也能建立不同的图。如果顶点改为表示线路，那么边可以表示两条线路拥有换乘站。开始计算前，应先回答：
1. 一个顶点表示什么？
2. 一条边表示什么？
3. 关系是否有方向？
4. 一个对象能否与自己发生关系？
5. 两个对象之间能否存在多种关系？
6. 每条边是否需要记录成本、距离或容量等数字？
有向图、自环、平行边与权重
有些关系具有方向。有向图（directed graph）使用带方向的边，这种边也称为弧。从 指向 的弧是有序对
此时 与 不同。网页链接、单行道和先修关系都适合用有向图建模。
从一个顶点回到自身的边称为自环。端点完全相同的两条或更多条不同边称为平行边。允许平行边的图通常称为多重图。
既没有自环，也没有平行边的无向图称为简单无向图。除非另有说明，本章大多数定理都以简单无向图为对象。
带权图为每条边 附加数值 。权重可以表示距离、时间、成本、风险或容量。第 11.3 节会用权重寻找最短路径，第 11.4 节会用权重构造最小生成树。
这些特征解决的是不同问题：方向保存不对称关系，平行边保存多种独立关系，自环保存对象与自身的关系，权重记录数量。不能仅仅为了让图看起来更真实就随意加入它们。
根据现实需求搭建不同网络：选择关系是否有方向，添加或删除自环与平行连接，并观察模型检查器解释当前图保留了哪些信息、又丢失了哪些信息。
同一张图的三种表示
图形便于人观察，但算法需要精确的数据表示。下面始终使用同一个例子：
边表
边表把每条边保存一次：
它结构紧凑，适合第 11.4 节 Kruskal 算法那样需要扫描所有边的过程。但要判断某一条特定边是否存在，可能必须遍历整张表。
邻接表
邻接表为每个顶点保存与它相邻的顶点：
| 顶点 | 邻居 |
|---|---|
每条无向边会出现两次，分别记录在两个端点的邻接表中。当边数远小于最大可能边数时，图称为稀疏图；邻接表尤其适合保存稀疏图。
邻接矩阵
固定顶点顺序 。邻接矩阵是如下定义的 矩阵 ：
本例的矩阵为
无向图满足 ，所以矩阵关于主对角线对称。简单图没有自环，因此对角线元素都是 。在有向图中，第 行记录从顶点 出发的弧，所以矩阵不一定对称。
若 ，邻接矩阵总要使用 个位置，即使图中只有很少的边。它的优点是：只查看一个矩阵元素，就能回答“ 与 是否相邻”。
度表示局部连接数
顶点 的度记为 ，等于与 关联的边数。若允许自环，一条自环对度贡献 ，因为它的两个端点都落在同一顶点上。
在上面的例子中，
度为 的顶点称为孤立顶点，度为 的顶点称为悬挂顶点。在树中，悬挂顶点就是不指定根时的叶子。
两种邻接表示都能直接给出度：
- 在邻接表中， 就是顶点 的邻居个数；
- 在简单无向图的邻接矩阵中， 就是顶点 所在行的元素和。
握手定理
把有限无向图中所有顶点的度相加时，每条边会被计算两次，两个端点各一次。因此
这个恒等式称为握手定理。在本例中，
右侧一定是偶数，所以奇数度顶点的数量必定为偶数。若若干个奇数之和为偶数，其中奇数的个数只能是偶数。
图的平均度为
在有向图中，要分别计算进入与离开顶点的弧数。入度 统计终点为 的弧，出度 统计起点为 的弧。每条弧会对两种总和各贡献一次，因此
编辑邻接矩阵，实时观察边表、邻接表、图形、度序列与握手定理账本如何同步变化。切换到有向模式后，还能分别追踪入度与出度。
本节建立了什么
建立图模型时，首先要说明顶点和边的含义；方向、重复关系、自环和权重都应是有目的的选择。边表、邻接表和邻接矩阵以不同形式保存同一组关系，度则概括一个顶点拥有多少局部连接。
第 11.2 节不再只观察单条边，而会把相邻边连接成游走、路径和环，再用这些路线定义连通性。