离散数学大概（三）

1. 最基本的计数法则

• 加法法则
  设事件A有m种产生方式，事件B有n种产生方式，当A和B产生的方式不重叠时，事件A或B有m+n种产生方式
• 乘法法则
  设事件A有m种产生方式，事件B有n种产生方式，当A和B产生的方式彼此独立时，事件A与B有mn种产生方式

2. 不定方程x1+x2+...+xt=n的非负整数解的个数为C(n+t-1, n)，其实为多重集{n·1，(t-1)·0}的全排列
3. 图

• 顶点数叫做图的阶，n个顶点的图称为n阶图
• 一条边也没有叫做零图，1阶零图称为平凡图，平凡图只有1个顶点
• 顶点集为空集的图叫做空图
• 将有向图的各条有向边改成无向边后得到的无向图称为这个有向图的基图
• 图中没有边关联的顶点叫做孤立点
• 多重图与简单图
  在无向图中，如果关联一对顶点的无向边多余1条，则称这些边为平行边，平行边的条数称为重数。
  在有向图中，如果关联一对顶点的有向边多余1条，并且这些边的方向相同，则称这些边为平行边。
  含平行边的图称为多重图，既不含平行边也不含环（vi=vj对应的一条边）的图称为简单图。

4. 度数与边数
   握手定理：在任何无向图中，所有顶点的度数之和等于边数的2倍。
   在任何有向图中，所有顶点的度数之和等于边数的2倍；所有顶点的入度之和等于所有顶点的出度之和，都等于边数。
5. 非负整数列d=(d1,d2,...,dn)是可图化的当且仅当sum(d)即所有度数之和为偶数
6. 完全图

• 设G是n阶无向简单图，若G中每个顶点均与其余n-1个顶点相邻，则称G为n阶无向完全图，简称n阶完全图，记作Kn(n>=1).
• 设D是n阶有向简单图，若D中每个顶点都邻接到其余n-1个顶点，则称D是n阶有向完全图.
• 设D是n阶有向简单图，若D的基图是n阶无向完全图Kn，则称D是n阶竞赛图.
• n阶无向完全图，n阶有向完全图，n阶竞赛图的边数分别为n(n-1)/2，n(n-1)，n(n-1)/2.

7. k-正则图
   设G是n阶无向简单图，若G中任意一个顶点的度都为k，则称G为k-正则图.
8. 图的同构
   至今还没找到判断两个图是否同构的便于检查的充要条件。显然阶数相同、边数相同、度数列相同等等都是必要条件。
9. 生成子图
   如果一个图的顶点集合和边集合都是另一个图的子集，则该图为另一个图的子图。如果子图的顶点集合等于母图的顶点集合，则称该子图为生成子图。
10. 补图
    设G是n阶无向简单图，G的补图的顶点集合与G相同，不过边集合为G的边集合的补。如果G和G的补图同构，则称G为自补图。
11. 通路与回路

• 设G是无向标定图，G中顶点与边的交替序列称为通路
• 若通路中始点和终点相同，则称为回路
• 若通路中所有边各异，则称为简单通路
• 若通路中所有顶点各异（除了始点和终点可能相同外），所有边也各异，则称为初级通路或路径
• 若路径中始点和终点相同，则称为初级回路或圈

12. 连通性
    若无向图G是平凡图或G中任何两个顶点都是连通的，则称G为连通图，否则称为非连通图。
13. 可达
    设D是一个有向图，若任意两个顶点Vi，Vj之间存在通路，则称Vi可达Vj；

• 若有向图D的基图是连通图，则称D是弱连通图
• 若有向图D中任意两个顶点Vi，Vj，存在Vi可达Vj或者Vj可达Vi，则称D为单向连通图
• 若有向图D中任意两个顶点之间相互可达，则称D为强连通图

14. 定理
    有向图D是强连通图当且仅当D中存在经过每个顶点至少一次的回路
    有向图D是单向连通图当且仅当D中存在经过每个顶点至少一次的通路
15. 二部图

• 若无向图G的顶点集V可划分为V1和V2（V1∪V2=V，V1∩V2=∅，
  V1≠∅，V2≠∅），使得G中的每条边的两个端点都是一个属于V1，一个属于V2，则称G为二部图（二分图），常将二部图记为<V1，V2，E>.
• 若G是简单二部图，V1中每个顶点均与V2中所有顶点相邻，则称G为完全二部图.
• n(n≥2)阶零图都是二部图
• n(n≥2)阶无向图G是二部图当且仅当G中无奇圈（长度为奇数的圈）

16. 关联矩阵和邻接矩阵
    无向图的关联矩阵mij记录的是顶点vi与边ej的关联次数（度）
    有向图的邻接矩阵aij记录的是顶点vi邻接到顶点vj的有向边的条数
17. 欧拉图

• 通过图（有向图或无向图）中所有边一次且仅一次遍历所有顶点的通路称为欧拉通路
• 通过图中所有边一次且仅一次遍历所有顶点的回路称为欧拉回路，具有欧拉回路的图称为欧拉图。规定平凡图是欧拉图。
• 具有欧拉通路而无欧拉回路的图称为半欧拉图。
• 无向图G是欧拉图当且仅当G是连通图且没有奇度顶点。
• 无向图G是半欧拉图当且仅当G是连通的且恰有两个奇度顶点。
• 有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度等于出度
• 有向图D是半欧拉图当且仅当D是单向连通的且恰有两个奇度顶点，其中一个顶点的入度比出度大1，另一个顶点的出度比入度大1，而其余顶点的入度等于出度
• G是非平凡的欧拉图当且仅当G是连通的且是若干个边不重的圈的并

18. 哈密顿图

• 经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路。
• 经过图中所有顶点一次且仅一次的回路称为哈密顿回路，具有哈密顿回路的图称为哈密顿图。规定平凡图是哈密顿图
• 具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图
  与判断一个图是否是欧拉图不同，目前人们还没有找到便于判断哈密顿图的充要条件
• 设G是n阶无向简单图，若对于G中任意不相邻的两个顶点u，v，均有
  d(u) + d(v) ≥ n-1
  则G中存在哈密顿通路（充分条件）
• 设G是n（n≥3）阶无向简单图，若对于G中任意不相邻的两个顶点u，v，均有
  d(u) + d(v) ≥ n
  则G中存在哈密顿通路（充分条件）
• n（n≥2）阶竞赛图中都有哈密顿通路