【离散数学】要点（屈婉玲版）第五部分 图论

��       大一上学期学习离散数学（屈婉玲版，其他版本可能名词和定义上有些差别），想写个学习笔记，记录一下所学，希望以后忘了还能再想起来。（如果有错误，欢迎小伙伴指正哦）

第十四章 图的基本概念

几个概念（与后面相关知识联系密切）

1. 关联次数（度数）：点与相邻一般边的关联次数为1，与环的关联次数为2，与不相邻的边关联次数为0。
2. 简单图：无环无平行边。
3. 握手定理：①无向图中，所有顶点度数之和=2×边数   ②有向图中，所有顶点度数之和=2×边数，且入度=出度=边数

当给出一个图的度数序列时（爱出）

• 判断是否可图画：①度数之和为偶数②有奇数顶点，则要满足奇数顶点偶数个
• 判断是否可简单图画：①满足握手定理②△(G)≤n-1（只要有一步不满足就不可以，下面举个例子）③当有0时除去不看举个具体例子吧

   再来几个概念

  1. 完全图：任意两点都有边；无平行边无环。
  2. 真子图：点一定少了或边一定少了。
  3. 生成子图：点不变，边改变。
  4. 连通图：平凡图或任意两点都（直接或间接）连通的图。
  5. 点/边连通图：向下兼容性（如果是5-连通图则一定是1/2/3/4-连通图）。

  连通性（爱考）

  1. 弱连通：有向图的基图是连通图的。
  2. 单向连通：任意两点均可达（经历所有顶点的通路）。
  3. 强连通：任意两点均相互可达（经历所有顶点的回路）。

  ---

  矩阵（分个类，别记混喽爱出大题哦）

  • 关联矩阵M：点与边的关联度。（点与边，点为行，边为列）
  • 邻接矩阵A：点到点边的条数。（点与点，行点到列点的条数）
  • 可达矩阵P：可达为1，不可达为0。（点与点，对角线上元素都为1，因为自己到自己可达）

    第十五章 欧拉图和哈密顿图

    欧拉图（点可重复走）：是回路的才叫欧拉图，有欧拉通路而无欧拉回路的叫半欧拉图。

    • 有向：

      通路：2个奇度顶点，其中出度多的为起点，入度多的为终点。（单向连通&恰有2个奇度顶点）

      回路：每点入度=出度（强连通）。（强连通&每点出度＝入度）

      • 无向：

        通路：仅有两个奇度顶点。（连通图&恰有两个奇度顶点）

        回路：所有顶点的度都为偶数。（连通图&无奇度顶点）

        ---

        哈密顿图（点不可重复，环和平行边不影响哈密顿性）：哈密顿回路——>初级回路，哈密顿通路——>初级通路，有通路无回路叫半哈密顿图。

        哈密顿图的必要条件（哈密顿图所具有的性质）：p（G-V1）≤ 丨V1丨

        用处：破坏必要条件，证明其不是哈密顿图。

        半哈密顿图的必要条件：

        p（G-V1）≤ 丨V1丨+1

        其中，p（G-V1）指无向图G的连通分支数。

        哈密顿图的充分条件（具有该性质可推出是哈密顿图）：d(u)+d(v)≥n

        用处：复合充分条件，证明是哈密顿图。

        半哈密顿图的充分条件：d(u)+d(v)≥n-1

        其中，d和v是任意两个与G不相邻的两个顶点，n的前提是大于等于3。

        第十六章 树

        最大考点！！！最优二叉树！！！❤️‍

        最优二叉树可以得到最优前缀码。（用于数据的传输和储存）

        以书上P339为例：

         

        步骤：

        1.  按从小到大排序
        2. 最小的两个加起来，删掉两个最小的，将两数之和放到剩余的一堆数里面

        重复步骤1、2，直到比较结束，左边分叉的线上标1，右边分叉的线上标2（左零右一标记），最后就可以读出最佳前缀码了。注：如果有加起来的和比原本存在的数大的话可以另起一个叉叉，比如(a)中左侧的20比右侧的两个10大，那么右侧的两个10就可以另起一支叉叉。

        第十七章 平面图

        判断平面图（小题）：能把无向图G的边移动到无边相交（全凭自己画）。

        判断极大平面图（小题）：在简单平面图G上任意两个不相邻的顶点之间加一条边，所得的图为非平面图，则G是极大平面图（全凭自己画，考的较少）。

        离散数学结束喽