图论基础和树

这是一篇关于图论基础和树的思维导图，内容有图的相关概念、图的矩阵表示（邻接矩阵、权值矩阵）、树（数的概念及性质）。

图论基础和树

• 图的相关概念
  • 图的定义
    • 相邻节点
    • 关联
    • 相邻边
  • 图的相关概念
    • 节点，边
    • 有向图，无向图
    • 有权图
      • 节点可代表交换局，权值可为造价或容量
      • 边可代表链路，全职可为长度，造价
    • 自环，重边
    • 节点与边的组合关系
      • 边序列，链
      • 径，回路
  • 图的连通性
    • 连通图，环路，子图，真子图，生成子图和最大连通子图
  • 割
    • 割端和割端集
      • 割端，不可分割图，割端集，最小割端集
    • 割边和割边集
      • 割边，割边集，割集，最小割集
• 图的矩阵表示
  • 邻接矩阵
    • 由节点与节点之间的关系确定的矩阵
  • 权值矩阵
    • 无向简单图，有向简单图
• 2.2 树
  • 数的概念及性质
    • 定义
      • 任何两节点间有且只有一条径的图成为树
      • 树干的边成为树枝
      • 若树枝的两个节点都至少与两条边关联，则称该树枝为树干
      • 若树枝的一个节点仅与此边关联，则称该树枝为树尖，并称该节点为树叶
      • 若指定树中的一个点为根，则称该树为有根树
    • 性质
      • 树是无环的连通图，但增加一条边便可以得到一个环。任何两节点间有径的图一定是连通图，而只有一条径就不能有环。
      • 树是最小的连通图，即去掉树中的任何一条边就成为非连通图，从而丧失了连通性，所以是最小的连通图。
      • 若树有m条边及n个节点，则有m=n-1，即有n个节点的树共有n-1个树枝。
      • 除了单点树之外，任何一棵树中至少有两片树叶