[拼音]：tulun

[外文]：graph theory

研究节点和边组成的图形的数学理论和方法，为运筹学的一个分支。图论的基本元素是节点和边（也称线、弧、枝），用节点表示所研究的对象，用边表示研究对象之间的某种特定关系。因此，图论可用节点和边组成的图形及其有关的理论和方法来描述、分析和解决各种实际问题，诸如物理学、化学、生物学、管理科学、计算方法和工程技术等领域的有关问题。图论与组合数学、线性规划、群论、矩阵论、概率论、数值分析等数学分支有密切的关系。

1736年瑞士数学家L.欧拉发表图论的第一篇论文,解决了著名的柯尼斯堡七桥问题,因此通常认为欧拉是图论的创始人。流经东普鲁士的柯尼斯堡的普莱格尔河上有七座桥，将河中的岛和河岸连接起来（图1）。长期以来人们在议论能否从A、B、C、D这四块陆地中的任何一块开始,经过所有的桥一次且仅一次，最后回到原来出发的这块陆地。当时，欧拉将每块陆地用一个点来代替，将每座桥用连接相应的两个点的一条边来代替,从而得到了一个“图”（图2）。欧拉对于一般的图提出了一个普遍的判别法则：要从图中一点出发，经过所有的边一次且仅一次，能回到原来的出发点，则这个图必须是连通的，且每个点都必须与偶数条边相关联。显然,图2中的各点都是连通的，但每个点都不是与偶数条边相连接，因此七桥问题不可能有解。1845年，德国物理学家G.R.基尔霍夫为了解决一类线性联立方程组而创建“树”理论。他把电网络和其中的电阻、电容和电感等抽象化，用一个只有点和边组成的组合结构来代替电网络，而不指明每条边所代表的电器元件种类,这样就可以方便地对方程组进行求解。图3为一电网络(N)及其基本图(G)和它的一个生成树(T)。 1852年F.格思里在对地图着色时发现,无论多么复杂的地图,只要用四种颜色就能将相邻区域区分开来。这就是所谓“四色猜想”。经过百余年的努力，直到1976年才由K.阿佩尔和W.赫肯借助电子计算机证明了四色定理。1856年，W.R.哈密顿在给 R.L.格雷夫斯的信中提出一个游戏：用正十二面体上20个顶点表示20个城市，要求游戏者沿着各边行走，走遍每个城市一次且仅一次，最后回到原出发城市。这个游戏促使人们研究如何判断一个图有无这一性质，如果有，则又如何确定这样的路径。这是一个至今尚未完全解决的问题（图4）。 1962年中国数学家管梅谷提出一个所谓“中国邮路问题”：邮递员带着邮件从邮局出发，走遍他所管辖的每一条街道，最后回到邮局，如何选择路线，使走的路程最短。1967年埃德蒙兹给出中国邮路问题一个好的解法。1936年出版D.克尼希第一本关于图论的书。60年代以来图论在各种学科领域中得到了广泛应用。图论在理论上也得到了新的发展，如W.图特等发展了拟阵理论，C.贝尔热等发展了超图理论，P.埃尔德什等发展了极图理论等。

图论中所研究的图就是节点和边的集合，记作G＝(V，E),其中V表示非空的节点集合，E表示边的集合。图5中,V＝{v₁,v₂,v₃,v₄,v₅,v₆},E＝{e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈},其中e₁＝[v₁,v₁],e₂＝[v₁,v₂],…。在图的研究中常用到的概念有：

（1）节点数和边数：集合V的元素个数称为图G的节点数;集合E的元素的个数称为图G的边数。

（2）端点和关联边：若e＝[v_i，v_j]∈E,则称点v_i和v_j是e的端点，而称e是点v_i和v_j的关联边。

（3）相邻点和相邻边:若v_i和v_j与同一条边相关联,则v_i与v_j是相邻点；若e_i与e_j有一个共同端点,则若e_i与e_j为相邻边。

（4）环和多重边:若边的两个端点同属一个节点,则称该边为环；若两个端点之间多于一条边，则称多重边。

（5）多重图和简单图：含有多重边的图称为多重图；无环无多重边的图称为简单图。

（6）次：以点 v为端点的边数称为这个点的次，记作d(v)。如图5中d(v₂)=4。

（7）悬挂点和悬挂边：次为1的点称为悬挂点;与悬挂点连接的边为悬挂边。

（8）奇点和偶点:次为奇数的点为奇点,否则为偶点。

（9）空图：若图G中E＝∅（空集）,则G为空图。

（10）孤立点：空图的点或次为零的点，均称为孤立点。

如果图G 的任意两点至少有一条通路连接起来，则图G称为连通图，否则称为不连通图（图6）。连通图也有一些常用的概念：

（1）链：若图G的节点的序列P＝{v₁,v₂,…,v_k}中,相继两节点在图中都是相邻的,则称P是一条连接v₁和v_k的链。

（2）有向连通图和无向连通图：给每条边规定一个方向，即各节点间用带有箭头的边连接时，称为有向连通图；否则为无向连通图（图7）。

（3）强连通图：在有向连通图中所有顶点间都有互通的边存在时，则这种有向连通图称为强连通图（图8）。

在研究和描述图的性质和图的局部结构中，子图的概念占有重要地位。对于图G₁＝(V₁,E₁)，G₂＝(V₂,E₂)，若V₁吇V₂，E₁吇E₂，则称G₁为G₂的子图。若V₁嶅V₂,E₁嶅E₂,即 G₁不包含G₂中所有节点和边，则称G₁为G₂的真子图,如图9中右图是左图的真子图。若V₁=V₂,E₁嶅E₂，则称 G₁为G₂的支撑子图。若V₁吇V₂，E₁＝{[u，v]∈E₂|u∈V₁,v∈V₁}，则称G₁是G₂由V₁导出的子图，记作G(V₁)。

树是图论中的一个重要概念。一个图中如果没有由节点和边组成的圈就称为无圈图。树就是一个连通的无圈图。图10给出有6个节点的不同的树。如果连通图G＝(V，E)的支撑子图T＝(V，E_T)是树,则称T为G 的支撑树（图11）。若T＝(V，E_T)是支撑树，则称堟＝(V，E\E_T)为G 的余树（图12）。

一个图由它的邻接性和关联性完全决定，这种信息可用矩阵表示。常用的有邻接矩阵和关联矩阵等。

（1）邻接矩阵 A：用来表示图中各节点之间连通状态的矩阵。A的元素a_ij可定义为

图13中图G 的邻接矩阵A为

（2）关联矩阵 S：用来描述节点和边之间的关联关系的矩阵。S的元素s_ij可以定义为

图13中图G 的关联矩阵S为

其他还有能用来描述基尔霍夫电流定理和电压定理的割集矩阵和圈矩阵等。

参考书目

1. 李修睦:《图论导引》,华中工学院出版社,武汉,1982。
2. F.Harary著,李慰萱译：《图论》,上海科学技术出版社，上海，1981。
3. J.A.Bondy，U.S.R.Murty，Graph Theory with Applications,MacMillan Press, London, 1976.