2.1.1 图的定义与类型_生物计算-QQ阅读历史男生网

上QQ阅读APP看书，第一时间看更新

2.1.1 图的定义与类型

用表示非空集的所有-元子集构成的集族，。基于此，给出图的定义：设是一个非空集，，则把有序对称为一个图，记作，并将称为的顶点集，称为的边集；中的元素称为的顶点，中的元素称为的边。对于给定图，有时也用和分别表示的顶点集和边集。设，通常用来代替，并称顶点与顶点相邻，称顶点（或）与边（相互）关联。设，或表示图中所有与顶点相邻的顶点构成的集合，称为的邻域集。如果图中的两条边、与同一个顶点关联，则称它们相邻。设，如果中的任意两个顶点均不相邻，则称是的一个独立集。类似地，设，若中的任意两条边均不相邻，则称是的匹配，或称是的一个边独立集。

注2.1　由于集合中元素不允许重复，因此与中均无重复的元素，且为无序2元子集构成的集族。这就意味着：①中没有重复的边；②中的每条边中的两个关联顶点不同；③。满足上述3点的图又称简单无向图。

若与中元素的数量均有限，则称为有限图，否则称为无限图。本书提到的图皆为有限图。通常，称为的阶，为的规模，并把具有个顶点、条边的图称为(n,m)-图。

图可在平面上用一个几何图形来表示：顶点用一个小圆点（称为点）表示，若顶点与相邻，则在与之间连接一条线。这种将画在平面上的方法称为的图解。用图解表示图，能更直观、清晰地展示图的结构，有助于理解图的性质，这也是图论的魅力所在。

设是一个阶简单图，。若，则称为阶完全图，记作；图2.1（a）（b）所示为的两种不同的图解。完全图的特征是：每对顶点均相邻。与完全图恰恰相反的是：若中每对顶点均不相邻，即，则称为阶空图，又称阶零图，记作，在不考虑顶点数时，通常称为空图或零图。

图若满足且，则称为长路或路，记作，图2.1（c）所示为的一种图解；若，，则称为-圈，记作。图2.1（d）所示为的一种图解。

　　　（a）　　　　　　　　　　　　　　　　　　　　　（b）　　　　　　　　　　　　　　　　　　　　　（c）　　　　　　　　　　　　　　　　　　　　　（d）

图2.1　、和的图解

（a）的第一种图解　（b）的第二种图解　（c）的一种图解　（d）的一种图解

注2.2　对于一个图的图解，我们不关心顶点和边的几何特征，即顶点的大小、形状、空心还是实心，以及边的长短、粗细、曲直等。

例2.1　设是简单图，其中，，则此图为著名的彼得松图（Peterson Graph），如图2.2（a）所示。图2.2（b）（c）所示为该图的两种图解。

若对中每个顶点标名称，则称为标定图，否则称为非标定图。图2.2（a）所示为标定图，图2.2（b）（c）所示均为非标定图。

　　　　　（a）　　　　　　　　　　　　　　　　　　　　　　　　　　（b）　　　　　　　　　　　　　　　　　　　　　　　　　　（c）

图2.2　彼得松图及图解

（a）彼得松图（b）彼得松图的图解之一（c）彼得松图的图解之二

在简单图的定义中，边集中的元素是互不相同的，即边互不相同。如果去掉这个限制，即允许有相同元素，会导致图G中一对顶点之间可能有（i＞1）条边，称为-重边。具有重边的图称为重图。更详细的论述如下。

将扩展成一个允许含重复元素[2]的新集族，记作。有序对称为一个重图，记作，其中；重复出现的元素称为重边。

[2]中的元素在中出现任意次。

例2.2　设，其中，，，，，，，则是重图。图2.3（a）所示为它的一种图解。

重图的基础图是一个基于的简单图，记作：顶点集，且中任意一对顶点相邻当且仅当该对顶点在中至少有一条边相连。重图的基础图，其中，，如图2.3（b）所示；图2.3（c）所示为它的一个图解。

　　　　　（a）　　　　　　　　　　　　　　　　　　　　　　　　　　　（b）　　　　　　　　　　　　　　　　　　　　　　　　　　　（c）

图 2.3　重图的一种图解，基础图及它的边赋权图

（a）重图的一种图解（b）的基础图（c）的边赋权图

在简单图与重图的定义中，任意边所关联的两个顶点不同，即。如果去掉这个限制，即一条边所关联的两个顶点相同，则这种边称为图的自环，且含有自环的图称为伪图。确切地讲，在简单图或重图中，可将（或）扩展为允许含中一个或多个元素[3]的新集族（记作），这时有序对称为一个伪图，记作。其中，，元素称为自环，。

[3]中的元素在中出现任意次。

例2.3　图是一个伪图，其中，。在中，与均为自环，如图2.4所示。

图2.4　一个含自环的图

注2.3　在重图中，边集必含重边；在伪图中，边集E_O必含自环。

在重图中，如果把关联同一对顶点的边的数量标于该边在基础图中对应的边上，则相当于给边赋权值。例如，对于图2.3（a）所示的重图，按边的重数定义各边的赋权w分别为、、、，则边赋权图如图2.3（c）所示。更一般地，边赋权图G可表示为一个三元有序组，其中(V, E)是一个简单图。令，则为赋权向量，（）为边的权值。按此定义，在图2.3（c）所示的边赋权图中，。

边赋权图的应用场景较多，如交通网络和生物神经网络。在交通网络中，顶点表示城市，边表示两个城市之间的公路、铁路、飞行航线或航海线等，边的权值则表示两个城市之间的距离（包括公路距离、铁路距离、飞行距离和航海距离等）。在生物神经网络中，顶点表示生物体（如人）的神经元，边表示两个神经元之间的突触，边的权值表示对应突触的厚度。人脑约有个神经元，以及～个突触，但关于突触厚度的研究相对较少，这方面的深入研究对脑科学的研究至关重要。