电子科大 图论复习 公式汇总

title: 图论期末考试复习

date: 2020-08-17 09:01:09
tags:

参考文献：《图论及其应用》 高等教育出版社 张先迪 李正良
仅作为复习参考使用，请参考教材内容中的公式可能有误。

文章目录

• • title: 图论期末考试复习 date: 2020-08-17 09:01:09 tags:

• 引言部分

  • 第1章 图论基础
  • 第1节 图的概念及其基本性质

    • 第1小节 同构图分析

      • 分析过程及案例研究
        • 练习题考察重点：第29至30页练习题编号为3、4、5、6]

    • 完全图偶图与补图

    • • • 定理1：若n阶图G是自补图，则有：n\%4 = 0 or 1

• 节点的次数与图的度序列

• • • 定理2 握手定理 在图G= (V, E)中所有节点次数之和等于边数m的两倍
      即：

\sum_{v \in V} \deg(v) = 2m

• 图的度序列及其特征

  • 定理3 非负整数组(d₁, d₂, …, dₙ)作为图G的度序列的一个充要条件是该组数列中各数值之和具有偶性。