图和子图思维导图

参考教材：邦迪《图论及其应用》，包含了简单图、图的同构、子图、顶点的度、路和连通、圈、最短路问题等内容。

ch1：图和子图

1. 简单图

简单图定义：既没有环也没有两边连接同一个顶点

平凡图：只有一个点的图

2. 图的同构

如果存在两个一一映射theta:V(G)-->V(H)和phi:E(G)-->E(H)，使得psi_G(e)=uv当且仅当psi_H(phi(e))=theta(u)theta(v)

完全图、空图、偶图

3. 关联矩阵、邻接矩阵

关联矩阵：点&边

邻接矩阵：点&点

4. 子图

定义：设有图G、H，若V(H)是V(G)子集，E(H)是E(G)子集，且psi_H是psi_G在E(H)上的限制，则H是G的子图

分类

真子图：H是G真子集

生成子图：满足V(H)=V(G)

导出子图

5. 顶点的度

定理1.1：SUM_{v in V}d(v)=2epsilon（所有度之和=总边数*2）

推论1.1：在任何图中，奇点个数为偶数

6. 路和连通

7. 圈

定理1.2：一个图是偶图当且仅当不包含奇圈

8. 最短路问题

边的权

Dijkstra算法

9. Sperner引理