离散数学———第十四章 图的基本概念相关知识

一、基本概念

简单图：不含平行边也不含自环的图为简单图

多重图：含平行边的图为多重图

度数：顶点所含边数，记作d（G），

//以下为有向图才有的概念

出度：以该点为起点的边的数量，记作d+（G）

入度：以该点为终点的边的数量，记作d+（G）

例外：度数=出度+入度

最大度：顶点的最大度数，记作Δ（G）

最小度：顶点的最小度数，记作δ（G）

最大出度：顶点的最大出度数，记作Δ+（G）

最小出度：顶点的最小出度数：记作δ+（G）

最大入度：顶点的最大入度数：记作Δ-（G）

最小入度：顶点的最小入度数：记作δ-（G）

二、

握手定理：1.在任何无向图中，所有顶点的度数之和等于边数的2倍

2.在任何有向图中，所有顶点的度数之和等于边数的2倍；所有顶点的入度之和等于所有顶点的出度之和，都等于边数。

3.推论：任何图中，奇度顶点的个数是偶数。

可简单图化：给定一个非负整数序列{d1,d2,…dn}，若存在一个无向图使得图中各点的度与此序列一一对应，则称此序列可图化。进一步，若图为简单图，则称此序列可简单图化。

定理（常用）：非负整数列d=（d1,d2,…dn）是可图化的当且仅当（d1+d2+…+dn）为偶数

定理：设G为任意n阶无向图，则Δ（G）<=n-1。

三、连通性

割点与桥（割边）的定义 割点：无向连通图中，去掉一个顶点及和它相邻的所有边，该图不连通，则该顶点称为割点。 桥（割边）：无向联通图中，去掉一条边，该图不连通，则这条边，称为桥或者割边。

点连通度：点割集所含割点最小数

边连通度：边割集所含桥最小数