离散数学之图论的基本概念

基本概念"/>

离散数学之图论的基本概念

最近在上离散数学中的图论这一章，下面是我对图的一些重要概念的分类和总结。

描述关系的概念

• 关联——用于描述点与边的关系，简单来说就是这条边由那些点构成，就和那些点关联。而关联矩阵则就是一个记录点边关联次数的矩阵。

• 邻接，相邻——用于描述点与点的关系，形成一条边的两个点，我们称它们邻接。而邻接矩阵就是一个记录两点之间边数的矩阵。特别的：如果这条边是个环，也就是说它由一个点构成，只是始点和终点重合，那么我们称始点和终点相邻。

  如图：
  

关于图的一些概念

• 有向图:每条边都有方向的图
• 无向图：同理，每条边都没有方向的图
• 混合图：有些边无向，有些边有向的图
• 零图：仅含孤立结点组成的图（孤立结点是指：图中不与任何结点相邻接的点）
• 平凡图：仅含一个结点的零图
• （n，m）图：含有n个结点，m条边的图
• 多重图：含有平行边的图
• 线图：不含有平行边的图
• 简单图：不含环的线图（环的概念参照上图）
  （ps:图中的平行边和我们通常理解的平行边有所不同，图中的平行边是指，两个结点间有几条边，那这几条边就称为平行边，如果这个图有方向，则要求这几条边方向相同，才算平行边。详看下图）

• 正则图：各结点的度数相同的图称为正则图.各结点的度数均为k的图称为k次正则图。

• 完全图：简单来说，就是图中的任意点和其它的点都有边的图。数学语言的说法：设图G是n阶无向简单图（有向图概念类似），若G中的任何一个结点与其余n-1的结点相邻，则G为n阶的无向完全图，记作Kn.(以后在图中看见Kn，要记得这是完全图的表示方法，不要傻傻的kk)。
  

• 连通图，非连通图：若无向图G是平凡图或是G中任意两个顶点都是连通的，则称G是连通图；否则，称G是非连通图。

一些重要定理

1. 握手定理：所有顶点的度数之和等于边数的两倍
2. 任何图中，度数为奇数的顶点个数是偶数