画布 1
树🌲
  基本概念
    树:不含简单回路的连通图
    森林:每个连通分支都是树的无向图;
    树叶v:d(v)=1;
    分枝点v: d(v)>=2;
    平凡树: 平凡图,既无树叶,也无分支点;
  无向树的基本概念
    设G=<V,E>为n阶m条边的无向图
    (1) G是树(连通无回路);
    (2) G中任二顶点之间存在唯一路径;
    (3) G中任二顶点之间存在唯一路径;
    (4) G连通且m=n-1;
    (5) G连通且每条边均为桥;
    (6) G无圈,但在任二不同顶点之间增加新边,所得图含唯一的一个圈;
    证明显然:1->2->3...->6
    无向树的性质
      定理9.2 任一n阶非平凡无向树至少有两片树叶.
        习题九:6
          例 设G为n(n≥5)阶简单图,证明G或G的补图中必含圈.
  生成树
    生成树T:T是G的生成子图,且T为树
      prim算法(破圈法)
      克鲁斯卡尔算法
    定理9.4: 设T是无向连通图G中一棵生成树,e是T的 任意一条弦,不同的弦对应的圈是不同的.
    基本回路
        基本回路的秩为 m-n+1
    基本割集
        基本割集的秩为 n-1
    生成树的个数
      G是n阶无向连通标定图(V={v1, v2, ..., vn}),则对于G的任意非环边均有
      t(G)= t(G-e)+ t(G\e)
  环路空间
        可以理解成 00->8->0
    定理 9.9,环路系统就是
  断集空间
      割集是断集,断集不一定是割集
  根树
    哈夫曼编码--会了