图和子图思维导图

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

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引理