图-离散数学

一、图的基本概念

1.图的定义

由顶点构成的集合，称为顶点集 V 。

由顶点构成的 无方向的无序对 (v1, v2) 或 有方向的有序对 <v1, v2> 称为边 e 。由边构成的集合，称为边集 E 。

由 V E 构成的二元组 <V, E> 就是图，无向图称为 G ，有向图称为 D 。

一些图的叫法：

• 有 n 个点为n阶图/有向图。
• 无边，叫零图。
• 无点，叫空图。
• 将有向图的边去掉方向的无向图，是有向图的基图。

2.点和边的定义

无向图中：

点与边关联后，点称作边的端点。

两个点关联于一条边，则这两个点是相邻的。点v的所有相邻点的集合为v的领域。

两条边的有一个公共端点，则这两条是相邻的。

有向图中：

ei = <vi, vj> vi是边ei的始点，vj是终点。

两个点，vi邻接到vj，vj邻接于vi。

环与平行边

自己连到(包括有向、无向)自己的边为环。相同的边(两点相同、有向图中还要方向相同)为平行边。

3.度

无向图中，以v点为端点的边(即与v点相连的边)的条数，为v的度数，称作d(v)。

后话

鉴于离散数学课程成绩惨不忍睹，就不在此献丑了。