文档介绍：§ 图与子图
1、图与网络
无向图(简称为图):一个有序二元组, 记为,其中,称为的点集合,称为的边集合,并且是一个无序的二元组,记为,称边连接点和,点和为边的端点。
例如:,边集合

圈:两个端点重合为一点的边()
孤立点:不与任何边关联的点()
关联:一条边的端点称为这条边的关联,反之一条边称为与它的端点关联

邻接:与同一条边关联的端点称为是邻接的,同时如果两条边有一个公共端点,则称这两条边是邻接的

有限图:点和边都是有限集合的图

空图:没有任何边的图

平凡图:只有一个点的图

简单图:既没有圈也没有两条边连接同一对点的图(即没有圈,并且任何两个点之间最多有一条边)
(a)是一简单图,(b)不是简单图。
设是一个简单图,若则
完全图:每一对点之间均有一条边相连的简单图,具有个点的完全图记为。显然有条边。
二分图:存在的一个二分划,使得的每条边有一个端点在中,另一个端点在中,记为。(a)

完全二分图:中的每个点与中的每个点都相连的简单二分图。(b)
简单图的补图: 与G有相同顶点集合的简单图,且中的两个点相邻当且仅当它们在G中不相邻。(a)和(b)就是互补的两个图。
有向图(简称为图):一个有序二元组, 记为,其中,称为的点集合,称为的弧集合,并且是一个有序的二元组,记为,称弧从点连向,点称为弧的尾,点称为弧的头。称为的先辈,称为的后继。例如:。
类似地,可以定义简单有向图、完全有向图、二分有向图和有向图的补图等概念。
有向图的基本图:对于的每条弧用一条边代替后得到的无向图
设是一个简单有向图,若则若是一个完全有向图,则有条弧。
(有向)网络:对(有向)图的每条边(弧)都赋予一个实数,并称为边(弧)的权,则连同它边(弧)上的权称为(有向)网络。, 记为(),其中。
2、关联矩阵和邻接矩阵
简单图的关联矩阵:一个阶矩阵,其中

简单有向图的关联矩阵:一个阶矩阵,其中

简单图的邻接矩阵:一个阶矩阵
,其中

注:简单图的邻接矩阵一定是方阵,并且是对称的。
简单有向图的邻接矩阵:一个阶矩阵
,