1. 图的引入
无序对和无序积
设 A, B 为任意集合, 称集合 A&B = {(a, b)|a ∈ A, b ∈ B} 为 A 与 B 的无序积,(a, b) 称为无序对.
与序偶不同, 对 ∀a, b,(a, b) = (b, a).
什么是图
一个图 (Graph) 是一个序偶 < V, E >，记为 G =< V, E >，其中：V = {v1, v2, · · · , vn} 是有限非空集合，vi 称为结点 (node)，V 称为结点集。
E 是有限集合，称为边集。E 中的每个元素都有 V 中的结点对与之对应，称之为边 (edge)。
与边对应的结点对即可以是无序的, 也可以是有序的.
若边 e 与无序结点对 (u, v) 相对应, 则称 e 为无向边(undirected edge), 记为 e =
(u, v) = (v, u), 这时称 u, v 是边 e 的两个端点.
若边 e 与有序结点对 < u, v > 相对应，则称 e 为有向边(directed edge)(或弧), 记为
e =< u, v >, 这时称 u 为 e 的始点 (或弧尾),v 为 e 的终点 (或弧头), 统称为 e 的端点
2. 图的表示
邻接矩阵
3. 图的分类
按边有无方向分类
每条边都是无向边的图称为无向图(undirected graph)；每条边都是有向边的图称为有向图(directed graph)；有些边是无向边，而另一些边是有向边的图称为混合图(mixed graph)。(混合图转化为有向图)
按有无平行边分类
多重图
按有无权值分类
赋权图(weighted graph)G 是一个三重组 < V, E, g > 或四重组 < V, E, f, g >，其中 V 是结点集合，E 是边的集合，f 是从 V 到非负实数集合的函数（即结点的权值函数），g 是从 E 到非负实数集合的函数（即边的权值函数）。相应的，边或结点均无权值的称为无权图
- 赋权图: 边有权值
- 赋权图: 边和结点都有权值
4. 子图和补图
设有图 G =< V, E > 和图 G1 =< V1, E1 >.
若 V1 ⊆ V，E1 ⊆ E，则称 G1 是 G 的子图(subgraph)，记为 G1 ⊆ G.
若 G1 ⊆ G，且 G1 ̸= G(即 V1 ⊂ V 或 E1 ⊂ E)，则称 G1 是 G 的真子图(propersubgraph)，记为 G1 ⊂ G.
若 V1 = V，E1 ⊆ E，则称 G1 是 G 的生成子图(spanning subgraph).
设 V2 ⊆ V 且 V2 ̸= ∅，以 V2 为结点集，以两个端点均在 V2 中的边的全体为边集的 G 的子图，称为 V2 导出的 G 的子图，简称 V2 的导出子(induced subgraph)
完全图
设 G =< V, E > 为一个具有 n 个结点的无向简单图，如果 G 中任意两个结点间都有边相连，则称 G 为无向完全图，简称 G 为完全图，记为 Kn。
设 G =< V, E > 为一个具有 n 个结点的有向简单图，如果 G 中任意两个结点间都有两条方向相反的有向边相连，则称 G 为有向完全图，在不发生误解的情况下，也记为 Kn。
补图
设 G =< V, E > 为简单图，G′ =< V, E1 > 为完全图，则称G1 =< V, E1 − E >为 G的补图(complement of graph)，记为G。
- 完全图-简单图
- 画补图时，边和原图是互补关系，但结点不变。尤其是孤立结点，一定不要漏掉！
5. 握手定理
邻接矩阵计算度数
握手定理
6. 图的同构
7. 通路和回路
通路数量的计算
8. 可达性与最短通路
可达性矩阵
短程线及距离
