人们在日常的生活和工作中，经常会遇到各种各样的图，但运筹学中所研究的图是一个抽象的数学概念。为了从感性上认识图以及理解图的概念，先讨论几个例子。

例9.1　18世纪东欧有个叫哥尼斯堡的城镇，小镇风景独特，有条河，人们称之为雷普格尔河，从镇中穿流而过。该河中有两个岛，河上有七座桥把河的两岸和河中的两个岛连接起来，如图9.1所示。当时该城镇居民热衷于一个问题，即一个人能否从某地出发，一次把七座桥不重复的都走过一遍，最后又回到原地。于是数学家欧拉用A、B、C、D四个点分别表示河两岸和河中的两个岛，每座桥用连接相应两点的一条边表示，这样就把图9.1化为图9.2的形式。基于图9.2的分析，欧拉给出了否定答案，这就是著名的哥尼斯堡七桥问题，同时欧拉在1736年发表了图论方面的第一篇论文。

图9.1

图9.2

例9.2　某大学创新协会共有7名同学，这7名同学中有的已经认识，有的还不认识。为了明确表明这7名同学之间的认识关系，现在用图9.3进行描述，其中v1、v2、v3、v4、v5、v6、v7分别表示7名同学，用边表示他们是否认识。通过图9.3就能弄清他们之间的认识关系，例如v1和v2之间的边表示这两名同学是认识的，而v3和v4之间没有边，则说明这两名同学是不认识的。

图9.3

例9.3　假设图9.4是我国某地区几座城市之间的高速公路交通示意图，它反映了这几座城市之间高速公路的连接情况，其中点代表城市，点与点之间的边代表两座城市之间的高速公路。

图9.4

由以上三个例子可以看出，一般的图都具有两个要素，即点和边。把现实问题抽象为图的方法是，用点表示现实中的对象，用边表示对象和对象之间的关系，若对象和对象之间有关系，则用边把表示对象的点连接起来，直观的描述如图9.5所示：

图9.5(www.daowen.com)

自然语言的描述是，图是由表示具体事物的对象（顶点）集合和表示事物之间的关系（边）集合组成，例如针对铁路网，边表示区段，顶点表示区段间的车站；针对城市道路网，边表示道路，顶点表示交叉口。

如果用G表示图，用vi表示点，用V表示所有点的集合，用ei表示边，用E表示所有边的集合，那么图的数学语言描述就是

G=(V,E)

其中V=(v1,v2,…,vn)，E=(e1,e2,…,em)。另外，图G的顶点集合与边集合也可分别用V(G)和E(G)表示。

根据边有没有方向，将图分为无向图、有向图和混合图。所有边都是无向边的图称为无向图，所有边都是有向边的图称为有向图，既有有向边又有无向边的图一般称为混合图。鉴于混合图的复杂现象，本教材不考虑混合图的相关问题。

根据无向图的定义，无向图的数学语言描述为：存在图G=(V,E)，其中V是一个有n个顶点的非空集合，即V=(v1,v2,…,vn)，E是一个有m条边的非空集合，即E=(e1,e2,…,em)，若E中任意一条边e是V的无序元素对(vi,vj)，其中i≠j，即可以有(vi,vj)=(vj,vi)，则称图G为无向图，如图9.6所示。

根据有向图的定义，有向图的数学语言描述为：存在图G=(V,E)，其中V是一个有n个顶点的非空集合，即V=(v1,v2,…,vn)，E是一个有m条边的非空集合，即E=(e1,e2,…,em)，若E中任意一条边e是V的有序元素对(vi,vj)，其中i≠j，即(vi,vj)≠(vj,vi)，则称图G为有向图，如图9.7所示。

如果把无向边用元素对表示，那么边(vi,vj)和边(vj,vi)是同一条边，vi和vj称为该无向边的端点，其中无向边与端点（顶点）vi和vj相关联，顶点vi和vj相邻，如图9.6中的边（v2,v4）和(v4,v2)属于同一条边，顶点v2和v4为该无向边的端点。

图9.6

如果把有向边用元素对表示，那么边(vi,vj)和边(vj,vi)就不是同一条边，针对边(vi,vj)来说，顶点vi称为该有向边的起点，顶点vj称为该有向边的终点；但针对边(vj,vi)来说，顶点vj为该有向边的起点，顶点vi为该有向边的终点，如图9.7中有向边(v2,v4)和(v4,v2)就不是同一条边，顶点v2和v4为边(v2,v4)的起点和终点，但为边(v4,v2)的终点和起点。

图9.7