图与网络的基本概念

一、图与网络的基本概念

1.图的相关概念及其分类

引例 在一次聚会中有五位代表x1，x2，x3，x4，x5，其中x1与x2，x1与x5，x2与x5，x3与x4，x4与x5是朋友，则我们可以用一个带有五个顶点、五条边的图形来表示这五位代表之间的朋友关系（图9-3）：

设V（G）={v1，v2，…，vp}是一个非空有限集合，E（G）={e1，e2，…，eq}是与V（G）不相交的有限集合，一个图G是指一个有序二元组（V（G），E（G）），其中V（G）称为图G的顶点集，E（G）称为G的边集；.

如引例中五位代表之间的朋友关系可以用图G来表示，V（G）={x1，x2，x3，x4，x5}，E（G）={e1，e2，e3，e4，e5}，其中：e1=（x1，x2），e2=（x1，x5），e3=（x2，x5），e4=（x4，x5），e5=（x3，x4）.

两个端点重合的边称为环；两点之间多于一条边的，称为多重边；不含有环和多重边的图称为简单图.

任意两个顶点之间都有边相连的无向简单图称为完全图，有n个顶点的完全图.

图G=（V，E）的点集V可以分为两个非空子集X，Y，即：X∪Y=V，X∩Y=Ø，使得E中每一条边的两个端点必有一个端点属于X，另一个端点属于Y，则称G为二部图（偶图），记作G=（X，Y，E）.

2.顶点的次

以点v为端点的边数叫作顶点v的次（度），记作：deg（v）（d（v））.

例如上述引例图中：d（x1）=d（x4）=2，d（x5）=d（x2）=3，d（x3）=1.

定理1 任何图中顶点次数的总和等于边数的2倍.

推论1 任何图中，次为奇数的顶点必有偶数个.

证明：设V1和V2分别是图G的奇点与偶点集合，由定理1知必有下式成立

由于2m为偶数，而为若干偶数之和也是偶数，所以也为偶数，即是偶数.

3.子图

图G=（V，E）和图H=（V′，E′），若V′⊂V且E′⊂E，则称H是G的子图，记作H⊂G；当V′=V时，称H为G的生成子图.

例1 如图9-4中（b）为（a）的子图，（c）为（a）的生成子图.

4.网络

在实际问题中，只用图来描述所研究对象之间的关系还不行，与图联系在一起的，通常还有与点或边有关的某些参数指标，我们称之为“权”，权可以代表距离、费用、通过能力（容量）等.这种点或边带有某种数量指标的图称为网络.与无向图和有向图相对应，网络又分为无向网络和有向网络.

例2 图9-5（a），图9-5（b）是常见的网络例子.