第2章　图论简介

图论是一门应用十分广泛的数学分支，应用图论解决运筹学、物理、化学、生物、计算机科学、网络理论、信息论、控制论、社会科学以及管理科学方面的问题都有其独特的优越性。图论与数学的其他分支如群论、矩阵论、概率论、拓扑、数值分析、组合数学等都有着密切的关系。事实上，图为任何一个包含一种二元关系的系统提供了一种数学模型。

众所周知，图论起源于一个非常经典的问题——哥尼斯堡七桥问题（见图2-1）。普莱格尔河流经哥尼斯堡小城，河中有两个小岛，在四块陆地之间修建了七座小桥，将河中间的两个岛和河岸联结起来。是不是可能存在路径，使得人们可以走遍四个地区，而且把每座桥走一次并且只走一次?这在图论中称为“欧拉图”问题。

图2-1　七桥问题

1738年，瑞典数学家欧拉解决了哥尼斯堡七桥问题。他将四块陆地视为结点，七座小桥成为连接四个结点的连线，从而证明了这样的路径是不存在的。由此图论诞生，欧拉也成为图论的创始人。

本章主要介绍一些图论的基本概念、符号和相关结果，供初学者入门。^[1～3]