当时人们热衷于这样的游戏：设想从任一个地方出发通过每座桥一次且仅一次后回到原地,这是否可能?但多次实践都发现不行1727年欧拉的朋友向欧拉提出了这个问题是否有解？1736年欧拉用图论的方法解决了这个问题,写了第一篇图论的论文,成为图论的创始人。后来称此问题为哥尼斯堡七桥问题。在图a中,用边表示桥,顶点表示岛屿和河的两岸,便得到一个图,如图b所示。但在此之后100年间，没有大的进展。直到Kirchhoff(克希霍夫)用树的理论解决了电网络问题，1857年Cayler(凯莱)用统计不同构树的方法来计算CnH2n+1同分异构体数目,这些结果引起了人们的重视,图论的研究进入了一个发展时期,在此期间,出现了两个著名的问题:四色问题和Hamilton回路问题,成为不少数学家的研究目标。但在19世纪后期和二十世纪初，图论的研究再次处于停顿状态。直到1920年,科尼格(Konig)攥写了许多图论方面的论文,在1936年科尼格(Konig)发表了第一本图论书籍《有限图与无限图理论》，总结了200年来图论研究的主要成果。此后的50年，图论经历了一场爆炸性的发展，成为数学科学中一门独立的学科。主要分支有图论、超图理论、极值图论、算法图论、网络图论和随机图论等。几十年来图论在理论上和应用上都得到很大的发展,特别是在近30多年来由于计算机的广泛应用而又得到飞跃的发展。在计算机科学、运筹学、化学、物理和社会科学等方面都取得了不少成果，对计算机学科中的操作系统研究、编译技术、人工智能和计算机网络等方面都有广泛的应用。这里主要讨论图的基本概念和算法，为今后的学习和研究打下基础。5.1引言例如有向图G=(V,E),V={a,b,c,d,e,f,g},E={(a,b),(a,c),(b,c),(c,a),(c,c),(c,e),(d,a),(d,c),(f,e),(f,f)},弧(a,b)表示从顶点a到顶点b的一条带箭头的线。定义5.2：顶点a和b称为弧(a,b)的端点,a为起点,b为终点。称a和b与弧(a,b)关联。若顶点a和b相同,则对应的弧(a,b)称为自环。若V中某顶点与E中任何弧都不关联,则该顶点称为孤立点。与一条弧相关联的两个顶点称为邻接的或相邻的。一顶点关联于几条弧,称这些弧是弧邻接或弧相邻。在研究有向图时,只考察它的顶点与弧的连接关系以及整个图形所具有的性质。至于各顶点之间的相对位置及弧的长短曲直都是无关紧要的。对于有向图，弧集中的元素都是有序对，若改成无序对，则就是下面介绍的无向图。定义5.3：设V是一个非空集,E是以V中两个元素组成的多重集为元素的集合,称有序对(V,E)为无向图,也记为G=(V,E)或G(V,E)。V中的元素称为顶点或点,V称为顶点集,E中的元素称为边,E称为边集。E中元素现在也是集合，由于可能出现{a,a}这种情况，所以说E中元素是V中两个元素组成的多重集。定义5.7：若图G=(V,E)中,连结两个顶点之间的边可以不止一条这些边称为多重边,则图G称为多重图。无自环的非多重图称为简单图。边集为空集的图称为零图。只有一个顶点的图称为平凡图。若G中每两个顶点之间恰有一条边,则称G为完全图。n个顶点的完全图记为Kn。在定义5.7中,零图是指没有边的图,其每个顶点为孤立点,但顶点集V不能是空集。同样在有向图中，也可定义多重弧，多重有向图和简单有向图。为了叙述方便起见,简称无向图为图,如果在图(有向图)中顶点标以名称,如上图中顶点标a,b,c,d,e,f,g,这样的图(有向图)称为标定图(有向图),否则称为非标定图(有向图)。下面主要考虑标定图。如果一个图的顶点集和边集是有限的,则称该图为有限图,类似地定义有限有向图。我们这里讨论的图和有向图是指有限图和有限有向图。图(有向图)的最本质的内容就是顶点与边(弧)的关联关系。为了描述这一关系,现在引进一个重要的概念,即顶点的度数。二、顶点度数定义5.4：设G=(V,E)是一个图,顶点v所关联的边数(有自环情况要计算两次),称为顶点v的度数,记为d(v)。度数为1的顶点称为悬挂点。度数为奇(偶)数的顶点称为奇(偶)顶点。图G中顶点的最小度数记为(G),(G)=minvV{d(v)},简记为。在这里要注意：对于边{a,b},在计算顶点a的度数和b的度数时分别都被用了一次，因此对于自环，此时b=a,{a,a},同样要统计两次。证明：对每条边来讲，有两个端点，在计算顶点度数时，每条边被计算了两次(极端情况，自环，同一端点同样算了两次)，所以图中所有顶点度数之和为边数的两倍。定理5.2:奇顶点有偶数个。定义5.5：设G是一个有向图,以顶点v为起点的弧数称为v的出度,记为d+(v);以顶点v为终点的弧数称为v的入度,记为d-(v)。