第八讲 图论概念和一笔画问题
（教材：第八章 图论概念和一笔画问题）
一． 图的基本概念
二． 欧拉环游及弗莱里算法
三． 中国邮递员问题
四． 实际问题应用举例
一． 图的基本概念
图
现实生活中，我们经常碰到一些现象，如：在一群人中有些人互相认识，有些人互相不认识。又如：某航空公司在 100 个城市之间建立若干航线，某些城市间有直达航班，而另一些城市间没有直达航班等等。以上现象都有共同内容：一是有研究的“对象”，如人，城市等；二是这些对象之间存在着某种关系：如互相认识，有直达航班等。为了表示这些对象以及对象之间的关系，我们将“点”代表“对象”，“边”表示“对象之间的关系”，引出了“图”这个概念。
图：由若干个不同的点与连接其中某些顶点的边所组成的图形，称为图。
由此可见，图有二要素：“点”和“边”： “点”表示对象，“边”反映对象之间的关系。图由顶点集
和边集 
构成，我们记为 G(V,E) 。
网络：对图中的顶点和边赋以具体的含义和权，这样的图称为网络。
边 e 可以表示为
e＝（
），称 
和 
是边 e 的端点，边 e 与点 
和 
关联。
次：与某一点 
关联的边的数目称为点 
的次。
奇点：次为奇数的点。 偶点：次为偶数的点。
对于图 G
中一个点、边交错的序列 
链：如果
，
且 
互不相同，称这个序列是 
到
的链。
闭链：如
与 
相同，称这条链为闭链。
路：如果链中的各点也不同，称这样的链为路。
圈：如
互不相同的闭链称为圈。
连通：若 G
中两点 u 和 v 之间存在路，则称 u 和 v
是连通的。连通关系是一种等价关系
，可以把图中的点分成若干部分，使得同一部分的点总是连通的，不同的部分总是不连通的。每
个部分连同连接它们的边（两个端点都在同一部分的边）称为组成 G
的一个分图。
若 G 只有一个分图，则 G 是连通的。
在一个网络 N=(V,E,W)
中，
环游：经过 N 中每一边至少一次的闭链称为 N 的环游。
欧拉环游： 经过 N 中每一边恰好一次的环游称为欧拉环游。可见，“能一笔画”的图即该图“有欧拉环游”。
注意：若 N 有欧拉环游，则它的每个欧拉环游具有相同的权，也是最优环游。