第2章　圖論簡介

圖論是一門應(yīng)用十分廣泛的數(shù)學(xué)分支，應(yīng)用圖論解決運(yùn)籌學(xué)、物理、化學(xué)、生物、計(jì)算機(jī)科學(xué)、網(wǎng)絡(luò)理論、信息論、控制論、社會(huì)科學(xué)以及管理科學(xué)方面的問題都有其獨(dú)特的優(yōu)越性。圖論與數(shù)學(xué)的其他分支如群論、矩陣論、概率論、拓?fù)?、?shù)值分析、組合數(shù)學(xué)等都有著密切的關(guān)系。事實(shí)上，圖為任何一個(gè)包含一種二元關(guān)系的系統(tǒng)提供了一種數(shù)學(xué)模型。

眾所周知，圖論起源于一個(gè)非常經(jīng)典的問題——哥尼斯堡七橋問題（見圖2-1）。普萊格爾河流經(jīng)哥尼斯堡小城，河中有兩個(gè)小島，在四塊陸地之間修建了七座小橋，將河中間的兩個(gè)島和河岸聯(lián)結(jié)起來。是不是可能存在路徑，使得人們可以走遍四個(gè)地區(qū)，而且把每座橋走一次并且只走一次?這在圖論中稱為“歐拉圖”問題。

圖2-1　七橋問題

1738年，瑞典數(shù)學(xué)家歐拉解決了哥尼斯堡七橋問題。他將四塊陸地視為結(jié)點(diǎn)，七座小橋成為連接四個(gè)結(jié)點(diǎn)的連線，從而證明了這樣的路徑是不存在的。由此圖論誕生，歐拉也成為圖論的創(chuàng)始人。

本章主要介紹一些圖論的基本概念、符號(hào)和相關(guān)結(jié)果，供初學(xué)者入門。^[1～3]